Integer Programming

In many problems the decision variables must have

integer values.
Example: assign people, machines, and vehicles to
activities in integer quantities.

INTEGER PROGRAMMING

If this is the only deviation from linear programming, it

is called an integer programming (IP) problem.

If only some variables are required to be integer, the
model is called a mixed integer programming (MIP)
San Francisco Police Dep. problem is an IP problem.
Wyndor Glass Co. problem could be an IP problem; how?
Joo Miguel da Costa Sousa / Alexandra Moutinho

Integer Programming

Prototype example

In integer programming divisibility assumption must

be dropped.

Another area of application relates to problems
involving yes-or-no decisions, which have binary
variables.

These IP problems are called binary integer
programming (BIP) problems.

A small example of a typical BIP problem is given in
the following.
Joo Miguel da Costa Sousa / Alexandra Moutinho

287

California Manufacturing Company is considering expansion,

building a factory in Los Angeles, San Francisco or in both
cities.

One new warehouse can also be considered in a city where a
new factory is being built. Maximum $10 million to invest.
Decision
number

Net present
value

Capital
required

Build factory in Los Angeles?

x1

$9 million

Build factory in San Francisco?

x2

$5 million

$3 million

Build warehouse in Los Angeles?

x3

$6 million

$5 million

Build warehouse in San Francisco?

x4

$4 million

$2 million

Joo Miguel da Costa Sousa / Alexandra Moutinho

$6 million

288

Groups of yes-or-no decision often constitute groups

of mutually exclusive alternatives: only one decision
in the group can be yes.

Occasionally, decisions of the yes-or-no type are
contingent decisions: decision that depend upon
previous ones.
 Software options for solving BIP, IP or MIP models:

1 if decision j is yes,
xj =
j = 1,2,3,4
0 if decision j is no,

Z = total net present value of these decisions.
Maximize Z = 9x1 + 5x2 + 6x3 + 4x4.

Constraints:
6x1 + 3x2 + 5x3 + 2x4 10
Mutually exclusive alternatives
Contingent decisions

xj is binary, for j = 1,2,3,4.

Joo Miguel da Costa Sousa / Alexandra Moutinho

Decision
variable

BIP models

All decision variables have the binary form:

x3 x1 and x4 x2

Yes-or-no question

BIP model

x3 + x4 1

286

289






Excel
MatLab
LINGO/LINDO
MPL/CPLEX

Joo Miguel da Costa Sousa / Alexandra Moutinho

290

BIP applications

Formulation examples

Investment analysis, such as the California Man. Co.

Site selection, of factories, warehouses, etc.

Designing a production and distribution network, or
more generally the entire global supply-chain.

Dispatching shipments, scheduling routes, vehicles
and time period for departure and arrivals.

Airline applications, as e.g. fleet assignment and crew
scheduling.

Scheduling interrelated activities, asset divestures, etc.
Joo Miguel da Costa Sousa / Alexandra Moutinho

291

Example 1

Example 1: making choices when decision variables

are continuous. R&D Division of Good Products Co.
has developed three possible new products.
 Requirement 1: from the three, at most two can be chosen
to be produced.

Each product can be produced in either of two plants.

However, management has imposed another
restriction:
 Requirement 2: just one of the two plants can be chosen as
the producer of the new products.
Joo Miguel da Costa Sousa / Alexandra Moutinho

Formulation of the problem

Production time used
for each unit produced

Similar to a standard product mix problem, such as the Wyndor

Glass Co. if we drop the two restrictions and require each
product to use production hours in both plants.

Let x1, x2, x3 be the production rates of the respective products:
Maximize Z = 5 x 1 + 7 x2 + 3 x 3
subject to 3 x1 + 4 x2 + 2 x 3 30

Production
time available
per week

Product 1

Product 2

Product 3

Plant 1

3 hours

4 hours

2 hours

30 hours

Plant 2

4 hours

6 hours

2 hours

40 hours

Unit profit

(103 $)

Sales
potential

(units per
week)

4 x1 + 6 x2 + 2 x 3 40
x1 7

Objectives: choose the products, the plant and the

production rates of the chosen products to maximize
total profit.
Joo Miguel da Costa Sousa / Alexandra Moutinho

293

Formulation of the problem

Number of strictly positive variables (x1, x2, x3) must be 2
 This must be converted to an IP problem. It needs the
introduction of auxiliary binary variables.

x3 9
x 1 , x2 , x 3 0
Joo Miguel da Costa Sousa / Alexandra Moutinho

294

For requirement 1, three auxiliary binary variables (y1, y2, y3) are
introduced:
if x j > 0 can hold (can produce product j )
1
yj =
0
if x j = 0 must hold (cannot produce product j )

This is introduced in the model with the help of an extremely

large positive number M, adding the constraints:
x 1 My1
x2 My 2
x 3 My 3

Restriction 2 requires replacing the first two

functional constraints by:

Either 3 x 1 + 4 x 2 + 2x 3 30
4 x 1 + 6 x 2 + 2 x 3 40

must hold. This again requires an auxiliary binary

variable.
Joo Miguel da Costa Sousa / Alexandra Moutinho

x2 5

Auxiliary binary variables

For the real problem, restriction 1 add the constraint:

or

292

y1 + y2 + y 3 2
y j is binary, for j = 1,2,3.
295

Joo Miguel da Costa Sousa / Alexandra Moutinho

296

Auxiliary binary variables

Complete model (MIP)

Maximize

For requirement 2, another auxiliary binary variable y4 is

introduced:
1
y4 =
0

Z = 5x1 + 7 x2 + 3 x 3
x1 7

subject to

x2 5

if 4x1 + 6 x2 + 2 x 3 40 must hold (choose Plant 2)

x3 9

if 3x1 + 4 x2 + 2 x 3 30 must hold (choose Plant 1)

x 1 My 1 0
x2 My 2 0

This adds the constraints:

x 3 My 3 0

3 x 1 + 4 x 2 + 2 x 3 30 + My 4

y 1 + y2 + y 3 2

4 x 1 + 6 x 2 + 2 x 3 40 + M (1 y 4 )

3 x 1 + 4 x 2 + 2 x 3 My 4 30

y 4 is binary

4 x 1 + 6 x 2 + 2 x 3 + My 4 40 + M
and

x i 0, for i = 1,2,3
y j is binary, for j = 1,2,3,4

Joo Miguel da Costa Sousa / Alexandra Moutinho

297

Solution

Joo Miguel da Costa Sousa / Alexandra Moutinho

298

Example: Southwestern Airways

MIP problem with 3 continuous and four binary

variables.

Optimal solution: y1 = 1, y2 = 0, y3 = 1, y4 = 1, x1 = 5.5, x2
= 0, x3 = 9.

That is, choose products 1 and 3 to produce, choose
Plant 2 for production, choose production rates of 5.5
units per week for product 1 and 9 units per week for
product 2.

Resulting total profit is $54,500 per week.
Joo Miguel da Costa Sousa / Alexandra Moutinho

299

Data for Southwestern Airways

Southwestern Airways needs to assign three crews to

cover all the upcoming flights.

Table shows the flights in the first column.
 Other 12 columns show the 12 feasible sequences of flights
for a crew.
 Numbers in each column indicate the order of the flights.
 Exactly three sequences must be chosen (one per crew).
 More than one crew can be assigned to a flight, but it must
be paid as if it was working.
 Last row shows the cost of assigning a crew to a particular
sequence of flights.
Joo Miguel da Costa Sousa / Alexandra Moutinho

300

Formulation of the problem

Feasible sequence of flights

Flight

1. San Francisco to Los Angeles

2. San Francisco to Denver

1
1

3. San Francisco to Seattle

9. Denver to Chicago

Joo Miguel da Costa Sousa / Alexandra Moutinho

2
4

2
3

Objective: minimize the total cost for the three crews

covering all flights.

12 feasible sequences of flights: 12 yes-or-no
decisions:
Should sequence j be assigned to a crew?

The 12 binary variables to represent the decisions are:

11. Seattle to Los Angeles

1
2

10. Seattle to San Francisco

12

1
3

3
3

11

3
3

10

7. Chicago to Seattle

8. Denver to San Francisco

1
2

6. Chicago to Denver

Cost (1000)

7
1

4. Los Angeles to Chicago

5. Los Angeles to San Francisco

2
5
2

9
301

1
xj =
0

if sequence j is assigned to a crew

otherwise

Joo Miguel da Costa Sousa / Alexandra Moutinho

302

Formulation of the problem

Solution

Minimize Z = 2 x 1 + 3 x 2 + 4 x 3 + 6 x4 + 7 x5 + 5 x 6 + 7 x 7 + 8 x8 + 9x 9
+9 x 10 + 8 x11 + 9 x12

subject to

x 1 + x 4 + x 7 + x 10 1 (SF to LA)
x 2 + x 5 + x 8 + x 11 1
x 3 + x 6 + x 9 + x 12 1
x 4 + x 7 + x 9 + x 10 + x 12 1
x 1 + x 6 + x 10 + x 11 1
and x j is binary,
x4 + x5 + x9 1
for j = 1,2, ,12
x 7 + x 8 + x 10 + x 11 + x 12 1
x2 + x 4 + x 5 + x 9 1
x 5 + x 8 + x 11 1
x 3 + x 7 + x 8 + x 12 1
x 6 + x 9 + x 10 + x 11 + x 12 1
12






x3 = 1 (assign sequence 3 to a crew)

x4 = 1 (assign sequence 4 to a crew)
x11 = 1 (assign sequence 11 to a crew)
And all other xj = 0.

Total cost is $18,000.

Another optimal solution is: x1 = x5 = x12 = 1.

= 3 (assign three crews)

j =1

Joo Miguel da Costa Sousa / Alexandra Moutinho

One optimal solution is:

303

Discussion

Joo Miguel da Costa Sousa / Alexandra Moutinho

304

Solving IP problems

This example belongs to a class called set covering problems,

with a number of potential activities (e.g. flight sequences) and
characteristics (e.g. flights).

Objective: determine the least costly combination of activities
that collectively possess each characteristic at least once.

Si is the set of all activities that possess characteristic i.

A constraint is included for each characteristic i:

jSi

In set partitioning problems the constraint is

=1

jS j
Joo Miguel da Costa Sousa / Alexandra Moutinho

305

Solving IP problems

 Difference to LP is that IP have far fewer solutions.

 IP problems have a finite number of feasible solutions.

However:
 Finite numbers can be astronomically large! With n
variables a BIP problem has 2n solutions, having
exponential growth.
 LP assures that a CPF solution can be optimal,
guaranteeing the remarkable efficiency of the simplex
method. LP problems are much easier to solve than IP
problems.
Joo Miguel da Costa Sousa / Alexandra Moutinho

306

Solving IP problems

Consequently, most IP algorithms incorporate the

simplex method. This is called the LP relaxation.

Sometimes, the solution of the LP problem is the
solution of the IP problem, such as :

Primary determinants of computational complexity:

1. number of integer variables,
2. these variables are binary or general integer variables,
3. any special structure in the problem.

This is in contrast to LP, where number of

constraints is much more important than the
number of variables.

As IP problems are much more difficult than LP, we
could apply LP and round the obtained solution...
Yes?

 Minimum cost flow problem, including transportation

problem, assignment problem, shortest-path problem and
maximum flow problem.

Special structures (see examples 2 and 3): mutually

exclusive alternatives, contingent decisions or setcovering constraints can also simplify the problem.
Joo Miguel da Costa Sousa / Alexandra Moutinho

Are integer problems easy to solve?

307

Joo Miguel da Costa Sousa / Alexandra Moutinho

308

Example 1

Example 2
Minimize

Z = x2

subject to x 1 + x 2 0.5
x 1 + x 2 3.5
and
x 1 , x 2 0,

Minimize Z = x 1 + 5 x2 subject to x1 + 10 x2 20
x1 2
and x 1 , x2 0, integers.

x 1 , x 2 integers.

Joo Miguel da Costa Sousa / Alexandra Moutinho

309

Solving IP problems

 These algorithms will be discussed later.

Pure IP problems can consider some type of

enumeration procedure.

This should be done in a clever way such that only a
tiny fraction of the feasible solutions is examined.

Branch-and-bound with a divide to conquer
technique can be used.
 dividing (branching) the problem into smaller and smaller
subproblems until it can be conquered
 conquering (fathoming) by bounding how good the best
solution can be. If no optimal solution in subset: discard it.

Most popular traditional method for solving IP

problems is the branch-and-bound technique.
311

Example: California Manuf, Co.

Joo Miguel da Costa Sousa / Alexandra Moutinho

312

Branching

Most straightforward way to divide the problem: fix
the value of a variable:

Recall prototype example:

Maximize Z = 9x1 + 5x2 + 6x3 + 4x4
subject to

 e.g. x1 = 0 for one subset and x1 = 1 for another subset.

 Subproblem 1 (fix x1 = 0):

Maximize Z = 5x2 + 6x3 + 4x4
subject to

(1) 6x1 + 3x2 + 5x3 + 2x4 10

(2)
x3 + x4 1
(3) x1 +
x3
0
(4)
x2 +
x4 0

(1) 3x2 + 5x3 + 2x4 10

(2)
x3 + x4 1
(3)
x3
0
(4) x2 +
x4 0
(5) xj is binary, for j = 2, 3, 4.

and
(5) xj is binary, for j = 1, 2, 3, 4.
Joo Miguel da Costa Sousa / Alexandra Moutinho

310

Branch-and-bound applied to BIP

Thus, a better approach to deal with IP problems that

are too large to be solved exactly are heuristic
algorithms.

Heuristics and metaheuristics are extremely efficient
for very large problems, but do not guarantee to find
an optimal solution.

Joo Miguel da Costa Sousa / Alexandra Moutinho

Joo Miguel da Costa Sousa / Alexandra Moutinho

313

Joo Miguel da Costa Sousa / Alexandra Moutinho

314

Branching

Branching

 Subproblem 2 (fix x1 = 1):

Maximize Z = 9 + 5x2 + 6x3 + 4x4
subject to

Dividing (branching) into suproblems creates a tree

with branches (arcs) for the All node.

This is the solution tree or enumeration tree.

Branching variable is the one used for branching.

The branching continues or not after evaluating the
subproblem.

Other IP problems usually creates as many branches
as needed.

(1) 3x2 + 5x3 + 2x4 4

(2)
x3 + x4 1
(3)
x3
1
(4) x2 +
x4 0
(5) xj is binary, for j = 2, 3, 4.

Joo Miguel da Costa Sousa / Alexandra Moutinho

315

Bounding

316

Bounding in example
 Example: for the whole problem, (5) is
replaced by xj 1 and xj 0 for j=1,2,3,4. Using
simplex:
 (x1, x2, x3, x4) = (5/6, 1, 0, 1), with Z = 16.5
 Thus, Z 16.5 for all feasible solutions for BIP
problem. Can be rounded to Z 16 (why?)
 LP relaxation for subproblem 1:
 (x1, x2, x3, x4) = (0, 1, 0, 1),
with Z = 9
 LP relaxation for subproblem 2:
 (x1, x2, x3, x4) = (1, 4/5, 0, 4/5), with Z = 16.5

A bound is needed for the best feasible solution of

each of the subproblems.

Standard way is to perform a relaxation of the
problem, e.g. by deleting one set of constraints that
makes the problem difficult to solve.

Most common is to require integer variables, so LP
relaxation is the most widely used.

Joo Miguel da Costa Sousa / Alexandra Moutinho

Joo Miguel da Costa Sousa / Alexandra Moutinho

317

Joo Miguel da Costa Sousa / Alexandra Moutinho

318