Optimization Methods - Recitation 7 | Massachusetts Institute of Technology

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

2023
Views:

193

Pages:

2
Author:

bartlettsholeoh

Recitation 7 1 Network Simplex Algorithm Network simplex algorithm components 1. Basis solution: a spanning tree solution. How to calculate the basic solution given a spanning tree? Consider the node n as the root node, the basis (collection of arcs in the spanning tree) matrix can be arranged to become a lower triangular matrix. The basis solution B−1 b is then can be calulated from the leaves upwards. 2. Reduced costs: c̄ij = cij − (pi − pj ), where pi is node ’potentials’. How to calculate the node potentials? Let pn = 0, calculate other node potentials using arcs in the current tree solution with the formula cij − (pi − pj ) = 0 (why is that?) from the root to leaves. 3. Simplex direction: involve a cycle created by an entering arc with arcs in the current tree solution. How to decide moving distance θ ∗ ? Push as many ﬂows as possible along the cycle in the entering arc’s orientation (keep all other ﬂows nonnegative). Example 1 BT 7.10 1. Calculate the basic solution? Is it a feasible solution? 2. Find the reduced costs 3. Is this basic solution optimal? 4. Is there a nondegenerate basic feasible solution? 5. Find an optimal dual solution? 6. Increase c56 how much so that the current solution is still optimal? 7. Change a small supply δ at node 1 and demand at node 9, how much is the change in cost? 8. Special structure of the problem? 1 2 Integer Programming Formulations The quality of a formulation of an integer programming problem can be judged by the closeness of the linear relaxation polyhedron to the convex hull of the set of all feasible solution of the problem. Question 1 Write down two formulations for the facility location problem: aggregate and normal formulations. Prove that ZAF L ≤ ZF L ≤ ZIP . Question 2 Write down two formulations for the minimum spanning tree problem: subset and cutset formulations. Prove that Zcut ≤ Zsub ≤ ZIP . Example 2 BT 10.5 n items of size aj , a truck of size Q, m boxes of sizes bi . Decide whether the move is possible. Example 3 BT 10.9 The ﬁxed charge network design problem: directed network, each node has a demand or supply of bi , each arc has a transportation cost cij , a building cost uij , and a capacity uij . Build the network and route ﬂows within the network so that all demands are satisﬁed with the minimum total cost. 2