Exact Methods

Question 1

Lower bound computation (for exact methods)

Answer 1

Computation procedure is determined by the structure of the problem, specially in NP-hard problems with a PLI model that is inpractical to use (e.g. too many integer variables).

There are 4 ways of calculating the lower bound:

• Problem relaxation by constraint elimination
• Modifying the objective function
• Lagrangian Relaxation
• Surrogate Relaxation (hardly used in practice, since the surrogate problem is usually not polynomial)

Question 2

Problem relaxation by constraint elimination

Answer 2

Constraints are removed or relaxed (integer variables are transformed into continuos ones).

Question 3

Problem relaxation by modifying the objective function

Answer 3

P1 should be polynomial, otherwise it wouldn’t be efficient enough.

Question 4

Lagrangian Relaxation

Answer 4

Question 5

Lagrangian Relaxation: equality and inequality constraints;

Answer 5

Question 6

Solving the Langrangian dual

Answer 6

When the constraints (easy and hard) are linear in x, there are general exact methods.

The subgradient is one of such methods that converges to the optimal lower bound.

Algorithm:

1. k = 0, u₀ is given
2. Solve linear subproblem w(u) = min L(x,u) s.t. u >= 0, and get optimal x*
3. using x* derive a subgradient in x*
   set u_k+1 = max(0, u_k + a_k (d - D x(u_k) )
4. Go to 2 until u converges or gets in pre-defined range.

Question 7

Lagrangian Example Exact Solution

Answer 7

In this example an optimal solution for the lagrangian subproblem w(u), can be found by setting to 1 every x with a coefficient > 0.

Question 8

Lagrangian Example Subgradient

Answer 8

max 10x1 + 4x2 + 14x3

3x1 + x2 + 4x3 <= 4

x1,x2,x3 boolean.

Question 9

Dynamic Programming Optimality Principle

Answer 9

Also called Bellman principle: if we consider an optimal solution and a subset of it, then that sub-solution is a noptimal solution for the corresponding sub-problem.

The shortest path algorithm is an example of it: a sub-path from i to j of the shortest path is an optimal solution of the shortest-path problem from edge i to j.

Question 10

Relationship between UB and LB of a node i and its parent j

Answer 10

In min. problems: The lower bound of a child node is greater or equal to the lower bound of the father. No relationships exists with the upper bound.

In max. problems: the upper bound of the father is >= max(UB of each child)

Question 11

KP 0/1 Dynamic Programming optimality recursive relation

Answer 11

Question 12

Proof that lagrangian relaxation is lower bound of a problem

Answer 12