A graph based simplex method for the integer minimum perturbation problem with sum and difference constraints

Abstract

The integer minimum perturbation problem with sum and difference constraints is stated as follows: minimize f(x) = a1|x1 - b1| + a2|x2 - b2| +...+ a n|xn - bn| under constraints ±x i1 ± xj1 ≥ c1, ±xi2 ± xj2 ≥ c2, ... ... ... ±xim ±xjm ≥ Cm, where the sign in front of each variable is either "+" or "-", a1, a 2,..., an ≥ 0 and all variables and constants are integers. The minimum perturbation problem [6] arose from layout migration. The sum and difference constraints arose from the hierarchical nature of the layout. We proposed and implemented a graph based algorithm to solve this optimization problem. Our algorithm consists of two steps. First find the optimal solution for the non-integer version of the problem by using a modification of simplex method which takes advantage of the special form of the constraints (a graph based simplex method). Then find an integer solution close to the optimal by solving a 2-SAT problem. The time complexity of the algorithm is O(p(m + n)), where p is the number of pivots in the simplex algorithm; note that the regular simplex method, being applied to this problem, would require O(pn(m + n)) time. Our result on production layouts shows that the runtime scale very well with a O(nlog(n)) scanline algorithm used to generate the constraints for the layouts. This makes it a very practical solver for the problem.