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 )= a 1 x 1 b 1 + a 2 - b 2 ++ a n x n - b n under constraints  x i1  x j1 ? c 1 ,  x i2  x j2 ? c 2 ,     x im  x jm ? cm , where the sign in front of each variable is either "+" or "-", a 1 ; a 2  a n ?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.
optimization linear programming design migration