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.
By: Alexey Lvov, Fook-Luen Heng
Published in: RC23243 in 2004
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .