Optimization Methods - Recitation 8 | Massachusetts Institute of Technology

University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

249

Pages:

2
Author:

Sonny Collins

Recitation 8 1 Exact Algorithms for Integer Programming Problems 1.1 Cutting plane methods 1. Solve the linear relaxation, x∗ is the optimal solution 2. If x∗ is integer, then x∗ is the optimal solution of the integer programming problem 3. If not, add a linear inequality constraint that is satisﬁed by all integer solutions but not x∗ Gomory cut Given an optimal simplex tableau of the linear relaxation, if all basic variables are integer, the optimal solution for the integer programming problem is obtained. If not, consider the equality constraint xi + (B−1 Aj )i xN = (B−1 b)i . The Gomory cut is then the rounding cut applied on this constraint. Arithmetic �Modular �n n i=1 bi xi ≥ b0 , where bi = ai mod d, d is an abitrary integer i=1 ai xi = a0 can lead to the inequality and x ∈ Rn+ . Example � Consider the matching problem, e∈δ({i}) xe ≤ 1. Prove that for a set S with odd cardinality, the � 1 inequality e∈E(S) xe ≤ 2 (|S| − 1) is valid. Solution � � � � � Using the formula 2 e∈E(S) xe + e∈δ(S) xe = i∈S e∈δ({i}) xe , we obtain the inequality e∈E(S) xe + 1� 1 e∈δ(S) xe ≤ 2 |S|. 2 � 1 |S| is odd and xe ≥ 0, thus we have: e∈E(S) xe ≤ 2 (|S| − 1). 1.2 Branch and bound 1. Partition: the feasible set F is partitioned into a ﬁnite collection of subsets Fi . These subsets are the feasible sets of corresponding subproblems. 2. Branching: splitting the current subproblem into further subproblems, a tree of subproblems is created. 3. Bounding: calculate the lower bound for the optimal cost of a subproblem b(Fi ) ≤ minx∈Fi c x. Linear relaxation or Lagrangian relaxation can be used. 1 4. Pruning: subproblem is infeasible or b(Fi ) ≥ U , where U is the best feasible solution so far (starting with ∞). 5. Additional cuts: valid cut could be added to the subproblem to improve the lower bound. 2 Integrer programming duality Primal problem min c x s.t. Ax ≥ b x∈X Relax the constraints Ax ≥ b with Lagrange multiplier p, we obtain the problem Z(p) = min c x + p (b − Ax) s.t. x∈X Property: Z(p) is a piecewise concave function. The Lagrange dual problem ZD = max Z(p) p≥0 We then have: min s.t. c x Ax ≥ b x ∈ CH(X) Weak duality ZD ≤ ZIP How about strong duality for linear programming problem? Subgradient method: motivated from the steepest ascent method, pt+1 = pt + θt st , where st ∈ ∂Z(pt ). 2