How to Add Cuts to Integer Linear Programming

Linear programming is a mathematical method of optimizing mathematical functions under a set of constraints. Integer linear programming takes linear programming one step further by placing an additional constraint on the set of solutions: only integers are to be considered as solutions. A cut, in terms of integer linear programming, puts one more constraint on the already heavily constrained mathematical problem. However, this extra constraint is not without meaning--it often changes the problem in a manner that allows the solution to appear more quickly. Adding a cut to an integer linear programming problem involves rearranging the optimal tableau of the problem's solution.

Instructions

    • 1

      Solve the integer linear programming problem up until the optimal tableau is reached. Use the standard method of integer linear programming until the optimal tableau is visible.

    • 2

      Choose one of the constraints on the tableau. The choice is arbitrary. The constraints in the tableau appear as rows. Choose any row besides the very bottom row (this is the optimization function and not a constraint).

    • 3

      Write the constraint in its mathematical form. It should be clear from the tableau how to write this. Write each element in the row multiplied by the variable in its corresponding column. Sum the elements and equate them to the number that appears in the far-right entry in the row.

    • 4

      Manipulate the equation so that only integers appear on the left-hand side and only fractions appear on the right-hand side. For example, if your equation is (3/2)x + 3y = 58/30, use algebra to rearrange this to x + 3y -- 1 = -(1/2)x + 28/30.

    • 5

      Take the right-hand side from the new equation and constrain it. Notice that the right-hand side will only get smaller and negative as the x-variable increases. Thus, bound the right-hand side to be less than zero. Your constraint is now --(1/2)x + 28/30 < 0. This constraint is the cut.

    • 6

      Add the cut to the original integer linear programming problem as a new constraint. If your original problem had "n" constraints, your new integer linear programming problem with a cut has "n + 1" constraints, and will yield a different solution (as well as a different optimal tableau).

Learnify Hub © www.0685.com All Rights Reserved