Integer Program Optimization: Algebraic Geometry

1 Chapter 6 1.1 Summary Slide 1 • Lattices - Discrete approach to integer optimization • Solve in polynomial time: – Is set S empty? (Theorem 6.4) S = {x ∈ Z n |Ax = b} – Integer Optimization problem with fixed dimension n (Algorithm 6.6) max c� x s.t. Ax = b 0≤x≤u x ∈ Z n. 1.2 Solves Efficiently... c� x Ax = b 0≤x≤u x ∈ Zn max s.t. Slide 2 where A ∈ Z m×n , b ∈ Z n • What can we say about m and n? • Meaning of solving in polynomial time when n is fixed. • Is it a practical algorithm? (c.f. ellipsoid algorithm for LP) • What are the limiting factors? – integral A, b?, x +ve?, Ax = b? fixed dimension n? • Geometrical picture 1.3 Theorem 6.5 Slide 3 Integral Farkas Lemma Let A ∈ Z m×n , b ∈ Z m and S = {x ∈ Z n |Ax = b} 1. S = ∅ if and only if there exists a y ∈ Qm , such that y� A ∈ Z m and y� b is not in Z m 2. S = ∅ if and only if there exists a y ∈ Qm , such that y ≥ 0, y� A ∈ Z m and y� b is not in Z m 1.4 Key Insight max s.t. c� x Ax = b 0≤x≤u x ∈ Zn Slide 4 versus 1 max s.t. c� x Ax = b x ∈ Zn Presence of bounds fundamentally changes the character and complexity of the under­ lying problem. Without bounds, polynomially solvable. With bounds, polynomial in fixed dimensions, but in general N P-hard. Is problem with Ax = b, x unbounded easy? What about Ax ≤ b 2 Chapter 7 2.1 Summary Approaches based on algebraic geometry • Grobner basis-based algorithms Slide 5 – Finite for both binary (Algo 7.2) and IO (Algo 7.3) – Farkas Lemma for IO (Theorem 7.9) – Good when the feasible set is small. • Semidefinite relaxation – Convergent sequence; in case of binary, exact. • Counting number of integer points in polyhedron (Algo 7.5) – Polynomial in fixed dimensions. 3 Chapter 8 3.1 Summary Slide 6 Integral Generating Set • • • • Provides optimality conditions Characterization of integral polyhedra (TDI) Cutting planes Potential improving directions 2 3.2 Optimality Conditions Theorem 8.5: A feasible solution x is optimal if and only if for every h one of the two conditions holds: Slide 7 • c� h ≤ 0 • c� h > 0 and x �∈ P When do we make use of this property? 3.3 Totally Dual Integral Slide 8 Dual : min s.t. � by A� y = c y≥0 Theorem 8.10: A� x ≤ b is TDI if and only if for every c ∈ Z such that dual is bounded, it has an integral optimal solution. Theorem 8.11: If A� x ≤ b is TDI, then {x ∈ Rn | A� x ≤ b} is integral. 4 Chapter 9 4.1 Summary Cutting plane methods using geometric ideas: Slide 9 • Integral generating sets – Method produces optimal solution, but integral generating set is hard to compute – Gomory cutting plane is a special case • Lattices 4.2 Algorithm 9.1 n C = {x ∈ R |x = Slide 10 � i∈I yi ai , yi ≥ 0, ∀i ∈ I} h�1 x ≤ �h�1 xt � 4.3 Algorithm 9.2 Slide 11 (z + �(z)− �)� At x ≤ �(z + �(z)− �)� b� 3 4.4 P 1, P t P 1 = {x ∈ Rn | c� x ≤ �δ� for all supporting hyperplanes {x ∈ Rn | c� x = δ} of P with c integral } Theorem 9.4: Let P = {x ∈ Rn | Ax ≤ b} be a nonempty polyhedron with A integral and Ax ≤ b totally dual integral. Then, P 1 = {x ∈ Rn | Ax ≤ �b�} P t+1 = (P t )1 Theorem 9.5: Let P be a rational polyhedron. Then, there exists a natural number t ∈ Z+ with P t = conv(F ) Compare with Theorem 9.1 5 Slide 12 Chapter 10 5.1 Integral Basis Method • Systematic way to reformulate problem by introducing new variables for the problem dynamically. – When are variables introduced? – How many variables are introduced? 4 Slide 13 • Provide in finite time an exact linear optimization formulation of an integer optimization problem. – What is the linear optimization formulation derived? • Extension of simplex algorithm to handle integer case. • Discrete relaxation – General, knapsack relaxation or database approach 6 Chapter 10 6.1 Algorithm 10.2 1. Compute bounds and make problem a bounded one. 2. If optimality conditions not met, do: (a) Choose column with positive reduced cost. (b) Measure simplex step size θ∗ . (c) If θ∗ = 1, take it and go to 2. 5 Slide 14 (d) If θ∗ > 1, apply gomory cut (with slack variable if necessary), take integral step, and go to 2. (e) If 0 ≤ θ∗ < 1, reformulate problem using integral generating sets. 3. Return optimal. 7 Chapter 11 7.1 Summary Slide 15 1. Branch and bound (and cut) 2. Optimization based heuristic methods 3. Dynamic programming and approximate dynamic programming 4. Local search methods 5. Simulated annealing • Guaranteed to find optimal solution? • High level implementation details • How/why does method work/not work? • Benefits/shortcomings of methods 6