Week 5

Question 1

How to do the branch and bound method?

Answer 1

1. Solve like LP problem
2. If the optimal solution is also ILP then it is the solution, if not continue
3. If the solution is not “prune” then ignore entire branch
4. Make a “branch” for either of the options, for one of the variables, the order does not reallu matter, now go to step 2

Question 2

What are the three pruning criterea?

Answer 2

1. The upper bound on the solution value of the sub-problem in that node is attained by a feasible integer solution.
2. The upper bound on the solution value of the sub-problem in that node is lower than (or equal to) the value of the best feasible (integer) solution.
3. The sub-problem in that node is infeasible.
4. [Optional, only for packing problems] If in a subproblem the remaining capacity is smaller than the weight of each of the remaining items, then the optimal solution has been reached for the subproblem by setting all remaingin items to 0, andn the subproblem can be pruned.

Question 3

How does the Cutting Plane algorithm work?

Answer 3

1. Solve with the LP-relaxation(, by dropping the integrality constraints)
2. Now rewrite the constraint to equals t₁ (or t_i), and and rewrite the rhs to the higest integer that is lower then the value.
3. Repeat step 2 until no fractions remain, if no fractions remain then this is the optimal solution.

Question 4

What is the definition of a relaxation?

Answer 4

Given two problems P1, max{f(x) | x in S} and P2 max{g(x)| x in T} P2 is a relaxation of P1 if:

1. S subset of T
2. g(x) ≥ f(x) for all x in S

Question 5

What is the theorem about Lagrangean Dual?

Answer 5

For maximazation problems the Lagrangean Dual always yiels an upper bound that is at least as strong to the LP-relaxation problem.