Recap: Integer Programming Flashcards
Classification of MIPs
Continuous and integer decision variable
Linear objective function and constraints
Special case: only integer decision variables —> integer (linear) program (IP)
Knapsack Problem model assumptions
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
Combinatorial optimization
Solutions via combination of elements
Practical problems have typically a combinatorial character
Number of (theoretically) possible solutions of the Knapsack Problem
2^N
Basic problem of combinatorial optimization
Number of possible solutions exponentially increases with increasing problem size (e.g., number of items)
Solution approaches
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
Exact methods examples
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)
General idea of constructive heuristics
Generating a new solution from scratch
Adding new components to an empty (partial) solution
Examples of constructive heuristics
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
the different types of constructive heuristics
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
Description of improvement heuristics
Start with a (set of) feasible initial solution(s)
- local search approaches
- population-based approaches
improvement of actual best solution
- deterministic approaches
- stochastic approaches
examples of improvement heuristics
2-opt for TSP
Tabu Search
Simulated Annealing
Genetic Algorithms
Fix&Optimize Heuristic
What is the standard technique for solving MIPs exactly, that is integrated in commercial software for solving MIPs?
Branch-and-Bound method
What is the idea of approach of the B&B-method?
Systematic search in set of feasible solutions —> optimal solution will be among them
Using bounds to exclude suboptimal solution early during enumeration
Basic principles of B&B
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
What does the LP relaxation for the Knapsack Problem look like?
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’.
How do you get the upper and the lower bound for the B&B algorithm for the Knapsack problem?
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).
What is the optimal solution of the initial problem (of B&B)?
Best solution of a subproblem
What are the three discarding rules (for maximization problems)?
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
What is the goal of rules of order for problems to be considered?
Early determination of the optimal solution (minimization of the decision tree)
Which are the two most common rules for processing order of the candidate list in B&B?
Depth-first search: LIFO rule (last-in first-out)
Breadth-first search: MUB rule (maximum-upper-bound)
What is the outline of the LIFO rule?
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)
Outline of MUB rule?
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.
Advantages and disadvantages of LIFO and MUB
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
