Integer programming, transportation problem

Integer Programming

Integer programming (IP) is a type of mathematical optimization problem where some or all of the decision variables are restricted to be integers. This is in contrast to linear programming (LP), where variables can take any real value. Many real-world problems, such as those involving discrete choices, indivisible items, or logical constraints, naturally lead to integer variables.

For example, if you are deciding whether to build a factory (a binary choice, 0 or 1), or how many units of a product to manufacture (which must be a whole number), integer variables are necessary.

Types of Integer Programming Problems

Integer programming problems can be broadly classified based on the type of integer variables involved:

• Pure Integer Programming: All decision variables must be integers.
• Mixed Integer Programming (MIP): Some decision variables must be integers, while others can be continuous.
• Binary Integer Programming: All decision variables must be binary (either 0 or 1). These are often used to model yes/no decisions or logical relationships.

Challenges in Integer Programming

Solving integer programming problems is generally much harder than solving linear programming problems. This is because the feasible region for an LP problem is a convex polyhedron, and its optimal solution (if one exists) is guaranteed to be at a vertex. However, for an IP problem, the feasible solutions are just the integer points within that polyhedron. Simply rounding the LP solution to the nearest integer point does not guarantee optimality or even feasibility.

The set of feasible integer solutions does not necessarily form a convex set. The problem of finding an optimal integer solution involves searching through a discrete set of possibilities, which can be computationally intensive.

Methods for Solving Integer Programming Problems

Several methods have been developed to solve IP problems. The most common ones include:

1. Branch and Bound Method: This is a widely used technique. It systematically enumerates all possible integer solutions by partitioning the problem into smaller subproblems.
2. Cutting Plane Method: This method starts with an LP relaxation of the IP problem and iteratively adds linear constraints (called "cuts") that eliminate non-integer solutions without removing any feasible integer solutions.
3. Branch and Cut Method: This is a hybrid approach that combines branching and cutting.
4. Heuristic Methods: These methods aim to find good, but not necessarily optimal, solutions quickly. They are useful for very large or complex problems where finding the exact optimum is computationally infeasible.

The Branch and Bound Method Explained

The Branch and Bound method is a fundamental algorithm for solving optimization problems, especially integer programming. It works by:

1. Initialization: Start with the original IP problem. Solve its LP relaxation (i.e., ignore the integer constraints).
2. Bounding: The optimal value of the LP relaxation provides an upper bound (for maximization problems) or a lower bound (for minimization problems) on the optimal integer solution.
3. Branching: If the LP solution is integer-feasible, it might be the optimal integer solution. If not, select a variable that has a non-integer value. Create two new subproblems by adding constraints that force this variable to take integer values greater than or equal to its current value, and less than or equal to its current value. For example, if variable $x$ has a value of 3.7, you create two subproblems: one with the added constraint $x \ge 4$ and another with $x \le 3$.
4. Bounding (again): Solve the LP relaxation of each new subproblem. This helps to establish bounds for these subproblems.
5. Pruning (Fathoming): A subproblem can be pruned (discarded) if:
   • Its LP relaxation is infeasible.
   • Its LP solution is integer-feasible. If this integer solution is better than the best integer solution found so far, update the best known integer solution.
   • The bound obtained from its LP relaxation is worse than the best integer solution found so far.
6. Iteration: Repeat the branching and bounding process on the remaining subproblems until all subproblems have been pruned. The best integer solution found during this process is the optimal solution to the original IP problem.

The Cutting Plane Method Explained

The Cutting Plane method is another important technique for solving integer programming problems. The core idea is to start with the LP relaxation of the IP problem and then add constraints that cut off fractional solutions without cutting off any integer solutions.

The process is as follows:

1. Solve LP Relaxation: Solve the LP relaxation of the IP problem.
2. Check for Integer Feasibility: If the solution is integer-feasible, it is the optimal solution.
3. Generate a Cut: If the solution is not integer-feasible, select a variable with a fractional value. Using the fractional solution, derive a new constraint (a "cut") that is violated by the current fractional solution but satisfied by all integer solutions. A common way to generate cuts is using Gomory's fractional cutting method.
4. Add Cut and Re-solve: Add the new cut to the LP problem and re-solve it.
5. Repeat: Continue this process until an integer-feasible solution is found.

While effective, the cutting plane method can sometimes require many cuts to converge to an integer solution.

Transportation Problem

The transportation problem is a classic optimization problem in operations research that deals with finding the least expensive way to ship goods from a set of sources (e.g., factories, warehouses) to a set of destinations (e.g., retail stores, customers). The goal is to satisfy the demand at each destination while respecting the supply at each source, all at the minimum total shipping cost.

Problem Formulation

A typical transportation problem can be defined by:

• A set of $m$ sources, $S_1, S_2, \ldots, S_m$.
• A set of $n$ destinations, $D_1, D_2, \ldots, D_n$.
• The supply available at each source $i$, denoted by $a_i$ (where $i = 1, \ldots, m$).
• The demand required at each destination $j$, denoted by $b_j$ (where $j = 1, \ldots, n$).
• The per-unit cost of shipping from source $i$ to destination $j$, denoted by $c_{ij}$.

The objective is to determine the quantity $x_{ij}$ to ship from source $i$ to destination $j$ such that:

• The total supply from each source does not exceed its availability: $\sum_{j=1}^{n} x_{ij} \le a_i$ for all $i$.
• The total demand at each destination is met: $\sum_{i=1}^{m} x_{ij} \ge b_j$ for all $j$.
• The quantity shipped is non-negative: $x_{ij} \ge 0$ for all $i, j$.

And the total shipping cost is minimized: Minimize $Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}$.

Balanced vs. Unbalanced Transportation Problems

A transportation problem is called "balanced" if the total supply equals the total demand:

$\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j$

If the total supply does not equal the total demand, the problem is "unbalanced."

• If Total Supply > Total Demand: Introduce a dummy destination with zero shipping costs. The demand of this dummy destination will be the excess supply ($\sum a_i - \sum b_j$). This ensures all supply is accounted for.
• If Total Demand > Total Supply: Introduce a dummy source with zero shipping costs. The supply of this dummy source will be the excess demand ($\sum b_j - \sum a_i$). This ensures all demand is met.

Methods for Solving Transportation Problems

There are several methods to solve transportation problems. These methods typically involve two phases: finding an initial basic feasible solution (IBFS) and then improving it to find the optimal solution.

Phase 1: Finding an Initial Basic Feasible Solution (IBFS)

The goal here is to find a feasible solution that satisfies the supply and demand constraints, and has $m+n-1$ basic variables (occupied cells in the transportation tableau). Common methods include:

1. North-West Corner Rule (NWCR): Start at the top-left cell (source 1 to destination 1) and allocate as much as possible. Move to the next cell either to the right or down, depending on whether the row or column is satisfied. It's simple but often results in a high initial cost.
2. Least Cost Method (LCM) / Matrix Minimum Method: Identify the cell with the lowest shipping cost ($c_{ij}$) in the entire tableau and allocate as much as possible. Repeat this for the next lowest cost cell, considering the remaining supplies and demands. This method generally yields a better (lower cost) initial solution than NWCR.
3. Vogel's Approximation Method (VAM): This is often the best method for finding a good initial solution. For each row and column, calculate the "penalty" – the difference between the two lowest costs in that row or column. Choose the row or column with the highest penalty and allocate as much as possible to the cell with the lowest cost in that row/column. Repeat the process, recalculating penalties for remaining rows/columns.

Phase 2: Optimality Test and Improvement

Once an IBFS is found, we need to check if it's optimal. If not, we improve it. The most common method for this is the Stepping Stone Method or the MODI (Modified Distribution) Method.

The MODI Method (Modified Distribution Method)

The MODI method is more efficient than the Stepping Stone method for testing optimality and finding improvements.

1. Calculate Dual Variables ($u_i$ and $v_j$): For each occupied cell $(i, j)$ in the current solution, the cost $c_{ij}$ should ideally equal $u_i + v_j$. We assign $u_1 = 0$ (or any other $u_i$ or $v_j$ to a value) and then solve for the remaining $u_i$ and $v_j$ values using the occupied cells.
2. Calculate Opportunity Costs (or Shadow Prices): For each unoccupied cell $(i, j)$, calculate the potential change in cost if we were to ship one unit along this route. This is given by $d_{ij} = c_{ij} - (u_i + v_j)$.
3. Optimality Check:
   • If all $d_{ij} \ge 0$ for all unoccupied cells, the current solution is optimal.
   • If there is at least one $d_{ij} < 0$, the solution is not optimal. The most negative $d_{ij}$ indicates the route where introducing shipments will yield the greatest cost reduction.
4. Improve the Solution (if not optimal):
   • Identify the unoccupied cell $(i, j)$ with the most negative $d_{ij}$. This cell becomes the 'entering cell'.
   • Form a closed loop (or cycle) starting from the entering cell, using only horizontal and vertical moves, and alternating between occupied and unoccupied cells. The entering cell is the first cell in the loop.
   • Assign alternating positive and negative signs to the cells in the loop, starting with a '+' at the entering cell.
   • Find the minimum allocation (let's call it $\theta$) among the cells in the loop that have a '-' sign.
   • Adjust the allocations: Add $\theta$ to cells with '+' signs and subtract $\theta$ from cells with '-' signs. This will increase the allocation in the entering cell and decrease the allocation in one of the previously occupied cells (which becomes zero, hence an 'exiting cell').
   • Re-calculate the $u_i$ and $v_j$ values for the new basic feasible solution and repeat the optimality check.

Example of a Transportation Problem

Suppose we have two factories (Source 1, Source 2) and three retail stores (Destination 1, Destination 2, Destination 3).

• Factory 1 has a supply of 50 units.
• Factory 2 has a supply of 60 units.
• Store 1 requires 30 units.
• Store 2 requires 40 units.
• Store 3 requires 40 units.

The shipping costs ($c_{ij}$) are given in the table below:

	Store 1 (Demand 30)	Store 2 (Demand 40)	Store 3 (Demand 40)	Supply
Factory 1 (Supply 50)	2	3	4	50
Factory 2 (Supply 60)	3	2	5	60
Demand	30	40	40	110

Step 1: Check if balanced. Total Supply = 50 + 60 = 110. Total Demand = 30 + 40 + 40 = 110. The problem is balanced.

Step 2: Find an Initial Basic Feasible Solution (using Vogel's Approximation Method).

Iteration 1:

• Row 1 penalties: (3-2)=1, (4-3)=1. Minimum cost is 2.
• Row 2 penalties: (3-2)=1, (5-3)=2. Minimum cost is 2.
• Column 1 penalties: (3-2)=1. Minimum cost is 2.
• Column 2 penalties: (3-2)=1. Minimum cost is 2.
• Column 3 penalties: (5-4)=1. Minimum cost is 4.

Highest penalty is 2 (Row 2, Col 3). Let's choose Row 2. The lowest cost in Row 2 is 2 (F2 to D2). Allocate min(Supply F2, Demand D2) = min(60, 40) = 40 units to (F2, D2).

Remaining Supply F2 = 60 - 40 = 20. Remaining Demand D2 = 40 - 40 = 0. Column 2 is satisfied.

Iteration 2:

Recalculate penalties for remaining cells.

• Row 1: (3-2)=1, (4-2)=2. Min cost is 2.
• Row 2: (3-?) is invalid as D2 is satisfied. (5-?) invalid. Only F2 to D1 and F2 to D3 remain. Cost 3 and 5. Penalty 5-3=2. Min cost 3.
• Column 1: (3-2)=1. Min cost 2.
• Column 3: (5-4)=1. Min cost 4.

Highest penalty is 2 (Row 1, Row 2). Let's choose Row 1. Lowest cost in Row 1 is 2 (F1 to D1). Allocate min(Supply F1, Demand D1) = min(50, 30) = 30 units to (F1, D1).

Remaining Supply F1 = 50 - 30 = 20. Remaining Demand D1 = 30 - 30 = 0. Column 1 is satisfied.

Iteration 3:

Remaining problem: F1 (Supply 20) to D2 (Demand 0), D3 (Demand 40). F2 (Supply 20) to D3 (Demand 40).

• Row 1: Only D3 remains. Cost 4.
• Row 2: Only D3 remains. Cost 5.
• Column 3: Min cost is 4 (F1 to D3).

Highest penalty is not clearly defined as only one column remains. Let's pick the lowest cost available. The lowest cost is 4 (F1 to D3). Allocate min(Supply F1, Demand D3) = min(20, 40) = 20 units to (F1, D3).

Remaining Supply F1 = 20 - 20 = 0. Remaining Demand D3 = 40 - 20 = 20. Row 1 is satisfied.

Iteration 4:

Only F2 (Supply 20) to D3 (Demand 20) remains. Allocate 20 units to (F2, D3).

Initial Basic Feasible Solution (IBFS):

• $x_{11} = 30$ (F1 to D1)
• $x_{13} = 20$ (F1 to D3)
• $x_{22} = 40$ (F2 to D2)
• $x_{23} = 20$ (F2 to D3)

Total cost = (30 * 2) + (20 * 4) + (40 * 2) + (20 * 5) = 60 + 80 + 80 + 100 = 320.

Number of occupied cells = 4. $m+n-1 = 2+3-1 = 4$. So, it's a basic feasible solution.

Step 3: Apply MODI Method to check optimality.

Occupied cells: (1,1), (1,3), (2,2), (2,3).

Set $u_1 = 0$.

From (1,1): $c_{11} = u_1 + v_1 \implies 2 = 0 + v_1 \implies v_1 = 2$.

From (1,3): $c_{13} = u_1 + v_3 \implies 4 = 0 + v_3 \implies v_3 = 4$.

From (2,2): $c_{22} = u_2 + v_2 \implies 2 = u_2 + v_2$. (Need $v_2$ first).

From (2,3): $c_{23} = u_2 + v_3 \implies 5 = u_2 + 4 \implies u_2 = 1$.

Now use $u_2=1$ in the equation for (2,2): $2 = 1 + v_2 \implies v_2 = 1$.

So, $u_1=0, u_2=1$ and $v_1=2, v_2=1, v_3=4$.

Step 4: Calculate opportunity costs ($d_{ij} = c_{ij} - (u_i + v_j)$) for unoccupied cells.**

• Cell (1,2): $d_{12} = c_{12} - (u_1 + v_2) = 3 - (0 + 1) = 2$.
• Cell (2,1): $d_{21} = c_{21} - (u_2 + v_1) = 3 - (1 + 2) = 0$.

Step 5: Optimality Check. All $d_{ij} \ge 0$ (2 and 0). Therefore, the current solution is optimal.

The optimal solution is:

• Ship 30 units from Factory 1 to Store 1.
• Ship 20 units from Factory 1 to Store 3.
• Ship 40 units from Factory 2 to Store 2.
• Ship 20 units from Factory 2 to Store 3.

The minimum total cost is 320.