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. P_{1}: Max z = x_{1} + x_{2}

s.t. 3x_{1} + 5x_{2} ≤ 15

5x_{1} + 2x_{2} ≤ 10

x_{1}, x_{2} ≥ 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 = 2x_{1} + x_{2}

s.t. 7x_{1} + 48x_{2} ≤ 84

x_{1} + 12x_{2} ≥ 3

x_{1}, x_{2} ≥ 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 b_{2} from “3” to “13,” (broken line) the AILP has no feasible solution. On the other hand, some types of problems have integer solutions naturally. x_{1} + x_{2} ≤ 10

5x_{1} + 3x_{2} ≥ 15

x_{1} ≤ 6

x_{2} ≤ 7

x_{1}, x_{2} ≥ 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 P_{Lagr}. 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 P_{4} and set up its Lagrangean relaxation by dualizing the first constraint, using the Lagrangean multiplier u_{1} = 2. The relaxed problem is Max = 10x_{1} + 10x_{2} – 2(3x_{1} + 5x_{2} – 15)

s.t. 5x_{1} + 2x_{2} ≤ 10

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

s.t. 3x_{1} + 5x_{2} ≤ 15

x_{1}, x_{2} ≥ 0 and integer, which has an optimal solution of , with . We could also dualize both constraints. The objective function is then Max 10x_{1} + 10x_{2} – u_{1}(3x_{1} + 5x_{2} – 15) – u_{2}(5x_{1} + 2x_{2} – 10) subject to only the nonnegativity constraints and the integrality requirements. For multipliers u_{1} = 2 and u_{2} =1, the objective function reduces to Max z_{Lagr} = –x_{1} – 2x_{2} + 40, with an optimal solution , and = 40. Choosing instead multipliers u_{1} = 1 and u_{2} = 2 results in an objective function Max z_{Lagr} = –3x_{1} + x_{2} + 35, which has unbounded “optimal” solutions (x_{2} 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 y_{1} and y_{2}, there are four solutions:

#

y_{1}

y_{2}

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

y_{1} + y_{2} ≥ 1

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

2a

y_{1} ≥ y_{2}

“If activity y_{2} is chosen, then activity y_{1} must also be chosen”

2b

y_{1} ≤ y_{2}

“If activity y_{1} is chosen, then activity y_{2} must also be chosen”

3

y_{1} + y_{2} ≤ 1

“At most one of the activities can be chosen”

The table below shows all 8 solutions for 3 variables

#

y_{1}

y_{2}

y_{3}

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

y_{1} + y_{2} + y_{3} ≥ 1

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

2a

y_{1} + y_{2} ≥ y_{3}

“If neither y_{1} nor y_{2}are chosen, then y_{3} must be chosen”

2b

y_{1} + y_{3} ≥ y_{2}

“If neither y_{1} nor y_{3} are chosen, then y_{2} must be chosen”

2c

y_{2} + y_{3} ≥ y_{1}

“If neither y_{2} nor y_{3} are chosen, then y_{1} must be chosen”

3a

–y_{1} + y_{2} + y_{3} ≤ 1

“If y_{1}is not chosen, then y_{2} and y_{3} must both be chosen”

3b

y_{1} – y_{2} + y_{3} ≤ 1

“If y_{2} is not chosen, then y_{1} and y_{3} must both be chosen”

3c

y_{1} + y_{2} – y_{3} ≤ 1

“If y_{3} is not chosen, then y_{1} and y_{2} must both be chosen”

4

y_{1} + y_{2} + y_{3} ≤ 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 y_{1} + y_{2} ≥ 1 and y_{1} ≥ y_{2} which can be collapsed into the single constraint y_{1} = 1. Then replace y_{1} by the value of 1 everywhere to reduce the size of the model. Another logical constraint may require an activity y_{0}to be chosen only if at least k activities in a set J = {y_{1}, y_{2}, …, y_{n}} are also chosen. This can be formulated as . 4.2 Applications of Integer Programming Knapsack problems Define variables y_{j} = 1, if the item is included, & 0 otherwise. Alternatively, y_{j}: the number of items of type j that are included, so that y_{j} ≥ 0 and integer. Cargo loading, capital budgeting.

y_{1}, y_{2}, y_{3}, y_{4}, y_{5} = 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

2^{1}=1

2^{2}=4

2^{3}=8

2^{4}=16

2^{40} ≈ 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: