Recap: Integer Programming

Question 1

Classification of MIPs

Answer 1

Continuous and integer decision variable

Linear objective function and constraints

Special case: only integer decision variables —> integer (linear) program (IP)

Question 2

Knapsack Problem model assumptions

Answer 2

Choice between N items (n = 1,…,N) each with known profit v_n and weight w_n

Maximum overall weight b for all items

Binary variable: gamma_n is 1, if item n is chosen, 0 else

Question 3

Combinatorial optimization

Answer 3

Solutions via combination of elements

Practical problems have typically a combinatorial character

Question 4

Number of (theoretically) possible solutions of the Knapsack Problem

Answer 4

2^N

Question 5

Basic problem of combinatorial optimization

Answer 5

Number of possible solutions exponentially increases with increasing problem size (e.g., number of items)

Question 6

Solution approaches

Answer 6

Exact methods

• – terminates with an optimal solution
• – computational effort (usually) very high

heuristic approaches

• – optimality of solution not provable
• – “good” solution with reasonable computational effort
• – solution quality not assessable

Question 7

Exact methods examples

Answer 7

1) Decision tree methods:
- - complete enumeration
- - incomplete enumeration (e.g., branch-and-bound methods)
- - dynamic programming

2) cutting plane methods
3) combinations of (1) and (2) (e.g., branch-and-cut methods)

Question 8

General idea of constructive heuristics

Answer 8

Generating a new solution from scratch

Adding new components to an empty (partial) solution

Question 9

Examples of constructive heuristics

Answer 9

Nearest Neighbor Heuristic for TSP

Insertion Heuristics for TSP

Saving Heuristic for VRP

Truncated exact methods (e.g., branch-and-bound with a given time limit)

Fix&Relax heuristic

Question 10

the different types of constructive heuristics

Answer 10

uninformed heuristics:
- without consideration of objective function

greedy-heuristics:

• try to achieve maximum improvement in each step
• often myopic (kurzsichtig), as future effects are not considered

‘forward-looking’ heuristics:
-try to estimate the impact of the next step on the solution

Question 11

Description of improvement heuristics

Answer 11

Start with a (set of) feasible initial solution(s)

• • local search approaches
• • population-based approaches

improvement of actual best solution

• • deterministic approaches
• • stochastic approaches

Question 12

examples of improvement heuristics

Answer 12

2-opt for TSP

Tabu Search

Simulated Annealing

Genetic Algorithms

Fix&Optimize Heuristic

Question 13

What is the standard technique for solving MIPs exactly, that is integrated in commercial software for solving MIPs?

Answer 13

Branch-and-Bound method

Question 14

What is the idea of approach of the B&B-method?

Answer 14

Systematic search in set of feasible solutions —> optimal solution will be among them

Using bounds to exclude suboptimal solution early during enumeration

Question 15

Basic principles of B&B

Answer 15

BRANCHING:
Decomposing problems into several subproblems –> enumeration tree with subproblems as nodes

BOUNDING:
Limitation of branching process by determining bounds of the objective function value –> discarding subproblems

Question 16

What does the LP relaxation for the Knapsack Problem look like?

Answer 16

Neglecting integrality constraints of gamma_n, which is supposed to be binary but now is 0 <= gamma_n <= 1.

You then order the items according to decreasing relative profit ( v_n : w_n ). Pack items according to their relative profit until the capacity is scrapped, meaning no full item can fit anymore. Choose the first item that could not be packed anymore and “fractionally” fit it according to the remaining space in the Knapsack. This combination of relaxed and binary variables leads to the relaxed objective function Z’.

Question 17

How do you get the upper and the lower bound for the B&B algorithm for the Knapsack problem?

Answer 17

Upper bound is the objective function value Z’ of the LP relaxation.

Lower bound is the objective function value when the fractional value of the relaxed solution is rounded down (and thus becomes a feasible solution).

Question 18

What is the optimal solution of the initial problem (of B&B)?

Answer 18

Best solution of a subproblem

Question 19

What are the three discarding rules (for maximization problems)?

Answer 19

Case A: A better solution already exists (Upper bound of the node is worse than the global lower bound)

Case B: New best solution found (Upper bound is higher than lower bound and the solution is feasible)

Case C: Infeasible subproblem

Question 20

What is the goal of rules of order for problems to be considered?

Answer 20

Early determination of the optimal solution (minimization of the decision tree)

Question 21

Which are the two most common rules for processing order of the candidate list in B&B?

Answer 21

Depth-first search: LIFO rule (last-in first-out)

Breadth-first search: MUB rule (maximum-upper-bound)

Question 22

What is the outline of the LIFO rule?

Answer 22

Continue with the last subproblem P_i included in the candidate list

Leave P_i in the candidate list until it is completely branched —> Form the subproblems P_i_j

After processing the belonging subtree of P_i_j —> Branch P_i

If P_i is completely branched —> remove from candidate list

(Im Grunde schaut man sich das erste Kind des Basisknotens an, macht dazu wieder das Branchen, schaut sich wieder nur das erste Kind an und das so lange, bis man eine feasible solution hat und “backtracked” dann zu dem ersten Knoten, der noch nicht vollständig gebranched wurde)

Question 23

Outline of MUB rule?

Answer 23

1) Select that P_i from the candidate list, which has the largest upper bound.
2) Form all subproblems of said P_i and calculate their upper bounds

repeat.

Question 24

Advantages and disadvantages of LIFO and MUB

Answer 24

LIFO:
+++ A first feasible solution is found quickly with low number of suproblems in candidate list
— first feasible solution is generally bad

MUB:
+++ First feasible solution generally very good
— longer candidate list copared to LIFO rule