A Graph Based Simplex Method for the Integer Minimum Perturbation Problem with Sum and Difference Constraints

The integer minimum perturbation problem with sum and difference constraints is stated as follows: minimize

f(x) = a1 * |x1-b1| + a2 * |x2-b2| + ... + an * |xn-bn|

under constraints

+- x{i1} +- x{j1} >= c1,
+- x{i2} +- x{j2} >= c2,
... ... ...
+- x{im} +- x{jm} >= cm,

where the sign in front of each variable is either "$+$" or "$-$", a1,a2, ..., a_n >= 0 and all variables and constants are integers. The minimum perturbation problem 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(n log(n)) scanline algorithm used to generate the constraints for the layouts. This makes it a very practical solver for the problem.