Integer programming (Part - 3) - Electronics and Communication Engineering (ECE) PDF Download

Integer programming - Part - 3, Operations Research

Example 5. Knapsack

Answer
 We compute the ratios:

Using the ratios, LR solution is

x₁ = 1, x₂ = 1, x₃ = 0.5, x₄ = 0, z = 22 We branch on x₃ and get

P1 (LR + x₃=0) sol’n: x₃=0, x₁=x₂=1, x₄=2/3, z=21.67

P2 (LR + x₃=1) sol’n: x₃=x₁=1, x₂=5/7, x₄=0, z=21.85

Choosing sub-problem P2 (the best z–value), we branch on x₂ and get

P3 (P2 + x₂=0) sol’n: x₃=1, x₂=0, x₁=1, x₄=1, z=18

P4 (P2 + x₂=1) sol’n: x₃=x₂=1, x1=3/5, x₄=0, z=21.8

P3 solution is feasible for the original knapsack problem Candidate solution; LB = 18

Choosing sub-problem P4, we branch on x1 and get P5 (P4 + x₁=0) sol’n: x₃=x₂=1, x₁=0, x₄=1, z=21
P6 (P4 + x₁=1) sol’n: Infeasible (x₃=x₂=x₁=1: LHS=16)
P5 solution is feasible for the original knapsack problem New candidate solution; updated LB = 21
The only remaining sub-problem is P1 with solution value 21.67
There is no better solution for this sub-problem than 21. But we already have a solution with value 21.
It is not useful to search for another such solution. We can fathom P1 based on this bounding argument and mark P1 as inactive.

Optimal sol’n and Report

Thus, the optimal solution is
z=21, x₁=0, x₂=1, x₃=1, x₄=1
Items 2, 3, and 4 should be put in the knapsack.
In this case, the total value would be 21.

B&B for Solving Combinatorial Optimization Problems

A combinatorial (discrete) optimization problem is any optimization problem that has a finite number of feasible solutions.
A B&B approach is often an efficient way to solve them.

Examples of combinatorial optimization problems:

• Ten jobs must be processed on a single machine. It is known how long it takes to complete each job and the time at which each job must be completed (the job’s due date). What ordering of the jobs minimizes the total delay of the 10 jobs?
• A salesperson must visit each of the 10 cities before returning to her/his home.

What ordering of the cities minimizes the total distance the salesperson must travel before returning home? (TSP).
In each of these problems, many possible solutions must be considered.

Example 6: Machine Scheduling

 Please refer to Winston 9.6. p. 528

TSP
Please recall that
We define x_ij as a 0-1 variable:
x_ij = 1 if TS goes from city i to city j;
x_ij = 0 otherwise
c_ij = distance form city i to city j (for ij)
c_ii = M (a very large number relative to actual distances)

An itinerary that begins and ends at the same city and visits each city once is called a tour.
It seems reasonable that we might be able to find the answer to TSP by solving an assignment problem having a cost matrix whose ijth is cij.
If the optimal solution to the assignment problem yields a tour, it is the optimal solution to the TSP.
Unfortunately, the optimal solution to the assignment problem need not be a tour (may yield subtours).
If we could exclude all feasible solutions that contain subtours and then solve the assignment problem, we would obtain the optimal solution to TSP Not easy to do...
Several B&B approaches have been developed for solving TSPs.
One approach start with solving the preceding assignment problem (sub-problem

1). Because this sub-problem contains no provisions to prevent subtours, it is a relaxation of the original TSP.
Thus, if the optimal solution to the subp.1 is feasible for the TSP (no subtours), then it is also optimal for the TSP.
If it is infeasible (contain subtours), we branch on the subp.1 in a way that will prevent one of subp.1’s subtours from recurring in solutions to subsequent sub-problems.

Example 7: TSP

(Winston 9.6., p. 530)
Joe State lives in Gary, Indiana and owns insurance agencies in Gary, Fort Wayne, Evansville, Terre Haute, and South Bend.
Each December, he visits each of his insurance agencies.
The distance between each agency:

What order of visiting his agencies will minimize the total distance traveled?

Answer

We first solve the assignment problem (subp.1) applying the Hungarian method to the cost matrix shown:

The optimal solution will be:

x₁₅=x₂₁=x₃₄=x₄₃=x₅₂=1, z=495

The optimal solution to subp.1 contains two subtours:

• recommends going from Gary (1) to South Bend (5), then to Fort Wayne (2), and then back to Gary (1–5–2–1).
• also suggests that if Joe is in Evansville (3), he should go to Terre Haute (4) and

then to Evansville (3–4–3).

Thus, the optimal solution can not be the optimal solution to Joe’s problem.
We arbitrarily choose to exclude the subtour 3-4-3.
Observe that the optimal solution to Joe’s problem must have either x₃₄=0 or x₄₃=0.

Thus, we can branch on subp.1 by creating two new sub-problems.
Subp.2: Subp.1 + (x₃₄=0, or c₃₄=M)
Subp.3: Subp.1 + (x₄₃=0, or c₄₃=M)

Now arbitrarily choose subp.2 to solve.

The optimal solution will be:

x₁₄=x₂₅=x₃₁=x₄₃=x₅₂=1, z=652

This solution includes the subtours 1–4–3–1 and 2–5–2.
Thus, it can not be the optimal solution to Joe’s problem.
Following the LIFO approach, now branch sub-problem 2 in an effort to exclude the subtour 2-5-2. Thus we add two additional sub-problems.

Subp.4: Subp.2 + (x₂₅=0, or c₂₅=M)

Subp.5: Subp.2 + (x₅₂=0, or c₅₂=M)

By using the Hungarian method on subp.4, we obtain the optimal solution x₁₅=x₂₄=x₃₁=x₄₃=x₅₂=1, z=668
This solution contains no subtours and yields the tour 1–5–2–4–3–1
It is a candidate solution and any node that cannot yield a z-value < 668 may be
eliminated from consideration.

We next solve subp.5.

x₁₄=x₄₃=x₃₂=x₂₅=x₅₁=1, z=704

This solution also yields a tour 1–4–3–2–5–1

But z=704 is not as good as the subp.4 candidate’s z=668 Thus this subp.5 may be eliminated from consideration.

Only subp.3 remains.

The optimal solution

x₁₃=x₂₅=x₃₄=x₄₁=x₅₂=1, z =652.

This solution includes the subtours 1–3–4–1 and 2–5–2.
However, it is still possible for this sub-problem to yield a solution with no subtours that beats z=668.
Next branch on sub-problem 3 creating new sub-problems.

Subp.6: Subp.3 + (x₂₅=0, or c25=M)

Subp.7: Subp.3 + (x₅₂=0, or c52=M)

Both of these sub-problems have a z-value that is larger than 668.

Optimal sol’n and Report

Subp.4 thus yields the optimal solution:
x15=x24=x31=x43=x52=1, z=668
Joe should travel from Gary (1) to South Bend (5), from South Bend to Fort Wayne (2), from Fort Wayne to Terre Haute (4), from Terre Haute to Evansville (3), and then back to Gary.
He will travel a total distance of 668 miles.

Heuristics for TSPs

An IP formulation can be used to solve a TSP but can become unwieldy and inefficient for large TSPs.
When using B&B methods to solve TSPs with many cities, large amounts of computer time is needed.
Heuristic methods, or heuristics, can be used to quickly lead to a good (but not necessarily optimal) solution.

Two types of heuristic methods can be used to solve TSP:
1. The Nearest-Neighbor
2. The Cheapest-Insertion

The Nearest-Neighbor Heuristic
1. Begin at any city and then “visit” the nearest city.
2. Then go to the unvisited city closest to the city we have most recently visited.
3. Continue in this fashion until a tour is obtained.
4. After applying this procedure beginning at each city, take the best tour found.

Example 8. Applying the NNH to TSP

We arbitrarily choose to begin at city 1.
Of the cities 2, 3, 4, and 5, city 5 is the closest city to city 1 Generate the arc 1–5 Of the cities 2, 3, and 4, city 2 is the closest city to city 5 1–5–2
Of the cities 3 and 4, city 4 is the closest city to city 2 1–5–2–4
Joe must next visit city 3 and then return to city 1 1–5–2–4–3–1 (668 miles).
In this case, the NNH yields the optimal tour.
If we had begun at city 3, however, NNH yields the tour 3–4–1–5–2–3 (704 miles).
Thus, the NNH need not yield an optimal tour.
This procedure should be applied beginning at each city, and then the best tour found should be taken as solution.

The Cheapest-Insertion Heuristic

1. Begin at any city and find its closest neighbor.
2. Then create a subtour joining those two cities.
3. Next, replace an arc in the subtour (say, arc (i, j)) by the combinations of two arcs (i, k) and (k, j), where k is not in the current subtour that will increase the length of the subtour by the smallest (or cheapest) amount.
4. Continue with this procedure until a tour is obtained.
5. After applying this procedure beginning with each city, we take the best tour found.

Example 9. Applying the CIH to TSP

We arbitrarily choose to begin at city 1.
Of the cities 2, 3, 4, and 5, city 5 is the closest city to city 1 Generate the arc 1–5 We create a subtour (1, 5)–(5, 1)
We could replace arc (1, 5) by (1, 2)–(2, 5), (1, 3)–(3, 5), or (1, 4)–(4, 5)
We could also replace (5, 1) by (5, 2)–(2, 1), (5, 3)–(3, 1), or (5, 4)–(4, 1)
The computations used to determine which arc of (1, 5)–(5, 1) should be replaced are given in the Table:

* indicates the correct replacement: either (1, 5) or (5, 1)
We arbitrarily choose to replace arc (1, 5) by arcs (1, 2) and (2, 5) New subtour:
(1, 2)–(2, 5)–(5, 1)
We then determine which arc should be replaced

We now replace arc (1, 2) by arcs (1, 4) and (4, 2) New subtour: (1, 4)–(4, 2)–(2, 5)–(5, 1)
Which arc should be replaced?

We now replace arc (1, 4) by arcs (1, 3) and (3, 4)
This yields the tour (1, 3)–(3, 4)–(4, 2)–(2, 5)–(5, 1)
In this case, the CIH yields the optimal tour.
But, in general, the CIH does not necessarily do so.
This procedure should be applied beginning at each city, and then the best tour found should be taken as solution.

Evaluation of Heuristics

• Performance guarantees

Gives a worse-case bound on how far away from optimality a tour constructed by the heuristic can be

• Probabilistic analysis

A heuristic is evaluated by assuming that the location of cities follows some known probability distribution

• Empirical analysis 

Heuristics are compared to the optimal solution for a number of problems for which the optimal tour is known

5.2.5 Cutting Planes

A linear inequality is a valid inequality for a given IP problem if it holds for all integer feasible solutions to the model. Relaxations can often be strengthened dramatically by including valid inequalities that are not needed by a correct discrete model. To strengthen a relaxation, a valid inequality must cut off (render infeasible) some feasible solutions to current LR that are not feasible in the IP model.

This need to cut off noninteger relaxation solutions is why valid inequalities are sometimes called cutting planes.
 

Cut Classification

• General purpose
  A fractional extreme point can always be separated (LP-based approach, that works for IP)
  •  Disjunctive cuts
  •  Gomory cutting planes
     
• Problem specific

Derived from problem structure, generally facets. (Capital Budgeting (Knapsack), Set Packing... )

Cutting Plane Algorithm (Gomory cut)

Find the optimal tableau for the IP’s LR.
If all variables in the optimal solution assume integer values, we have found an optimal solution! Otherwise proceed to next step
Pick a constraint in the optimal tableau whose RHS has the fractional part closest to ½.
For the constraint identified, put all of the integer parts on the left side (round down),
and all the fractional parts on the right

Generate the cut as:
“RHS of the modified constraint” < 0

Use the dual simplex to find the optimal solution to the LR, with the cut as an additional constraint.

• If all variables assume integer values in the optimal solution, we have found an optimal solution to the IP.
• Otherwise, pick the constraint with the most fractional right-hand side and use it to

generate another cut, which is added to the tableau.

We continue this process until we obtain a solution in which all variables are integers.
This will be an optimal solution to the IP.

Dual Simplex Method
 Please recall that at dual simplex:

•  We choose the most negative RHS.
•  BV of this pivot row leaves the basis.
•  For the variables that have a negative coefficient in the pivot row, we calculate the ratios (coefficient in R0 / coefficient in pivot row).
•  Variable with the smallest ratio (absolute value) enters basis.

Example 10. Telfa Co.
 (Winston 9.8., p. 546)

Answer

If we ignore integrality, we get the following optimal tableau:

Let's choose the constraint whose RHS has the fractional part closest to ½ (Arbitrarily choose the second constraint):

x₁ – 1.25 s₁ + 0.25 s₂ =3.75

We can manipulate this to put all of the integer parts on the left side (round down), and all the fractional parts on the right to get:

x₁ – 2 s₁ + 0 s₂ – 3 = 0.75 – 0.75 s₁ – 0.25 s₂

Now, note that the LHS consists only of integers, so the right hand side must add up to an integer. It consists of some positive fraction minus a series of positive values. Therefore, the right hand side cannot be a positive value. Therefore, we have derived the following constraint:

0.75 – 0.75 s₁ – 0.25 s₂ ≤ 0

This constraint is satisfied by every feasible integer solution to our original problem. But, in our current solution, s1 and s2 both equal 0, which is infeasible to the above constraint. This means the above constraint is a cut, called the Gomory cut after its discoverer.
We can now add this constraint to the linear program and be guaranteed to find a different solution, one that might be integer.

The dual simplex ratio test indicates that s1 should enter the basis instead of s3.

The optimal solution is an IP solution:
z = 40, x₁ = 5, x₂ = 0

Example 11. Supplementary Problem

Answer

Optimal tableau for LR

Choose the second constraint

x₂ + 0.2 e₁ – 0.6 e₂ = 1.6

Manipulate this:

x₂ – e₂ – 1 = 0.6 – 0.2 e₁ – 0.4 e₂

Cut:

0.6 – 0.2 e₁ – 0.4 e₂ ≤ 0

New LP tableau

The dual simplex ratio test indicates that e1 should enter the basis instead of s3.
The optimal solution is an IP solution:
z = 20, x₁ = 2, x₂ = 1