Integer Programming PDF

# Integer Programming Rachana Mehta ## Types | | Linear programming problems | Nonlinear programming problems | |:---|:---|:---| | | All-integer problem | Mixed-integer problem | Zero-one problem | Polynomial programming problem | General nonlinear problem | | Solving Methods | Cutting plane m...

# Integer Programming Rachana Mehta ## Types | | Linear programming problems | Nonlinear programming problems | |:---|:---|:---| | | All-integer problem | Mixed-integer problem | Zero-one problem | Polynomial programming problem | General nonlinear problem | | Solving Methods | Cutting plane method Branch-and-bound method | Cutting plane method Branch-and-bound method Balas method | | | All-integer problem Mixed-integer problem | | | | | | | Generalized penalty function method Sequential linear integer (discrete) programming method | ## Graphical Method **Maximize** $f(X) = 3x_1 + 4x_2$ **Subject to:** * $3x_1 - x_2 ≤ 12$ * $3x_1 + 11x_2 ≤ 66$ * $x_1 ≥ 0$ * $x_2 ≥ 0$ $x_1$ and $x_2$ are integers The image shows a graph with two lines intersecting at $(5,4)$. The optimal solution occurs at the intersection point of these two lines. This point is $x_1 = 5, x_2 = 4$, and $f = 31$. ## Gomory's Method ### Table 10.2: Optimum Noninteger Solution of Ordinary LP Problem | Basic Variables | $x_1$ | $x_2$ | ... | $xi$ | ... | $xm$ | $y_1$ | $y_2$ | ... | $yj$ | ... | $yn$ | Objective function | Constants | |:---|:---|:---|:---|:---|:---|:---|:---|:---|:---|:---|:---|:---|:---| | $x_1$ | 1 | 0 | 0 | 0 | 0 | 0 | $a_{11}$ | $a_{12}$ | ... | $a_{1j}$ | ... | $a_{1n}$ | 0 | $\bar{b}_1$ | | $x_2$ | 0 | 1 | 0 |0 | 0 | 0 | $a_{21}$ | $a_{22}$ | ... | $a_{2j}$ | ... | $a_{2n}$ | 0 | $\bar{b}_2$ | | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | | $x_i$ | 0 | 0 | 1 | 0 | 0 | 0 | $a_{i1}$ | $a_{i2}$ | ... | $a_{ij}$ | ... | $a_{in}$ | 0 | $\bar{b}_i$ | | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | | $x_m$ | 0 | 0 | 0 | 1 | 0 | 0 | $a_{m1}$ | $a_{m2}$ | ... | $a_{mj}$ | ... | $a_{mn}$ | 0 | $\bar{b}_m$ | | $f$ | 0 | 0 | 0 | 0| ... | 0 | $c_1$ | $c_2$ | ... | $c_j$ | ... | $c_n$ | 1 | $\bar{f}$ | ### Gomory's Method Procedure: The Gomory's method is used to get an integer solution after finding an optimum non-integer solution of the ordinary LP problem. **Step 1:** Express the basic variable which has integer restrictions from the ith equation of Table 10.2 as: $x_i = \bar{b}_i - \sum_{j=1}^n a_{ij}y_j$ **Step 2:** Write $\bar{b}_i$ and $a_{ij}$ as follows: * $\bar{b}_i = b_i + \beta_i$ * $\bar{a}_{ij} = \hat{a}_{ij} + \alpha_{ij}$ where: * $b_i$ and $\hat{a}_{ij}$ are integers obtained by truncating the fractional parts from $\bar{b}_i$ and $\bar{a}_{ij}$ * $\beta_i$ is a strictly positive fraction (0 < $\beta_i$ < 1) * $\alpha_{ij}$ is a nonnegative fraction (0 ≤ $\alpha_{ij}$ < 1) **Step 3:** Using the values above, rewrite the equation for $x_i$ as: $\beta_i - \sum_{j=1}^n \alpha_{ij}y_j = x_i - b_i + \sum_{j=1}^n \hat{a}_{ij} y_j$ **Step 4:** Since $x_i$ and $y_j$ must be integers at an optimal integer solution, the right-hand side of the equation must be an integer. This gives the new constraint: $\beta_i - \sum_{j=1}^n \alpha_{ij}y_j = integer$ **Step 5:** Notice that $\alpha_{ij}$ is a nonnegative fraction and $y_j$ is a nonnegative integer. Hence $\sum_{j=1}^n \alpha_{ij}y_j$ will be nonnegative number. Since $\beta_i$ is a strictly positive fraction, rewrite the new constraint as: $\beta_i - \sum_{j=1}^n \alpha_{ij}y_j ≤ \beta_i < 1$ **Step 6:** The quantity $\beta_i - \sum_{j=1}^n \alpha_{ij}y_j$ must be an integer (from the constraint above) and can be either zero or a negative integer. This results in the following Gomory constraint: $\beta_i - \sum_{j=1}^n \alpha_{ij}y_j ≤ 0$ **Step 7:** Add a nonnegative slack variable $s_i$ to the Gomory constraint equation and rewrite it as: $s_i - \sum_{j=1}^n \alpha_{ij}y_j = -\beta_i$ where $s_i$ is an integer. **Step 8:** Insert the Gomory constraint into the final tableau of the ordinary LP problem and solve with the dual simplex method. The newly generated solution will be infeasible. This indicates that the original optimal solution does not satisfy the new constraint. **Step 9:** Use the dual simplex method to find a new optimal solution that does satisfy the new constraint. Repeat steps 1 through 8 until the obtained solution satisfies the integer requirement. ### Gomory's Method for all integer This method uses iterations to find the optimal values of the variables. **Step 1:** Solve the LP problem, neglecting the integer requirement, using the simplex method. The image shows a tableau with the initial values of the basic variables. The pivot is chosen by finding the most negative entry in the objective function. **Step 2:** Generate a Gomory constraint. Since the solution is noninteger, a Gomory constraint must be added to the last tableau. The image shows the initial tableau at step 2 with the Gomory constraint added. **Step 3:** Apply the dual simplex method to find a new optimum solution. The process continues until the final tableau is reached. **Step 4:** Repeat steps 2 and 3 for each variable with the integer constraint. ### Gomory's Constraint for MIP * Consider the final tableau of an LP problem consisting of n basic variables (original variables) and m non-basic variables (slack variables). * Let $x_i $ be the basic variable which has integer restrictions. * From the ith equation, express this variable as: $x_i = b_i - \sum_{j=1}^m c_{ij}y_j$ Where $b_i$ is an integer part plus a fractional part: $b_i = \bar{b}_i + β_i$ And $c_{ij}$ is expressed as: $c_{ij} = c_{ij}^+ + c_{ij}^-$ Where: * $c_{ij}^+= c_{ij}$ if $c_{ij} ≥ 0$ * $c_{ij}^+= 0$ if $c_{ij}$ < 0 And * $ c_{ij}^- = 0$ if $c_{ij} ≥ 0$ * $c_{ij}^- = c_{ij}$ if $c_{ij}$ < 0 * The new equation is: $\sum_{j=1}^m (c_{ij}^+ + c_{ij}^-)y_j = β_i + (\bar{b}_i -x_i)$ Since $x_i$ and $\bar{b}_i$ are restricted to take integer values and 0 < $β_i <1$, the value of $β_i + (\bar{b}_i -x_i)$ can be ≥ 0 or <0. * Thus we have to consider two cases **Case 1:** $β_i + (\bar{b}_i -x_i)≥0$. For $x_i$ to be an integer: $β_i + (\bar{b}_i -x_i)= β_i$ or $β_i +1$ or $β_i +2$, ..... This leads to: $\sum_{j=1}^m (c_{ij}^+ + c_{ij}^-)y_j ≥ β_i$ Final form: $\sum_{j=1}^m c_{ij}^+ y_j ≥β_i$ **Case 2:** $β_i + (\bar{b}_i -x_i) < 0$. For $x_i$ to be an integer: $β_i + (\bar{b}_i -x_i)= -1 + β_i$ or $-2 + β_i$ or $-3 + β_i$,... This leads to: $\sum_{j=1}^m (c_{ij}^+ + c_{ij}^-)y_j ≤ β_i - 1$ Final form: $\sum_{j=1}^m c_{ij}^- y_j ≤ β_i - 1$ **Gomory constraint for MIP:** The final form of Gomory constraint after adding one slack variable $s_i$ for the two cases can be expressed as: $s_i - \sum_{j=1}^m c_{ij}^+ y_j - \frac{β_i}{β_i-1} \sum_{j=1}^m c_{ij}^- y_j = -β_i$ ### Mixed Integer Programming * Solve the problem as an ordinary LP problem, neglecting the integrality constraints. * Generate a Gomory constraint for each fractional valued variable that has integer restrictions. * Insert a new row with the coefficients of this constraint to the final tableau of the ordinary LP problem. * Solve this by applying the dual simplex method. * Continue this process for all variables that have integrality constraints. ### MIP - Example 1 - SSRao **Minimize** $f = -3x_1 - 4x_2$ **Subject to:** * $3x_1 - x_2 + x_3 = 12$ * $3x_1 + 11x_2 + x_4 = 66$ * $x_i ≥ 0, i = 1 to 4$ * $x_i$ are integers **Step 1:** Solve the LP problem by simplex method, neglecting the integer requirement. This gives a noninteger solution table: | Basic Variables | $x_1$ | $x_2$ | $y_1$ | $y_2$ | $-f $ | $\bar{b}_i$ | |:---|:---|:---|:---|:---|:---|:---| | $x_1$ | 1 | 0 | $\frac{11}{36}$ | $\frac{1}{36}$ | 0 | $\frac{11}{2}$ | | $x_2$ | 0 | 1 | $\frac{-12}{12}$ | $\frac{12}{12}$ | 0 | $\frac{69}{2}$ | | $-f$ | 0 | 0 | $\frac{7}{12}$ | $\frac{5}{12}$ | 1 | $\frac{69}{2}$ | The noninteger solution is: $x_1 = \frac{11}{2}, x_2 = \frac{69}{2}, y_1 = y_2 = 0, f_{min} = -\frac{69}{2}$ **Step 2:** Formulate a Gomory constraint. Since $x_2$ is the only variable restricted to take integer values, construct the Gomory constraint for $x_2$: $\bar{b}_2 = \hat{a}_{21}y_1 + \bar{a}_{22}y_2$ Using the values from the table: $\bar{b}_2 = \frac{69}{2}, \bar{a}_{21} = \frac{-12}{12} = -1, \bar{a}_{22} = \frac{12}{12} = 1$ Apply the Gomory constraint equation with the values of $β_i$ and $\bar{a}_{ij}$ in the table. **Step 3:** Apply the dual simplex method to find a new optimum solution. The new solution is given by the table: | Basic Variables | $x _1$ | $x_2$ | $y_1$ | $y_2$ | $-f$ | $s_2$ | $\bar{b}_i$ | |:---|:---|:---|:---|:---|:---|:---|:---| | $x_1$ | 1 | 0 | $\frac{1}{3}$ | 0 | 0 | $\frac{1}{16}$ | $\frac{11}{2}$ | | $x_2$ | 0 | 1 | $0$ | 0 | 0 | $\frac{1}{4}$ | $4$ | | $-f$ | 0 | 0 | $-1$ | 1 | 1 | $-12$ | $32$ | | $y_2$ | 0 | 0 | $-1$ | 1 | 0 | $-12$ | $6$ | The desired integer solution is: $x_1 = 5\frac{1}{2}, x_2 = 4, y_2 = 6, y_1 = 0, s_2 = 0, f_{min}=-32$ ### MIP - Example 2 Consider the previous problem with integer constraint only on $x_2$: **Maximize** $z = 3x_1 + x_2$ **Subject to:** * $2x_1 - x_2 ≤ 6$ * $3x_1 + 9x_2 ≤ 45$ * $x_1, x_2 ≥ 0$ * $x_2$ is an integer **Standard form of the problem** **Maximize** $z = 3x_1 + x_2$ **Subject to:** * $2x_1 - x_2 + y_1 = 6$ * $3x_1 + 9x_2 + y_2 = 45$ * $x_1, x_2, y_1, y_2 ≥ 0$ * $x_2$ is an integer **Solve the problem as an ordinary LP**. The optimal solution is: * $z = \frac{123}{7}$ * $x_1 = \frac{33}{7}$ * $x_2 = \frac{24}{7}$ **Step 2:** Generate a Gomory constraint for $x_2$. The equation is: $x_2 = \frac{24}{7} + \frac{1}{7}y_2 - \frac{2}{21} y_1$ **Step 3:** Add the new constraint to the tableau and solve it using the dual simplex method. The optimal solution is: * $z = \frac{33}{2}$ * $x_1=4.5$ * $x_2 = 3$ * $y_2 = 4.5$ This solution satisfies all the constraints and is the desired solution.