COMP3530 Discrete Optimization
Week 7: Integer Programming
School of Computer Science University of and Refresher
Goal for Today
Develop algorithmic framework for solving Integer Linear Programs:
” minimize c · x C c – IR
subject to Ax b
A-c- IR”” -+ 6c-IRM
x 2 Zn
1
Recall
Simplex is a practical algorithm for solving LPs.
–
Some times LPs are integral. In those cases we can solve the
–
underlying IP by simply solving the LP.
Some times the LP relaxation of an IP has optimal solutions whose cost can only be attained by setting variable to fractional values.
2
Branch and Bound
Linear Relaxation
Def.: The linear relaxation of a given ILP is the LP that results
from removing the integrality constraints.
min c. ✗ (LP) Sit A-✗ 76
relax →
Z
5- Jeez! Ax> b }
(P) min c. ✗
S.t. Axzb
” c- IR
” ✗ c-
✗
P={✗ ER? Axzb }
w
gap
3
Feasible Region Decomposition
Def.: A decomposition of a feasible set S ✓ Zn of aSn ILP is a collection of subsets S1,…,Sk ✓ S such that S = i Si.
Lem.:Letz=minc·xandzi =minc·x.Thenz=minzi.
x2S
”
x2Si i
Z is
global optimal value
S, , Sz, – . be a
.SK
need
not
partition
4
Branching
Def.: Branching is a process used to break up a hard subprogram S into smaller subprograms S1 and S2:
• solve the linear relaxation of S to get a solution x • if x⇤ is integral, we are done!
• otherwise, pick a variable xi⇤ 2/ Z and define:
– S1 = {x 2 S : xi bxi⇤c} – S2 = {x 2 S : xi dxi⇤e}
*
=D✗ in
✗F- 1.25
{S.ES ES
is not feasible relaxation of
sor52 I
.IS
5=5052
,
✗ is -=L×
✗ • 32=8*1
5
Branching
Def.: Branching is a process used to break up a hard subprogram S into smaller subprograms S1 and S2:
• solve the linear relaxation of S to get a solution x • if x⇤ is integral, we are done!
• otherwise, pick a variable xi⇤ 2/ Z and define:
– S1 = {x 2 S : xi bxi⇤c} – S2 = {x 2 S : xi dxi⇤e}
0s
Problem is
that
4–01 ¥!1 !¥
sub problems
Her ☒
# with #
000
grows exponentially
branching
levels
relax is5 infeasible
I f LP
Bounding
Def.: Bounding is the process used to lower and upperbound the
Si
• zi is the value of the LP relaxation of Si
• z ̄ is the value of an integral solution found by a heuristic
value of a subproblem z z z ̄:
i i i for subproblem
”
i
We can put together these bound into a bound fo0r the whole problem S: y s,
• z = mini zi , and • z ̄ = m i n z ̄ .
§.
ii
? ±=Ii*< Z-jr-21-zs-z-7.Z-2-j-SZirEI.se- - I
6
Rules for
Def.: We say that a subproblem can b÷e pruned when it does not need to be explored further.
There are three reasons why we may want to prune a subproblem
Si: =
• Prune by optimality: If z = z ̄ then we know z .
iii • Prune by infeasibility: If Si = ; then zi = 1.
• Prune by bound: If z z ̄, there is no better solution in S . ii
still don't know 2-i out but we don't have to find
EsEisZi =D Z S Zi
7
Stronger Linear Relaxation
Strength of a Linear Relaxation
Def.: Let P ✓ Rn and Q ✓ Rn be two linear relaxation of the same integer program. We say the former if the stronger than the latter if P ⇢ Q.
÷
÷.
8
Bipartite Matching Problem
m a x we ✗ e %# ⇐
ltuev
Xetxgsr enf -401
m a - E w ie
| He,fEE
ec-fo.is feet ✗etxfsv VI.}
is tighter ? μ
Exe so 8cm) eescn)
✗ec-lo.is feet p=}e←1R¥! ✗ (SH)S'
✗ th"}Q={✗c-IRIE' :
which
PSQ
÷¥E±+÷
one
1
!
§
=D
? Yes Q
)Si
f e ¥e t
relaxation
d- ✗ c-
✗ c- xetxf-xffi.la ? No ✗e-£
QEP
✗c-Q
¢8
9
✗
Gen÷eral Matching Problem .
Thm.: The constraint matrix associated with the circulation
problem polyhedron is TU.
V-uc-vtg.E.ee#fP--4xc-RIiee]
*
Exe Er ,
P' =P constraints :
integral solution solutions
su
Has
we need extra
1
should be obeyed by all shout fraction
I
✗e.+ ✗e.Hess' [✗e
cut off
¥5k ]-
Yet -142 TE.e←EE 112
-4 /Vasu .
••
✓
10
Administratrivia
Announcements
• Assignment 1:
• Regrade requests close on Sep 24.
• Assignment 2:
• we aim to post marks before semester break
• Assignment 3:
• to be released this week
• due on November 8 (11:59pm) And
Enjoy your well deserved break!!
11
12