MILP Factory › Example

Let's work through a concrete factory optimization example step by step. Consider a factory that produces two products using two machines with the following specifications:

Problem Setup:

• Product 1: requires 2 hours on Machine A, 4 hours on Machine B, profit of $3 per unit
• Product 2: requires 3 hours on Machine A, 2 hours on Machine B, profit of $2 per unit
• Machine A: 12 hours available
• Machine B: 16 hours available
• Additional constraint: We can only produce products in whole units (integer constraint)

Step 1: Define Variables

Let $x_1$ = number of units of Product 1 to produce Let $x_2$ = number of units of Product 2 to produce

Step 2: Formulate the Problem

Our objective is to maximize profit: $\max 3x_1 + 2x_2$

Subject to constraints:

• Machine A capacity: $2x_1 + 3x_2 \leq 12$
• Machine B capacity: $4x_1 + 2x_2 \leq 16$
• Non-negativity: $x_1, x_2 \geq 0$
• Integer constraint: $x_1, x_2 \in \mathbb{Z}$

Step 3: Solve the LP Relaxation First

If we ignore the integer constraint, we can solve this as a linear program. We need to find where the constraint boundaries intersect, which gives us the optimal solution.

From Machine A constraint: $2x_1 + 3x_2 \leq 12$, we can express $x_2$ as:

From Machine B constraint: $4x_1 + 2x_2 \leq 16$, we can express $x_2$ as:

To find the intersection point where both constraints are binding (satisfied with equality), we set the two expressions equal:

Multiplying both sides by 3 to eliminate the denominator:

Expanding the right side:

Rearranging terms to collect $x_1$ on one side:

Simplifying:

Solving for $x_1$:

Substituting $x_1 = 3$ back into the Machine A constraint (with equality) to find $x_2$:

Simplifying:

Solving for $x_2$:

Verification: Let's verify this solution satisfies both constraints:

• Machine A: $2(3) + 3(2) = 6 + 6 = 12 \leq 12$ ✓
• Machine B: $4(3) + 2(2) = 12 + 4 = 16 \leq 16$ ✓

So the LP relaxation gives us $x_1 = 3, x_2 = 2$ with profit:

The optimal profit is \13$.

Step 4: Apply Branch-and-Bound

Since we need integer solutions, we use branch-and-bound:

Branch 1: $x_1 \leq 3$

• New constraint: $x_1 \leq 3$
• With $x_1 = 3$ fixed, from Machine A: $2(3) + 3x_2 \leq 12$, so $3x_2 \leq 12 - 6 = 6$, giving $x_2 \leq 2$
• From Machine B: $4(3) + 2x_2 \leq 16$, so $2x_2 \leq 16 - 12 = 4$, giving $x_2 \leq 2$
• The binding constraint is $x_2 \leq 2$, so the solution is $x_1 = 3, x_2 = 2$ (this is already an integer solution)
• Profit = $3(3) + 2(2) = 9 + 4 = 13$

Branch 2: $x_1 \geq 4$

• New constraint: $x_1 \geq 4$
• From Machine B: $4x_1 + 2x_2 \leq 16$, with $x_1 = 4$: $4(4) + 2x_2 \leq 16$
• Simplifying: $16 + 2x_2 \leq 16$, so $2x_2 \leq 0$, giving $x_2 \leq 0$
• Since $x_2 \geq 0$ (non-negativity), we have $x_2 = 0$
• Solution: $x_1 = 4, x_2 = 0$ (integer solution)
• Profit = $3(4) + 2(0) = 12 + 0 = 12$

Branch 1.1: $x_1 \leq 3$ and $x_2 \leq 1$

• With $x_1 = 3$ and $x_2 = 1$:
• Verification: Machine A: $2(3) + 3(1) = 6 + 3 = 9 \leq 12$ ✓
• Verification: Machine B: $4(3) + 2(1) = 12 + 2 = 14 \leq 16$ ✓
• Solution: $x_1 = 3, x_2 = 1$ (integer solution)
• Profit = $3(3) + 2(1) = 9 + 2 = 11$

Branch 1.2: $x_1 \leq 3$ and $x_2 \geq 2$

• With $x_1 = 3$ and $x_2 = 2$:
• Verification: Machine A: $2(3) + 3(2) = 6 + 6 = 12 \leq 12$ ✓
• Verification: Machine B: $4(3) + 2(2) = 12 + 4 = 16 \leq 16$ ✓
• Solution: $x_1 = 3, x_2 = 2$ (integer solution)
• Profit = $3(3) + 2(2) = 9 + 4 = 13$

Step 5: Compare Integer Solutions

We have found three feasible integer solutions:

• Solution 1: $x_1 = 3, x_2 = 1$, Profit = $3(3) + 2(1) = 9 + 2 = 11$
• Solution 2: $x_1 = 4, x_2 = 0$, Profit = $3(4) + 2(0) = 12 + 0 = 12$
• Solution 3: $x_1 = 3, x_2 = 2$, Profit = $3(3) + 2(2) = 9 + 4 = 13$

Since we're maximizing profit, the optimal integer solution is Solution 3: $x_1 = 3, x_2 = 2$ with a profit of \13$.

Note: In this example, the LP relaxation solution $(3, 2)$ happens to be an integer solution, so the integer constraint doesn't reduce the optimal value. This is not always the case. Often, integer constraints force us to accept a lower objective value than the LP relaxation.

Let's visualize this example to see the LP relaxation solution compared to the integer solutions:

Note: In this case, the LP relaxation happens to give an integer solution. However, the integer constraint ensures we only consider feasible integer points