Integer Linear Programming Solving

Question 1

Branch and Bound

Answer 1

We solve the LP relaxation problem.
Then 1 by 1 we enumerate the possible binary values of the x values

if solution of branch is all integer, fathom (stop searching this branch) it and make it your best solution aka incumbent (if it is the case)

if you visit a branch that is not integers continue visiting as long as its value is bigger than the current incumbent (or smaller if minimization). Otherwise fathom.

if not binary values, instead of having 2 branch ( 1 for x=1 and for x=0) we would have ranges, eg: x<=7, x>=8

Question 2

LP relaxation

Answer 2

0 <= x <= 1

then round to nearest integer
/!\ the optimal found can violate the constraints. then, can be difficult to find the true optimal

Optimum LP-relaxation -> upper bound ILP. ILP can never be better than solution of the LP relaxation. If minimization then it is a lower bound.

Question 3

Branch and cut

Answer 3

The same as branch and bound but we rewrite the LP such that less branches will need to be visited

1. fixing variables
2. eliminating redundant constraints
3. tightening constraints
4. cutting planes

Question 4

Tightening constraints

Answer 4

check constraints, if you see that not all x can =1 such that <= is satisfied, the constraint can be rewritten as x+x+.. = 1. You replace constraints if you see that the new hold iff this one hold

Works for <= constraints ! (if not multiply by -1)

Algorithm
have constraint sum_i aixi <= b
S = sum of the + coef

for ai > 0
if S <= b +|ai| then ai = S - b and b = S - a

for ai <0
S<= b + |ai| then ai = b - S

repeat and rewrite the constraint, recompute S with the new coef.

Question 5

Cutting planes

Answer 5

Adding constraints to the LP program to reduce the feasible region

consider the constraints and see what it implies in the eyes of the binary values
if have x + x + x + … <= …
and see that to satisfy it then eg x + x +x <=2
this is a constraint you add. It means for the LP, not all binary can = 1.

this technique include minimum covers

Question 6

minimum cover

Answer 6

this yields to a cutting plane (we add a constraint)

The constraint is satisfied if and only if at least one variable in the constraint = 0
thus cutting plane : sum var <= num var constraint - 1

check each constraint and whether or not all can = 1

The minimum cover is the sets of decision variables concerned by the cutting plane ie: {x1,x2,…}

Question 7

removing redundant constraints

Answer 7

check if constraints satisified even if taking the strongest binary values
if yes then remove

Question 8

fixing variables

Answer 8

Check variables, if see that to satisfy constraint a variables is obligated to = 1 or 0 then fix its value.
This often enable other values to be fixed and redundant constraints can be removed.