Chapter 9 Integer Programming Learning Objectives



Download 87.93 Kb.
Date conversion11.10.2016
Size87.93 Kb.
Chapter 9 - Integer Programming Learning Objectives


  1. Understand what an integer program is and how it differs from a linear program.




  1. Understand how to formulate integer programming problems in general and in particular understand:




  1. Understand why, in general, integer programs are more difficult to solve than linear programs.




  1. Be able to solve pure and mixed integer programming problems using the branch-and-bound method.


Integer Programming Overview and Definitions
Defn: Integer Programming (IP) - an LP in which some or all of the variables are required to be non-negative integers.

Specific Problems


Pure IP - all variables are integers.

Mixed IP - some variables are integers.

0-1 IP - all variables must be equal to 0 or 1.

See Example of each.


Defn: LP Relaxation - the LP obtained by omitting all integer or 0-1 constraints on variables.
The feasible region for the IP problem is a subset of the feasible region for the LP relaxation problem.
Hence, the optimal z-value for an LP relaxation will always be equal to or better than the optimal z-value for the original IP.

Ex.


max z = 3x1 + 2x2

st 2x1 + x2  4 (1)

x1 + 3x2  5 (2) x1  0 (3)

x2  0 (4)


Pure IP
Add x1, x2 integer


Feas. region (0,0), (0,1), (1,0), (1,1), (2,0)
Mixed IP
Add x2 integer
Feas. region x2 = 0 and x1  2; x2 = 1 and x1  3/2
0-1 IP
Add x1, x2 = 0 or 1
Feas. region (0,0), (0,1), (1,0), (1,1)

The Difficulty of Solving IPs

IP’s are generally harder to solve than LP’s due to the integer restriction.


Unfortunately, we can not take the optimal LP solution and round it off to find the optimal IP solution.
Ex.

Max z = 4x1 + 5x2

s.t. 2x1 + x2  5 (1)

2x1 + 3x2  5 (2)

x1  0 (3)

x2  0 (4)

The LP optimum is (2.5, 0) with z = 10.

If we round up we get (3,0) which is infeasible.

If we round down we get (2,0) which has z = 8. Is this optimal for the IP?
Suppose we require x1 and x2 to be integer.

The feasible region becomes: (0,0), (0,1), (1,0), (1,1), (2,0)

The IP optimum is (1,1) with z = 9.

Formulating an IP Problem
Review examples 1 - 6 in our book in detail and skim examples 7 and 8 and the discussion of piecewise linear functions.
Ex. Section 9.2, Problem 20
Steps 2,3


State

A

B

C

D

E

F

G

Adja-cent

State

B C

A C D E

A B D

B C E F G

B D F

D E G

D F


Step 4

Step 5

Step 6

Step 7
Ex. Section 9.2, Problem 1
Step 2
Step 3 - See table.
Step 4


Step 5


Step 6
Step 7

Special types of constraints 1) If - Then constraints
If a constraint f(x1, x2, .... xn) > 0 is satisfied then the constraint g(x1, x2, .....xn)  0 must be satisfied. However if f(x1, x2, .... xn) > 0 is not satisfied then the constraint g(x1, x2, .....xn)  0 may or may not be satisfied.
Example:

Basketball example - if player 1 starts then players 4 and 5 must also start.


In general we model it this way:
-g(x1, x2, .....xn)  M*y

f(x1, x2, .... xn)  M*(1-y)

where y equals 0 or 1.
Observe that the only way f(x1, x2, .... xn) > 0 can be true is if y = 0. This forces -g(x1, x2, .....xn)  0 or g(x1, x2, .....xn)  0 which is what we want.
Also note that if f(x1, x2, .... xn)  0 then y can equal 1 and -g(x1, x2, .....xn)  M*y = M is always satisfied.

Example
f(x1, x2, .... xn) > 0

Looks like x1 > 0

g(x1, x2, .....xn)

Looks like x4 + x5 = 2 or x4 + x5 - 2  0
Thus we add the constraints:
x1  M*(1-y)

-(x4 + x5 - 2)  M*y


y = 0, 1
Check that x1 > 0 implies x4 + x5 = 2.

If x1 = 0, then x4 and x5 can take on any value.

Example

Special types of constraints 2) Either - Or

Either one condition is met or the other condition must be met. Either the constraint f(x1, x2, .... xn)  0 is satisfied or the constraint g(x1, x2, .....xn)  0 must be satisfied.

However, it is okay to satisfy both of them.
Example:

Basketball example - either player 2 or 3 must start.


In general we model it this way:
f(x1, x2, .... xn)  M*y
g(x1, x2, .....xn)  M*(1-y)
If y = 0 then f(x1, x2, .... xn)  0 is enforced and

g(x1, x2, .....xn)  M*(1-y) = M is a loose constraint.


If y = 1 then g(x1, x2, .... xn)  0 is enforced and

f(x1, x2, .....xn)  M*y = M is a loose constraint.



Example


f(x1, x2, .... xn)  0

Looks like x2  1 or 1 - x2  0

g(x1, x2, .....xn)  0

Looks like x3  1 or 1 - x3  0
Thus we add the constraints:
1 - x2  M*y

1 - x3  M*(1-y)


y = 0, 1
Check that if y = 0 this forces x2 to equal 1, and x3 can take on any value. If y = 1 then x3 must equal 1 and x2 can take on any value.
Second example:
Consider a problem with a finite amount of labor available - say 40 hours per week but permit overtime. However, if overtime occurs it must be at least 4 hours.
So either OT = 0 or OT  4.
Thus,

f(x1, x2, .... xn)  0

Looks like OT  0

g(x1, x2, .....xn)  0

Looks like OT  4 or 4 - OT  0
Thus we add the constraints:
OT  M*y

4 - OT  M*(1-y)


y = 0, 1
Check that if y = 0 this forces OT to equal 0, and 4 - OT is less than M. If y = 1 then 4 - OT  0 (thus OT  4) and OT  M is satisfied.

The Knapsack Problem
You are going on a trip and can take a bag that can at most contain W lbs. of items. You have n items to consider taking with you. Each item i has a different weight, wi and value, vi. How do you maximize the value of the items that you take on the trip?

Example


Ex. Problem 2, p. 518-9.
Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

What constraint would I add if I must
a) Must have either the TV or the stereo or both?

b) Either both the TV and stereo or neither one?



Fixed Charge Problem
General idea.
Ex: Two machine production problem with purchase costs. There is a fixed charge for buying the machine - whether we make 1 or 1000 parts on it.
Model the fixed charge with a variable that equals 0 or 1.

Consider Problem 17, p. 494.


Step 2

Step 3


Step 4

Step 5


Step 6

Step 7


In Class Example Problem 19, p. 494.
Step 2

Step 3

Step 4

Step 5


Step 6

Step 7


Branch-and-Bound Method Overview

Using the Branch-and-Bound Method to Solve a Pure IP Problem

Step 1 Solve the LP Relaxation Problem. For a Max. problem the z-value to this problem is called the Upper Bound (UB).

Step 2 Divide the feasible region into subsets and iteratively search for the optimal solution to the IP Problem.

Step 3 Use the Last In First Out (LIFO) method of search to select the next region to examine.
Note:
(1) It is unnecessary to branch on a subproblem if it is fathomed. It is fathomed if:

(a) It is infeasible.

(b) The subproblem obtains an optimal solution in which all variables are integers.

(c) The optimal z-value for the subproblem is worse than the current Lower Bound (LB).

(2) A subproblem may be eliminated from consideration if

(a) It is infeasible.

(b) If the z-value for the subproblem is less than the LB.
Ex. Section 9.3, Problem 4
Max z = 4x1 + 3x2

st 4x1 + 9x2  26 (1)

8x1 + 5x2  17 (2)

x1  0 (3)

x2  0 (4)

x1, x2 are integer

SP 1
z = 128/13

x1 = 23/52

x2 = 35/13
SP 1
z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

SP 1
z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z =

x1 =

x2 =

X

SP 1
z = 128/13



x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X

SP 1
z = 128/13



x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z =

x1 = 2 x1 =

x2 = 1/5 x2 =

SP 1
z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z =

x1 = 2 x1 =

x2 = 1/5 x2 =

x2  1 x2  0

SP 8 SP 9


infeasible z =

x1 =

x2 =

X

SP 1


z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z =

x1 = 2 x1 =

x2 = 1/5 x2 =

x2  1 x2  0

SP 8 SP 9


infeasible z = 17/2

x1 = 17/8

x2 = 0

X

SP 1



z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z =

x1 = 2 x1 =

x2 = 1/5 x2 =

x2  1 x2  0

SP 8 SP 9


infeasible z = 17/2

x1 = 17/8



x2 = 0

X x1  3 x1  2

SP 10 SP 11


infeasible z =

x1 =

x2 =

SP 1


z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z =

x1 = 2 x1 =

x2 = 1/5 x2 =

x2  1 x2  0

SP 8 SP 9


infeasible z = 17/2

x1 = 17/8



x2 = 0

X x1  3 x1  2

SP 10 SP 11


infeasible z = 8

x1 = 2

x2 = 0 LB = 8

SP 1


z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z =

x1 = 1 x1 =

x2 = 9/5 x2 =

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z = 7

x1 = 2 x1 = 1

x2 = 1/5 x2 = 1

x2  1 x2  0 LB = 8

SP 8 SP 9 X Can’t beat z = 8 at SP 11


infeasible z = 17/2

x1 = 17/8



x2 = 0

X x1  3 x1  2

SP 10 SP 11


infeasible z = 8

x1 = 2

x2 = 0 LB = 8

SP 1


z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z = 26/3

x1 = 1 x1 = 0

x2 = 9/5 x2 = 26/9

x2  2 x2  1

SP 4 SP5



infeasible z = 9

x1 = 3/2

x2 = 1

X x1  2 x1  1

SP 6 SP 7


z = 43/5 z = 7

x1 = 2 x1 = 1

x2 = 1/5 x2 = 1

x2  1 x2  0 LB = 8

SP 8 SP 9 X Can’t beat z = 8 at SP 11


infeasible z = 17/2

x1 = 17/8



x2 = 0

X x1  3 x1  2

SP 10 SP 11


infeasible z = 8

x1 = 2

x2 = 0 LB = 8

SP 1


z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z = 26/3

x1 = 1 x1 = 0

x2 = 9/5 x2 = 26/9

x2  2 x2  1 x2  3 x2  2

SP 4 SP5 SP 12 SP 13


infeasible z = 9 infeasible z =

x1 = 3/2 x1 =

x2 = 1 x2 =

X x1  2 x1  1 X

SP 6 SP 7


z = 43/5 z = 7

x1 = 2 x1 = 1

x2 = 1/5 x2 = 1

x2  1 x2  0 LB = 8

SP 8 SP 9 X Can’t beat z = 8 at SP 11


infeasible z = 17/2

x1 = 17/8



x2 = 0

X x1  3 x1  2

SP 10 SP 11


infeasible z = 8

x1 = 2

x2 = 0 LB = 8

SP 1


z = 128/13

x1  1 x1 = 23/52 x1  0

x2 = 35/13


SP 2 SP 3

z = 47/5 z = 26/3

x1 = 1 x1 = 0

x2 = 9/5 x2 = 26/9

x2  2 x2  1 x2  3 x2  2

SP 4 SP5 SP 12 SP 13


infeasible z = 9 infeasible z = 6

x1 = 3/2 x1 = 0

x2 = 1 x2 = 2

X x1  2 x1  1 X LB = 8

SP 6 SP 7 X

Can’t beat

z = 43/5 z = 7 z = 8 at SP 11

x1 = 2 x1 = 1

x2 = 1/5 x2 = 1

x2  1 x2  0 LB = 8

SP 8 SP 9 X Can’t beat z = 8 at SP 11


infeasible z = 17/2

x1 = 17/8



x2 = 0

X x1  3 x1  2

SP 10 SP 11


infeasible z = 8

x1 = 2

x2 = 0 LB = 8

Using the Branch-and-Bound Method for Solving Mixed IP Problems
Use the same method as discussed previously except, only branch on the variables which must be integer.

Ex. Section 9.4, Problem 1


max z = 3x1 + x2

st 5x1 + 2x2  10

4x1 + x2  7

x1, x2  0; x2, integer

Solving the LP relaxation yields,

z = 17/3


x1 = 4/3

x2 = 5/3


x1 is okay, but x2 must be an integer

SP 1
z = 17/3

x1 = 4/3

x2 = 5/3


SP 1
z = 17/3

x2  1 x1 = 4/3 x2  2

x2 = 5/3


SP 2 SP 3

z = 5.5 z =

x1 = 1.5 x1 =

x2 = 1 x2 =

Candidate Solution

SP 1
z = 17/3



x2  1 x1 = 4/3 x2  2

x2 = 5/3


SP 2 SP 3

z = 5.5 z = 5.6

x1 = 1.5 x1 = 1.2

x2 = 1 x2 = 2

Candidate Solution LB = 5.5
The optimal solution is z = 5.6, x1 = 1.2, and x2 = 2.

To Solve an IP Using LINDO


1. Type in the problem in the same format as if it were an LP.
2. After the END command indicate which variables are integer restricted.
 For 0-1 variables type in the line
INTE Var. Name
Ex. INTE x
 For variables that can assume the values

0, 1, 2, .... type in the line


GIN Var. Name
Ex. GIN y
3. Using the DOS version of LINDO, to solve the problem use the GO command followed by the SOLU command. In the Windows version of LINDO just use the solution option.

Unfortunately, sensitivity analysis cannot be performed for IP’s in the same way that it is for LPs.



Chap 9 -


The database is protected by copyright ©ininet.org 2016
send message

    Main page