Integer Program Combination Optimization - Recitation Notes for Ideal Formulations III

1 Chapter 1 1.1 Modeling Techniques General rules to express a valid formulation Slide 1 • Understand the constraints and objective function stated! • Find best expression showing valid formulation, compactness secondary consid­ eration. • Often, most natural definitions is the best definition. • Try to minimize logical variables and forcing constraints. • Is formulation linear! Once nonlinear, need to prove convexity. • No constraints with > or < constraints. 1.2 Strength of Formulations Let IZ be the convex hull of the IO (i.e. integral extreme points), Zi polyhedra of relaxation under valid formulation i. Slide 2 • If IZ ⊆ Z1 ⊆ Z2 , Z1 is a stronger formulation than Z2 . Stronger means the optimal objective value under Z1 is a better bound. • When we get an integral solution when solving relaxed problem, have we solved the IO? Is the problem polynomially solvable (belonging to class P)? • If valid formulation describes the IZ exactly, we can solve the problem easily. Is the problem polynomially solvable? • If Z1 only have integral extreme points, is Z1 = IZ? 1.3 Summary • A good formulation can have an exponential number of constraints. Slide 3 • Conjecture: The convex hull of problems that are polynomially solvable are explicitly known. Formulations characterize the complexity of problems. • If convex hull is known, problem is polynomially solvable. How to solve it? • Several problems (MST, TSP, etc) are discussed. Useful to know which problems are easy, which are hard. 2 Appendix A 2.1 Summary • Vectors x1 , . . . , xk are affinely independent if and only if x2 − x2 , . . . , xk − x2 are linearly independent. • P has dimension k ⇐⇒ ∃ k + 1 affinely independent points in P . • Facet F has dimension dim(P ) − 1. • Theorem A.1: 1 Slide 4 – For each facet F , at least one of the inequalities representing F is necessary in description of P . – Every inequality representing a face F , where F is not a facet, is not necessary in the description. 3 Chapter 2 3.1 Enhancing Formulations When does a valid inequality improve a formulation? Slide 5 Methods to generate valid inequalities • Rounding • Superadditivity • Modular Arithmetic • Disjunctions • Mixed Integer Rounding 3.2 Facet Defining Inequalities • General techniques do not necessarily yield the high dimensional faces of the convex hull of a set of integral solutions. Slide 6 • Lifting technique of deriving a higher dimensional face from a lower one. Since we can increase the dimension, we have a way to improve the valid inequalities but: – Computing coefficients step by step is expensive – Order of lifting matters. (Potentially exponential growth) – One may need to solve a couple of IO in performing the procedure! 3.3 Independence Systems Slide 7 N finite set, I collection of subsets of N • (N , I) is an independent system iff 1. ∅ ∈ I; 2. if A ⊆ B and B ∈ I, then A ∈ I. • Basis of T : Independent set (IS) of max cardinality in T ⊆ N • Maximum cardinality of a basis of T , denoted by r(T ) is called the rank of T . • Circuits C is dependent set F ⊆ N such that, ∀i ∈ F , F \{i} is independent. • Polyhedron of (N , I), PI := conv{xF : F ∈ I} 2 3.4 Cont. Slide 8 max s.t. � cx � x ≤ |C | − 1 i∈C i x ∈ {0, 1}n . • Rank inequality (RI): � i∈T ∀C ∈ C xi ≤ r(T ) = |CT | − 1 • RI is facet defining under some conditions. • Matroid: an independence system where every maximal IS in F has same car­ dinality r(F ) for all F ⊂ N . How about |C |, ∀C ∈ C? • For matroids, PI is completely characterized by RI. Are matroid problems easy? Do we know PI of all independence systems? 3.5 Nonlinear Formulations Slide 9 • Observations: – Variables taking values in {0, 1} can be expressed as x2 = x. – It may be easier to express constraints as xi xj = 0, for example. • Incorporating them leads to: – Semidefinite constraints and relaxations – More general nonlinear problems 3.6 Summary • While only facet defining inequalities are required to describe P , it is hard to identify them. It is also hard to prove that a valid inequality is facet­defining. Slide 10 • Therefore, general valid inequalities are used instead. • Importance of valid inequalities has been demonstrated. • Improved formulations can involve nonlinear (still convex) constraints or expo­ nential number of constraints. 4 Chapter 3 4.1 Ideal Formulations Slide 11 Central question: When do we have an integral polyhedron? Total Unimodularity Corollary 3.1: A is totally unimodular if and only if {x|a ≤ Ax ≤ b, l ≤ x ≤ u} is integral ∀ integer vectors a, b, l, u. When is A totally unimodular? • Definition 3.1 3 • Proposition 3.2 • Theorem 3.2 • Corollary 3.2 Implications: Theorem 3.3 ­ list of easy problems 4.2 Dual Methods Slide 12 Proposition 3.4: Given P is nonempty with at least 1 extreme point: ∀c ∈ Z n P integral ⇐⇒ ZLP integral, Since ZD ≤ ZLP ≤ ZIP ≤ ZH , if for general integral c, we have feasible solutions to primal and dual (relaxed) problems, and ZD = ZH , P is integral. 4.3 Polymatroid P (f ) Slide 13 Consider max s.t. � x c� x ≤ f (S) j∈S j n x ∈ Z+ . ∀S ⊂ N where N is finite set {1, . . . , n}. Let F be set of feasible integer solutions and P (f ) is the feasible region of relaxed problem. Theorem 3.4: If f is submodular, nondecreasing, integer valued, and f (∅) = 0, then P (f ) = conv(F ). � Similar results for integer valued. 4.4 j∈S xj ≥ f (S) and f (S) is supermodular, nondecreasing and Cont. Slide 14 Matroid is independence system where r(T ) is submodular. Matroid problems can be solved efficiently using a greedy algorithm. Intersection of polymatroid polyhedra: max s.t. � x c� �j∈S xj ≤ f1 (S) x ≤ f2 (S) j∈S j n x ∈ Z+ . P = {x ∈ Rn +| � j∈S ∀S ⊂ N ∀S ⊂ N xj ≤ min(f1 (S), f2 (S)), ∀S ⊂ N } is integral if fi (S) are sub­ modular, nondecreasing, integer valued, and fi (∅) = 0. 4 4.5 Other Techniques • Randomized Rounding E[c� x] = ZLP = c� x∗ for arbitrary c Slide 15 • Minimal Counterexample Show P \ conv(F ) = ∅. • Lift and Project Systematic way to reduce polyhedron to integral convex hull for binary opti­ mization problems. Given integral P , ­ must P be unbounded? ­ when is the feasible region to the dual problem (of the relaxed LP) integral? 4.6 Summary • Given integral P , if LP can be applied, integral solution can be obtained readily. Slide 16 • Given integral P , efficient combinatorial algorithms (for example, greedy algo­ rithms) may be derived. • From complexity point of view, integral formulations with polynomial number of variables and constraints can be solved efficiently by applying a polynomial interior point algorithm. • Even if number of constraints is exponential, efficient methods proving solvabil­ ity in polynomial time may be derived. 5 5.1 Chapter 4 Duality Dual problem provides a lower bound (weak duality) to the cost of integer optimization problem. Given a cost of a primal feasible solution, this can be used as a measure of optimality. Binary IO Duality The lift and project method in Section 3.5 leads to explicit dual problem of exponential size for binary optimization problems for which strong duality holds. 5.2 Slide 17 Lagrangean Duality Slide 18 Let ZIP be the optimal value to min s.t. c� x Ax ≥ b Dx ≥ d x ∈ Z n. and let X = {x ∈ Z n |Dx ≥ d} and Z(λ) be the optimal value to min s.t. c� x + λ� (b − Ax) x∈X 5 Proposition 4.4: ­ Z(λ) ≤ ZIP ∀λ ≥ 0. ­ Z(λ) is concave in λ 5.3 Lagrangean Dual Let ZD be the optimal value to the Lagrangean Dual max s.t. Slide 19 Z(λ) λ≥0 Theorem 4.8: ZD ≤ ZIP Theorem 4.9: ZD = optimal cost of min s.t. 5.4 c� x Ax ≥ b x ∈ conv(X) ZIP = ZD min s.t. Slide 20 c� x Ax ≥ b Dx ≥ d x ∈ Zn min s.t. where c� x Ax ≥ b x ∈ conv(X) X = {x ∈ Z n |Dx ≥ d} Corollary 4.1 a) ZIP = ZD for all c if and only if conv(X ∩ {x|Ax ≥ b}) = conv(X) ∩ {x|Ax ≥ b}. 5.5 Z = ZD min s.t. Slide 21 c� x Ax ≥ b Dx ≥ d x ∈ Rn min s.t. where c� x Ax ≥ b x ∈ conv(X) X = {x ∈ Z n |Dx ≥ d} Corollary 4.1 ab) Z = ZD for all c if and only if conv(X) = Dx ≥ d. What about Z = ZD = ZIP ? 6 5.6 Subgradient Optimization • Method for finding the optimal Lagrange multipliers λ∗ solving the Lagrangean dual Slide 22 • Modified from steepest ascent method from nonlinear optimization • Modification required as Z(λ) is not always differentiable. Is this problem polynomially solvable? 5.7 Summary • Binary IO duals exponential in dimension of problem. Slide 23 • Lagrangean only leads to weak duality but: – Provides bounds to IO that are critical in enumerative approaches to solv­ ing them – Always as least as good and often much better than LP relaxation – Provides an often effective approach to solving linear relaxation via use of subgradient methods 6 Chapter 5 6.1 Ellipsoid Method • Solves linear optimization problems involving an exponential number of con­ straints in polynomial time under certain conditions (boundedness and full­ dimensionality). Slide 24 • Problems not meeting the conditions can be modified accordingly. • For optimization problem: – Finding feasible point where strong duality is met. – Sliding objective ellipsoid method. • More of a tool to classify complexity of linear optimization problems. 6.2 Separation / Optimization Definition 5.5 Given P and x, the separation problem is to: 1. Either decide is x ∈ P , or 2. Find a vector d such that d� x < d� y for all y ∈ P . Theorem 5.5 If we can solve the separation problem efficiently, then we can also solve the linear optimization problems efficiently. Note: Converse is true as well. 7 Slide 25