4 Integer Programming



Download 299.78 Kb.
Page1/4
Date11.10.2016
Size299.78 Kb.
#8
  1   2   3   4

4 Integer Programming



Natural occurrences of integer variables (e.g., the number of buses allocated to a route, the number of boxes of hardwood flooring purchased, etc. But also: logical variables.
1950s: Gomory’s cutting plane techniques

Early 1960s: Land & Doig’s Branch-&-Bound method.
4.1 Basic concepts.
P1: Max z = x1 + x2

s.t. 3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10

x1, x2 ≥ 0.
In addition, some or all variables must be integers. These are additional requirements.
MILP: mixed-integer linear programming problems

AILP: all-integer linear programming problems.

(a) (b)

(c) (d)
Simple rounding will not do!
Example:
Max z = 2x1 + x2

s.t. 7x1 + 48x2 ≤ 84

x1 + 12x2 ≥ 3

x1, x2 ≥ 0 and integer.


Optimal solution of LP relaxation:
= (6.5455, 0.7955) with = 13.8864,
while the optimal all-integer solution is
= (5, 1) with = 11.
No rounding can achieve this.
Change b2 from “3” to “13,” (broken line) the AILP has no feasible solution.
On the other hand, some types of problems have integer solutions naturally.
x1 + x2 ≤ 10

5x1 + 3x2 ≥ 15

x1 ≤ 6

x2 ≤ 7

x1, x2 ≥ 0.

Extreme points (3, 0), (6, 0), (6, 4), (3, 7), (0, 7), & (0, 5).
Ignoring the integrality conditions & solving the LP relaxation will result in an integer solution. Some large classes of problems fall into this category.
: Optimal objective value of the integer problem,

: optimal objective value of the LP relaxation. Then
≤ .
Absolute integrality gap ,
relative integrality gap .
Earlier example: = (6.5455, 0.7955) with = 13.8864, & = (5, 1) with = 11.
Then: absolute integrality gap 13.8864  11 = 2.8864,

relative integrality gap is 2.8864/13.8864 = .2079.
Indicator of difficulty: relative integrality gap > 0.1: difficult, if > 0.5: very difficult. This is, of course, only known after the fact.
Another type of relaxation is the Lagrangean relaxation PLagr. First, choose some or all of the given structural constraints (the dualized constraints), multiply them by some preselected nonnegative constants (Lagrangean multipliers or dual variables) and subtract them from the objective function. Then the dualized constraints are removed from the set of constraints.
Example: Refer to problem P4 and set up its Lagrangean relaxation by dualizing the first constraint, using the Lagrangean multiplier u1 = 2. The relaxed problem is
Max = 10x1 + 10x2 – 2(3x1 + 5x2 – 15)

s.t. 5x1 + 2x2 ≤ 10

x1, x2 ≥ 0 and integer.
Optimal solution: , with .
Alternatively, if we dualize the second constraint with, say, a Lagrangean multiplier of u2 = 3, a different relaxed problem results:
Max = 10x1 + 10x2 – 3(5x1 + 2x2 – 10)

s.t. 3x1 + 5x2 ≤ 15

x1, x2 ≥ 0 and integer,
which has an optimal solution of , with .
We could also dualize both constraints. The objective function is then Max 10x1 + 10x2 – u1(3x1 + 5x2 – 15) – u2(5x1 + 2x2 – 10) subject to only the nonnegativity constraints and the integrality requirements.
For multipliers u1 = 2 and u2 =1, the objective function reduces to Max zLagr = –x1 – 2x2 + 40, with an optimal solution , and = 40. Choosing instead multipliers u1 = 1 and u2 = 2 results in an objective function Max zLagr = –3x1 + x2 + 35, which has unbounded “optimal” solutions (x2 can be chosen arbitrarily large).
The optimal objective value is greater than or equal to the value of the objective function of the original (maximization) problem. The choice of Lagrangean multipliers determines how close the gap between and will be. In the context of linear programming, selecting Lagrangean multipliers equal to optimal values of the dual variables, the inequality is actually satisfied as an equation. This idea is used in a heuristic method in Section 4.3.3.
Integer variables either occur naturally or due to the way we must formulate constraints. For instance, logical variables are zero-one variables introduced to model logical implications. In standard linear programming, all constraints must hold.
However, if we have the choice of one of a number of different machines, each with its own capacity, the actual capacity constraint is not given by all machines, but only by the machine that is chosen. We speak of an either-or constraint. Another class is that of conditional constraints. They can be spotted by the wording “if this, then that.”
Formulate logical constraints by using a table. For two zero-one variables y1 and y2, there are four solutions:


#

y1

y2

1

0

0

2a

0

1

2b

1

0

3

1

1


The table below shows the exclusion constraints that allow excluding one specific solution without affecting any of the others.


Solution to be excluded

Formulation

Wording

1

y1 + y2 ≥ 1

“At least one of the two activities needs to be chosen”

2a

y1 ≥ y2

“If activity y2 is chosen, then activity y1 must also be chosen”

2b

y1 ≤ y2

“If activity y1 is chosen, then activity y2 must also be chosen”

3

y1 + y2 ≤ 1

“At most one of the activities can be chosen”



The table below shows all 8 solutions for 3 variables


#

y1

y2

y3

1

0

0

0

2a

0

0

1

2b

0

1

0

2c

1

0

0

3a

0

1

1

3b

1

0

1

3c

1

1

0

4

1

1

1


The table blow shows how each individual solution can be excluded.


Sln to be excluded

Formulation

Wording

1

y1 + y2 + y3 ≥ 1

“At least one of the three activities must be chosen”

2a

y1 + y2 ≥ y3

“If neither y1 nor y2 are chosen, then y3 must be chosen”

2b

y1 + y3 ≥ y2

“If neither y1 nor y3 are chosen, then y2 must be chosen”

2c

y2 + y3 ≥ y1

“If neither y2 nor y3 are chosen, then y1 must be chosen”

3a

–y1 + y2 + y3 ≤ 1

“If y1 is not chosen, then y2 and y3 must both be chosen”

3b

y1 – y2 + y3 ≤ 1

“If y2 is not chosen, then y1 and y3 must both be chosen”

3c

y1 + y2 – y3 ≤ 1

“If y3 is not chosen, then y1 and y2 must both be chosen”

4

y1 + y2 + y3 ≤ 2

“No more than two of the three activities can be chosen”


If more than a single solution is excluded, we combine the pertinent logical constraints. For example, two variables, excluding #1 and #2a is achieved by the constraints y1 + y2 ≥ 1 and y1 ≥ y2 which can be collapsed into the single constraint y1 = 1. Then replace y1 by the value of 1 everywhere to reduce the size of the model.
Another logical constraint may require an activity y0 to be chosen only if at least k activities in a set J = {y1, y2, …, yn} are also chosen. This can be formulated as
.
4.2 Applications of Integer Programming
Knapsack problems
Define variables yj = 1, if the item is included, & 0 otherwise.
Alternatively, yj: the number of items of type j that are included, so that yj ≥ 0 and integer.
Cargo loading, capital budgeting.





Highrise

Shopping mall

Amusement park

Warehouses

Airport

Profit contribution (in m$)


10


6


12


2


7

Resource consumption

4

2

5

1

3


Seven resource units are available.
P: Max z = 10y1 + 6y2 + 12y3 + 2y4 + 7y5

s.t. 4y1 + 2y2 + 5y3 + 1y4 + 3y5  7

y1, y2, y3, y4, y5 = 0 or 1.
The LP relaxation has the optimal solution = 3.5, with the objective value .
Optimal integer solution: , with objective value = 18.
Even for simple problems, enumeration does not work! n: number of variables, # slns = the number of 0-1 solutions (feasible or not).



n

1

2

3

4

40

# slns

21=1

22=4

23=8

24=16

240 ≈ 1 trillion


A computer that examines 1 quadrillion solutions per second requires > 40 million years for a problem with n = 100 variables.
4.2.1 Cutting Stock Problems (Trim Loss

Problems)
Given some material, change its shape from whatever shape exists to whatever shape is needed.
Example: Wooden rods in standard profile & width.
Twenty 12 ft rods and twenty-five 10 ft rods are available.
Sixty 8 ft rods, forty 5 ft rods, & seventy-five 3 ft rods are needed.
Cut: 50¢ per cut
Purchase: $2, $1.50, & $1.10 for the 8 ft, 5 ft, and 3 ft lengths.

Objective: Minimize waste (nonlinear! short pieces are waste, long unused pieces may be used later) or minimize cost.
Cutting plan:


Download 299.78 Kb.

Share with your friends:
  1   2   3   4



The database is protected by copyright ©ininet.org 2024
send message
    Main page
objective function