Linear Program Duality and Algorithms
Explore the duality concept in linear programming, with examples and solutions. Learn about the simplex and ellipsoid algorithms for solving graph problems efficiently. Discover the key principles behind these algorithms, including basic feasible solutions and running times.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Duality for Linear Programs Consider the following LP: min2?1 3?2+ ?3 ?1 ?2 1 ?2 2?3 2 ?1 ?2 ?3 7 ?1,?2,?3 0 Question: How can I prove to you that optimal solution is at most -1? Answer: You can check (4, 3, 0) Question: How to prove the optimal is at least -1?
Dual LP min2?1 3?2+ ?3 ?1 ?2 1 ?2 2?3 2 ?1 ?2 ?3 7 ?1,?2,?3 0 max?1+ 2?2 7?3 ?1 ?3 2 ?1+ ?2 ?3 3 2?2 ?3 1 ?1,?2,?3 0 Solution: y = (2.5, 0, 0.5)
Dual LP min ?,? ?? ? ? 0 max ?,? ? ? ? ? 0 Primal Constraints Variables Feasible solution gives an upper bound. Dual Variables Constraints Feasible solution gives a lowerbound. Strong Duality: The two LP has the same optimal value.
Using LP to solve graph problems 1 2 1 2 3 3 1 2 4 5 6 4 1 1 3 2 7 8 9 1 1
LP algorithms Simplex Ellipsoid Interior Point
Simplex Algorithm Recall: geometric interpretation Basic Feasible Solution: A vertex in the polytope. Algebraic interpretation: Solution of n tight constraints. Claim: There is always an optimal basic feasible solution.
Simplex Algorithm [Dantzig 1947] Idea: Start from a basic feasible solution, follow an edge in the polytope. Algorithmically: follow an edge swap a constraint. Many ways to decide which constraint to swap.
Running time of Simplex algorithm Each move takes polynomial time, but how many moves do we need? In the worst case can require 2n moves. But in practice simplex is often very fast! Still used in many LP solvers.
Ellipsoid algorithm First idea: finding a feasible solution finding optimal solution. y x
Running time of ellipsoid Polynomial in the number of variables and constraints. Actual running time is a bit slow, often used for low dimensional problems.
Interior Point algorithms Idea: Build barrier functions for constraints. y x Barrier: Reach infinity at boundary, but small when far from boundary.
Interior Point algorithms Idea: First find the optimal solution for objective + all barrier functions. y x Gradually decrease the barrier functions to make the point closer to the actual optimal.
Running time for Interior point Also polynomial in number of variables and constraints. Can be implemented efficiently in practice. Many recent developments in both theory and practice, becoming the method of choice in many LP solvers.
