Integer Programming

Formulations

Lecture 2
Integer Programming Formulations Integer Programming

Logical constraints
MATH3220 Operations Research and Logistics Nonlinear Functions
Jan. 8, 2015

Pan Li
The Chinese University of Hong Kong
2.1
Integer Programming
Agenda Formulations

Integer Programming

Logical constraints
1 Integer Programming Nonlinear Functions

2 Logical constraints

3 Nonlinear Functions

2.2
Integer Programming
Integer Programming Formulations

Integer Programming

Logical constraints
Integer Programming: a linear program plus the additional Nonlinear Functions
constraints that some or all of the variables must be integer
valued.

We also permit "xj ∈ {0, 1}", or equivalently, "xj is binary".

This is a shortcut for writing the constraints:

0 ≤ xj ≤ 1 and xj is integer.

2.3
Integer Programming
Simple logical constraints Formulations

Here, we address different logical constraints that can be

transformed into integer programming constraints.
selection of items from a subset Integer Programming

Logical constraint IP constraint Logical constraints

Nonlinear Functions
If item i is selected, then item j is also selected. xi − xj ≤ 0
Either item i is selected or item j is selected, xi + xj = 1
but not both.
Item i is selected or item j is selected or both. xi + xj ≥ 1
If item i is selected, then item j is not selected. xi + xj ≤ 1
If item i is not selected, then item j is −xi + xj ≤ 0
not selected.
At most one of item i, j and k are selected. xi + xj + xk ≤1
At most two of items i, j and k are selected. xi + xj + xk ≤2
Exactly one of items i, j, and k are selected. xi + xj + xk =1
At least one of items i, j and k are selected. xi + xj + xk ≥1

2.4
Integer Programming
Simple logical constraints - con’t Formulations

Restricting a variable to take on one of several values.

Suppose that we want to restrict x to be one of the elements
{4, 8, 13}. This is accomplished as follows. Integer Programming

Logical constraints
x = 4w1 + 8w2 + 13w3 Nonlinear Functions

w1 + w2 + w3 = 1
wi ∈ {0, 1}for i = 1 to 3.

Question: If we want to restrict x to be one of the elements {0,

4, 8, 13}, how should we model it?

2.5
Integer Programming
Simple logical constraints - con’t Formulations

Restricting a variable to take on one of several values.

Suppose that we want to restrict x to be one of the elements
{4, 8, 13}. This is accomplished as follows. Integer Programming

Logical constraints
x = 4w1 + 8w2 + 13w3 Nonlinear Functions

w1 + w2 + w3 = 1
wi ∈ {0, 1}for i = 1 to 3.

Question: If we want to restrict x to be one of the elements {0,

4, 8, 13}, how should we model it?
Answer: It suffices to use the above formulation with the
equality constraint changed to "w1 + w2 + w3 ≤ 1".

2.6
Integer Programming
Simple logical constraints - con’t Formulations

Restricting a variable to take on discontinuous values.

Suppose that we want to restrict x must be either 0 or between
particular positive bounds. In algebraic notation: Integer Programming

Logical constraints
x =0 or l ≤x ≤u Nonlinear Functions

Define:

0 for x = 0
y=
1 for l ≤ x ≤ u

Then, the logical constraints can be modeled by:

ly ≤ x ≤ uy
y ∈ {0, 1}

2.7
Integer Programming
Other logical constraints, and the big M method. Formulations

Big-M method for IP formulations

Assume that all variables are integer valued.

Assume a bound u ∗ on coefficients and variables;

Integer Programming

Logical constraints

Nonlinear Functions

e.g. xj ≤ 1, 000 for all j.

|aij | ≤ 1, 000 for all i, j

Choose M really large so that for every constraint i,

|ai1 x1 + ai2 x2 + . . . + ain xn − bi | ≤ M

That is, we will be able to satisfy any "≤" constraint by

adding M to the RHS.
And we can satisfy any "≥" constraint by
subtracting M from the RHS.
2.8
Integer Programming
Logical constraint - Constraint feasibility Formulations

Binary variables that are 1 when a constraint is satisfied.

1 if f (x1 , x2 , . . . , xn ) ≤ b Integer Programming
w= Logical constraints
0 otherwise
Nonlinear Functions

Here we assume that f (x) is bounded.

Equivalent constraints:

f (x1 , x2 , . . . , xn ) ≤ b + M(1 − w).

f (x1 , x2 , . . . , xn ) ≥ b − Mw.
w ∈ {0, 1}

where the constant M is chosen to be large enough so that the

constraint is always satisfied if w = 0. Whenever w = 1 gives a
feasible solution to IP constraint, the logical constraint must be
satisfied.
2.9
Integer Programming
Logical constraint - Alternative constraint Formulations

We formulate the logical constraint, "x ≤ 2 or x ≥ 6" as follows.

Choose a binary variable w so that

Integer Programming
if w = 1, then x ≤ 2 Logical constraints

if w = 0, then x ≥ 6 Nonlinear Functions

x ≤2 + M(1 − w)
x ≥6 − Mw
w ∈ {0, 1}

To validate the formulation one needs to show:

The logical constraints are equivalent to the IP constraints.

2.10
Integer Programming
The logical constraint - Alternative constraint (con’t) Formulations

Logical constraint IP constraints

x ≤ 2 + M(1 − w)
x ≤ 2 or x ≥ 6 x ≥ 6 − Mw Integer Programming

Logical constraints
w ∈ {0, 1} Nonlinear Functions

Suppose (x, w) is feasible for the IP,

if w = 1, thenx ≤ 2.
if w = 0, thenx ≥ 6.

In both cases, the logical constraints are satisfied.

Suppose that x satisfies the logical constraints.

If x ≤ 2, then let w = 1 ⇒ x ≤2 and x ≥6−M

If x ≥ 6, then let w = 0 ⇒ x ≤2+M and x ≥6

In both cases, the IP constraints are satisfied.

2.11
Integer Programming
The logical constraint - Alternative constraint (con’t) Formulations

Logical constraint IP constraints

2x1 + 3x2 ≥ 14 or 2x1 + 3x2 ≥ 14 − M(1 − w)
5x2 − 7x3 ≤ 3 5x2 − 7x3 ≤ 3 + Mw Integer Programming

Logical constraints
w ∈ {0, 1} Nonlinear Functions

Suppose xi is Suppose that M is very large.

bounded for all i.

To show:
The logical constraints are equivalent to the IP constraints.

Suppose (x, w) is feasible for the IP,

if w = 1, then 2x1 + 3x2 ≥ 14.

if w = 0, then 5x2 − 7x3 ≤ 3.

Therefore, the logical constraints are satisfied.

2.12
Integer Programming
The logical constraint - Alternative constraint (con’t) Formulations

Logical constraint IP constraints

2x1 + 3x2 ≥ 14 or 2x1 + 3x2 ≥ 14 − M(1 − w)
5x2 − 7x3 ≤ 3 5x2 − 7x3 ≤ 3 + Mw Integer Programming

Logical constraints
w ∈ {0, 1} Nonlinear Functions

To show:
The logical constraints are equivalent to the IP constraints.

Suppose that x satisfies the logical constraints.

If 2x1 + 3x2 ≥ 14, then let w = 1 ⇒ 2x1 + 3x2 ≥ 14 and

5x2 − 7x3 ≤ 3 + M
If 5x2 − 7x3 ≤ 3, then let w = 0 ⇒ 2x1 + 3x2 ≥ 14 − M and
5x2 − 7x3 ≤ 3

In both cases, the IP constraints are satisfied.

2.13
Integer Programming
Logical constraint - Conditional constraints Formulations

These constraints have the form:

if f1 (x1 , x2 , . . . , xn ) > b1 , then f2 (x1 , x2 , . . . , xn ) ≤ b2 .

Integer Programming

Logical constraints
Since this implication is not satisfied only when both
Nonlinear Functions
f1 (x1 , x2 , . . . , xn ) > b1 and f2 (x1 , x2 , . . . , xn ) > b2 , the conditional
constraint is logically equivalent to the alternate constraints

f1 (x1 , x2 , . . . , xn ) ≤ b1 and/or f2 (x1 , x2 , . . . , xn ) ≤ b2

where at least one must be satisfied. Hence, this situation can

be modeled by alternative constraints:

f1 (x1 , x2 , . . . , xn ) ≤ b1 + B1 y ,
f2 (x1 , x2 , . . . , xn ) ≤ b2 + B2 (1 − y ),
y ∈ {0, 1}

2.14
Integer Programming
At least one of three inequalities is satisfied. Formulations

x1 + 4x2 + 2x4 ≥ 7 or 3x1 − 5x2 ≤ 12 or 2x2 + x3 ≥ 6

Create three binary variables w1 , w2 , and w3 and reformulate
the above constraint as the following system of logical, linear Integer Programming

and integer constraints. Logical constraints

Nonlinear Functions
If w1 = 1, then x1 + 4x2 + 2x4 ≥ 7
If w2 = 1, then 3x1 − 5x2 ≤ 12
If w3 = 1, then 2x2 + x3 ≥ 6
w1 + w2 + w3 ≥ 1
wi ∈ {0, 1} for i = 1 to 3.
This above system of constraints is equivalent to the following.
x1 + 4x2 + 2x4 ≥ 7 − M(1 − w1 )
3x1 − 5x2 ≤ 12 + M(1 − w2 )
2x2 + x3 ≥ 6 − M(1 − w3 )
w1 + w2 + w3 ≥ 1
wi ∈ {0, 1} for i = 1 to 3 .

2.15
Integer Programming
Logical constraint - k-Fold alternative Formulations

Suppose we must satisfy at least k of the constraints:

fi (x) ≤ bi (j = 1, 2, . . . , m)
Integer Programming
Assuming that Bi are chosen so that the ignored constraints Logical constraints

will not be binding, the general problem can be formulated as Nonlinear Functions

follows:

fi (x) ≤ bi + Bi (1 − yi )
Pm
i=1 yi ≥ k ,
yi ∈ {0, 1} (i = 1, 2, . . . , m)

2.16
Integer Programming
Nonlinear Functions Formulations

Nonlinear functions can be represented by integer

programming formulations.
Integer Programming

Logical constraints

Nonlinear Functions

2.17
Integer Programming
Fixed costs Formulations

In a typical production planning problem involving N products,

the production cost for product j may consist of a fixed cost dj
independent of the amount produced and a variable cost cj per
unit. Thus if xj is the production level of product j, its production Integer Programming

cost function may be written as Logical constraints

Nonlinear Functions

dj + cj xj xj > 0
fj (xj ) =
0 xj = 0

This is nonlinear in xj because of the discontinuity of fj (xj ) at

the origin. Consequently, the following minimum cost problem
is also nonlinear:
PN
Min z = j=1 fj (xj )
s.t. Ax = b, x ≥ 0.

2.18
Integer Programming
Fixed costs (con’t) Formulations

If it is known that 0 ≤ xj ≤ uj and dj > 0 then we can define a

binary variable yj that indicates when the fixed cost is incurred,
so that
Integer Programming

yj = 1, if xj > 0 Logical constraints

Nonlinear Functions
yj = 0, if xj = 0

Then the contribution to cost due to xj may be written as

fj (xj ) = dj yj + cj xj
with the constraints:

xj ≤ uj yj ,
xj ≥ 0,
y = 0 or 1.

2.19
Integer Programming
Fixed costs (con’t) Formulations

In a typical production planning problem involving N products,

the production cost for product j may consist of a fixed cost dj
independent of the amount produced and a variable cost cj per
unit. Thus if xj is the production level of product j, its production Integer Programming

cost function may be written as Logical constraints

Nonlinear Functions

dj + cj xj xj > 0
fj (xj ) =
0 xj = 0

This is nonlinear in xj because of the discontinuity of fj (xj ) at

the origin. Consequently, the following minimum cost problem
is also nonlinear:
PN
Min z = j=1 (cj xj + dj yj )
s.t. Ax = b
0 ≤ xj ≤ uj yj , j = 1, 2, . . . , N
yj ∈ {0, 1}, j = 1, 2, . . . , N

2.20
Integer Programming
Piecewise linear representation Formulations

Integer Programming

Logical constraints

Nonlinear Functions

Define integral variables δ1 , δ2 and δ3 so that:

δ1 corresponds to the amount by which x exceeds 0, but is
less than or equal to 4;
δ2 is the amount by which x exceeds 4, but is less than or
equal to 10; and
δ3 is the amount by which x exceeds 10, but is less than or
equal to 15. 2.21
Integer Programming
Piecewise linear representation Formulations

Integer Programming

Logical constraints

Nonlinear Functions

Hence,
x = δ1 + δ2 + δ3 ,
where
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5, (1)
and the total variable cost is given by:
Cost = 5δ1 + δ2 + 3δ3 .
2.22
Integer Programming
Piecewise linear representation Formulations

However, we should have the

following conditional Integer Programming
constraints: Logical constraints

δ1 = 4, if δ2 > 0 Nonlinear Functions

δ2 = 6, if δ3 > 0

Hence,
x = δ1 + δ2 + δ3 ,
where
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5, (2)
and the total variable cost is given by:

Cost = 5δ1 + δ2 + 3δ3 .

2.23
Integer Programming
Piecewise linear representation (I) Formulations

Logical constraints:

0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5,
Integer Programming
δ1 = 4, if δ2 > 0
Logical constraints

δ2 = 6, if δ3 > 0 Nonlinear Functions

Define

1 if δ1 is at its upper bound
w1 =
0 otherwise

1 if δ2 is at its upper bound
w2 =
0 otherwise

2.24
Integer Programming
Piecewise linear representation (I) (con’t) Formulations

Logical constraints:

0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5,
Integer Programming
δ1 = 4, if δ2 > 0
Logical constraints

δ2 = 6, if δ3 > 0 Nonlinear Functions

Then the constraints above can be replaced by:

4w1 ≤ δ1 ≤ 4,
6w2 ≤ δ2 ≤ 6w1 ,
0 ≤ δ3 ≤ 5w2
w1 and w2 binary.

2.25
Integer Programming
Piecewise linear representation (I) (con’t) Formulations

Logical constraints:
0 ≤ δ1 ≤ 4, 0 ≤ δ2 ≤ 6, 0 ≤ δ3 ≤ 5,
δ1 = 4, if δ2 > 0 Integer Programming

Logical constraints
δ2 = 6, if δ3 > 0 Nonlinear Functions

Then the constraints above can be replaced by:

4w1 ≤ δ1 ≤ 4,
6w2 ≤ δ2 ≤ 6w1 ,
0 ≤ δ3 ≤ 5w2
w1 and w2 binary.

There are three feasible combinations for the values of w1 and

w2 :
w1 = 0, w2 = 0 corresponding to 0 ≤ x ≤ 4
w1 = 1, w2 = 0 corresponding to 4 ≤ x ≤ 10
w1 = 1, w2 = 1 corresponding to 10 ≤ x ≤ 15 2.26
Integer Programming
Piecewise linear representation (I) (con’t) Formulations

The same general technique can be applied to piecewise linear

curves with any number of segments.

The general constraint imposed upon the variable δj for the jth Integer Programming

segment will be: Logical constraints

Nonlinear Functions
Lj wj ≤ δj ≤ Lj wj−1
where Lj is the length of the segment.

2.27
Integer Programming
Approximation of Nonlinear Functions Formulations

One of the most useful applications of the piecewise linear

representation is for approximating nonlinear function.

Suppose the expansion cost in our previous example is given Integer Programming

by the heavy curve in the figure below. Logical constraints

Nonlinear Functions

2.28
Integer Programming
Approximation of Nonlinear Functions (con’t) Formulations

Integer Programming

Logical constraints

Nonlinear Functions

If we draw linear segments joining selected points on the

curve, we obtain a piecewise linear approximation, which can
be used of the curve in the model. The piecewise
approximation is represented by introducing integer variables
as indicated before.

By using more points on the curve, we can make the

approximation as close as we desire. 2.29
Integer Programming
Piecewise linear representation (II) Formulations

y= 2x if 0 ≤ x ≤ 3
y= 9−x if 4 ≤ x ≤ 7
Integer Programming
y= −5 + x if 8 ≤ x ≤ 9 Logical constraints

Nonlinear Functions
x is integer valued.

If the variables are defined as above, then

y = 2x1 + (9w2 − x2 ) + (−5w3 + x3 ) 2.30

Integer Programming
Piecewise linear representation (II) (con’t) Formulations

Add constraints
Constraints

Definitions of the variables.

0 ≤ x1 ≤ 3w1 Integer Programming

Logical constraints
w1 ∈ {0, 1} Nonlinear Functions

4w2 ≤ x2 ≤ 7w2
w2 ∈ {0, 1}
8w3 ≤ x3 ≤ 9w3
w3 ∈ {0, 1}

w1 + w2 + w3 = 1
x = x1 + x2 + x3
xi integer∀i
Suppose that 0 ≤ x ≤ 9, x integer.
If (x, w) satisfies the definitions, then it also satisfies the
constraints.
If (x, w) satisfies the constraints, then it also satisfies the
definitions. 2.31
Integer Programming
Exercise Formulations

Construct integer programming formulations to represent the

following piecewise linear function.
 Integer Programming
 0 if x = 0
Logical constraints
f (x) = 1 if 1 ≤ x ≤ 2 Nonlinear Functions
2 if 3 ≤ x ≤ 4.


2.32
Integer Programming
Summary Formulations

IPs can model almost any combinatorial optimization

problem.
lots of transformation techniques.
Integer Programming
Next lecture: how to solve integer programs. Logical constraints

Nonlinear Functions

2.33