@ Notes On Integer Programming

Integer programs: linear equalities and inequalities plus constraints that say a variable must be integer valued.

All integer programs have linear equalities and inequalities and some or all of the variables are required to be integer.

• If all variables are required to be integer, then it is usually called a pure integer program.

• If all variables are required to be 0 or 1, it is called a binary integer program, or a 0-1 integer program.

• If some variables can be fractional and others are required to be integers, it is called a mixed linear integer program (MILP).

Modeling Logical Constraints as IPs:

The main appeal of Integer Programming is the ability to include many constraints not possible in Linear Programming formulations.

For pure BILP problems all constraints expressible through Boolean logic can be represented by following some simple rules. For MILP some more skill is required, but logical constraints can still be modeled.

A special case BILP, (an IP where all variables are binary):

In the special case of a BILP problem it is possible to model logical connectives more simply than in a general integer program. The operators AND, OR, NOT, are sufficient to represent all Boolean logic.

XOR, implication are shown because these are common operations.

Note: Each entry in the table assumes that both binary variables in the operation being are to 1.

For example there is an entry for (A = 1) AND (B = 1),

but there is no entry for ((A = 1) AND (B = 0)), or ( (A = 0) ⇒ (B = 1) ).

How can we model this new constraint ?

The answer is to use the NOT(A) = (1 - A = 1) rule to transform these constraints.

Then ( (A = 1) AND (B = 0) ) becomes ( (A = 1 ) AND (1 - B = 1) )

And ( (A = 0) ⇒ (B = 1) ) becomes ( (1 - A = 1) ⇒ ( B = 1 ) )

Now apply the rules above to the changed equations:

( (A = 1 ) AND (1 - B = 1) ) becomes (A + 1 - B = 2) = (A - B = 1)

( (1 - A = 1) ⇒ ( B = 1 ) ) becomes (1 - A <= B ) = (A + B >= 1)

Compatibility: In almost every case in the table below I have been careful to make sure that the added constraints are of the form f(v) = 1.

Where v is the vector of I.P variables defined for the problem.

This is so that the table becomes self-referential, the last constraint added for each entry can be used to fully represent the validity of the statement thus far, all further table operations will apply to it.

For example, if I have I wish to include the constraint

(A = 1) OR ( (B = 1) AND (C = 1) )

I will model the portion ( (B = 1) AND (C = 1) ) as (B + C - 1) = 1

I have (A = 1) OR ( (B + C - 1) = 1 ), an expression I can match to the left hand side of the table.

Now I will apply the operations indicated on the right hand side of the table for the OR operation.

I define binary variable y, add the constraint (A + B + C - 1 >= 1 - y), then add the constraint (1 - y = 1). If that entire expression were then itself part of a larger expression, for example

(A = 1) OR ( (B = 1) AND (C = 1) ) ⇒ (Z = 1)

Then the entire left hand side of that expression can be substituted by the last constraint I added, namely it becomes (1 - y = 1) ⇒ (Z = 1). To solve this expression I can look up the implication entry in the table and proceed. I will define a binary variable x, add constraint (1 - y - Z) <= x, then add the constraint (1 - x) = 1. Now if this were in turn part of an even larger expression, all I need to work with this entire expression is the left hand side of this last constraint, namely (1 - x).

So, according to this table method, the constraint (A = 1) OR ( (B = 1) AND (C = 1) ) ⇒ (Z = 1).

Can be expressed as a set of L.P constraints as follows:

define binary variable y,

add the constraint (A + B + C - 1 >= 1 - y),

define a binary variable x,

add constraint (1 - y - Z) <= x,

then add the constraint (1 - x) = 1

Note that (1 - y = 1) is not a constraint in the set. This is because it was a sub expression of a larger logical expression, and as such it is represented in the first constraint added when that sub-expression was processed ((1 - y - Z) <= x).

Also, notice that the constraints (1 - y - Z) <= x , and (A + B + C - 1 >= 1 - y) were added.

Such constraints are added only in the cases where an OR, or ⇒ operation occur.

These constraints ensure that if the expression which they represent holds true, then (1 - the variable introduced) = 1.

If the expression that they represent does not hold true, then the constraint will always be satisfied.

This is important since otherwise these constraints would mandate that the expression that they represent be true for any valid solution of the problem!

I shall show how to model some interesting constraints on the Stock Problem below:

Stockco is considering 6 investments. The cash required from each investment as well as the NPV of the investment is given next.

The cash available for the investments is $14,000.

Stockco wants to maximize its NPV.

What is the optimal strategy?

An investment can be selected or not.

One cannot select a fraction of an investment.

Binary Variables X1 … X6

Maximize 16X1+ 22X2+ 12X3+ 8X4+ 11X5+ 19X6

5X1+ 7X2+ 4X3+ 3X4+ 4X5+ 6X6 <= 14

Let’s see how to add some constraints to this problem:

Exactly 3 stocks are selected.

X1 + X2 + X3 + X4 + X5 + X6 = 3

This example shows that sometimes constraints in an BILP can be expressed much more concisely than by using purely Boolean operators.

The equivalent Boolean expression would need to look at expressions of the form ( X1 = 1 AND X2 = 1 AND X3 = 1) OR ( X1 = 1 AND X2 = 1 AND X4 = 1) etc.

Applying the table method would result in many unnecessary variables and constraints.

If stock 2 is selected, then so is stock 1.

(X2 = 1) ⇒ (X1 = 1)

define bin-var y.

add constraint: (X2 + X1) >= 1 - y

add constraint: (1 - y) = 1

Equivalently, in this simple case we can say X2 <= X1 .

However this only works for the simple case.

If stock 1 is selected, then stock 3 is not selected.

(X1 = 1) ⇒ (X3 = 0)

(X1 = 1) ⇒ (1 - X3 = 1)

define bin-var x.

add constraint: (X1 - 1 + X3 ) <= x

add constraint: (1 - x) = 1

Equivilantly X1 + X3 <= 1.

But again, this formulation will not generalize.

Either stock 4 is selected or stock 5 is selected, but not both.

(X4 = 1) XOR (X5 = 1)

X4 + X5 = 1

If stock 1 or stock 2 are selected, then stock 3 and stock 4 must be selected.

(X1 OR X2) ⇒ ( X3 AND X4 )

define bin-var V1.

add constraint: (X1 + X2) >= 1 - V1

define bin-var V2.

add constraint: (2 - V1 - X3 - X4) <= V2

add constraint: (1 - V2) = 1

Can be simplified to:

Binvars:

V1

Constraints:

(X1 + X2) >= 1 - V1 ,

2 <= V1 + X3 + X4

Logical Constraints in General Integer Programming Problems

Constraints specified through inequalities can be represented through binary variables by applying the big M method .

For example: x + y ≤ 100 becomes x + y + s1 = 100, whilst x + y ≥ 100 becomes x + y − a1 = 100.

A term including each such introduced multiplied by a large negative M value are introduced into a maximizing utility function.

This ensures that whenever each such variable is set to 0 the appropriate constraint is satisfied. The method is described in detail in the link above.

Once the procedure is performed the resulting variables may be used to represent more complicated binary constraints as outlined above.

When looking at modeling logical general integer programming constraints some different techniques can be applied.

Either-Or Constraints:

If we want to ensure that at least one of the following is are satisfied:

f(x1, x2, x3,...,xn) ≤ 0 OR

g(x1, x2, x3,...,xn) ≤ 0

Then we add the following constraints:

f(x1, x2, x3,...,xn) ≤ My AND

g(x1, x2, x3,...,xn) ≤ M(1-y)

y is a 0-1 variable.

M is a number chosen large enough to ensure that

f(x1, x2, x3,...,xn) ≤ M and g(x1, x2, x3,...,xn) ≤ M

for all values of x that satisfy the other constraints of the problem.

Key steps:

1) Choose an appropriate M (inf).

2) Define binary variable y.

3) For each either-or constraint define 2 new constraints as above.

Generalized Either-Or, k of N must hold:

If k of N constraints must hold:

define N binary variables y1...yn

define M as before.

Produce N constraints of the form:

fi(x) <= bi + Myi

Produce an additional constraint:

Σ_i=1^N (y_i) = N - k

If-then constraints:

Suppose we want to ensure that: f(x1, x2, x3,...,xn) > 0 implies that g(x1, x2, x3,...,xn) ≥ 0

Then we add the following constraints:

-g(x1, x2, x3,...,xn) ≤ My AND

f(x1, x2, x3,...,xn) ≤ M(1-y)

Choose M so that f(x) ≤ M and –g(x) ≤ M for all values of xi that satisfy the problem.

(P=>Q) = (!P OR Q) {modus-ponens}

P = ( f(x1, x2, x3,...,xn) > 0 )

!P = ( f(x1, x2, x3,...,xn) ≤ 0 )

Q = ( g(x1, x2, x3,...,xn) ≥ 0 ) = (- g(x1, x2, x3,...,xn) ≤ 0 )

So:

( f(x1, x2, x3,...,xn) ≤ 0 ) OR ( -g(x1, x2, x3,...,xn) ≤ 0 ) *Use Either-Or method from above*

Define M S.T {f(x) ≤ M and –g(x) ≤ M for all values of xi that satisfy the problem.}

Define binary variable y.

f(x1, x2, x3,...,xn) ≤ My

-g(x1, x2, x3,...,xn)≤ M(1-y)

Problem :

For example: if (A > 0) then B >= 0.

Answer :

if (A > 0) then B >= 0

==>

( A > 0 and B >= 0 ) or ( A <= 0 )

==>

( 0 < A and 0 <= B ) or ( A <= 0 )

==>

0 < A + M1*y ........ (1)

0 <= B + M2*y ........ (2)

A <= 0 + M3*(1-y) ........ (3)

where y = {0, 1}

Note that y is a binary variable, that is, y = {0, 1}.

In addition, M1, M2, and M3 are constants whose values should be large enough.

If y=0, then (A > 0 and B >= 0) and constraint (3) is redundant.

If y=1, then constraints (1) and (2) are redundant.

==> /* constraint (1) can be removed */

0 <= B + M2*y ........ (4)

A <= 0 + M3*(1-y) ........ (5)

where y = {0, 1}

Note that y is a binary variable, that is, y = {0, 1}. In addition, M2 and M3 are constants whose values should be large enough.

According to (5), if A > 0, then y=0 and thus B >= 0.

If (A > 0) is not satisfied, then y=0 or y=1. Therefore, B is unrestricted.

*http://www.yzuda.org/Useful_Links/optimization/if-then-else-01.html

*http://www.yzuda.org/Useful_Links/optimization/if-then-else-02.html

Branch & Bound:

Techniques for solving integer programs:

Complete Explicit Enumeration:

All possible solutions to the problem instance are made explicit, and explored in turn. The best of these is chosen as the optimal solution.

Branch & Bound:

Implicitly search all solutions in the search space. This method covers the entire search space like complete explicit enumeration, but does not look at all solution instances. The vast majority of problem instances will be ‘pruned’ and not explored.

Implicit Enumeration:

Branch and bound when applied to only binary variables.

Cutting Planes:

Iteratively solved relaxed LP versions of the problem IP instance adding a constraint to eliminate a fractional solution at each iteration.

Duality:

Every MILP program M has an associated dual program M’.

Each program can be converted into it’s dual in a series of steps.

Call this operation DUAL(M), then DUAL(M) = M’ .

The dual of a dual is the original problem, so DUAL(M’) = M.

Weak duality states that for every solution x of M, and every solution y of M’

cTx <= bTy

this is equivalent to saying that the objective function of the maximization will never exceed the objective function of the dual on all possible solutions for the dual and the primal.

If the primal is infeasible, then the dual is either infeasible or unbounded .

If the primal is unbounded, then the dual must be infeasible.

If the primal is feasible and bounded, then the dual is feasible and bounded.

If the primal is feasible and bounded, then the dual is also feasible and bounded, and strong duality states that cTx = bTy.

This means that the objective functions of the primal maximization will equal the objective function of the dual minimization at optimal solutions x,y.