際際滷

際際滷Share a Scribd company logo

Random Simplex for operation research.ppt

Download as PPT, PDF
M
mohammedsaaed1

This document summarizes a randomized polynomial-time simplex algorithm for linear programming. The algorithm introduces randomness to overcome the exponential worst-case running time of the deterministic simplex method. It works by first running the shadow vertex simplex algorithm on a randomized input. If the optimal is not found, it transforms the coordinates and runs the algorithm again, guaranteeing a polynomial running time with high probability by avoiding "bad" inputs that cause exponential behavior deterministically.

1 of 30
Download to read offline
A Randomized Polynomial- Time Simplex Algorithm for Linear Programming CS3150 Course Presentation
Linear Programming Example: 鐔Find the maximum value of p = 3x - 2y + 4z 鐔subject to 鐔4x + 3y - z >= 3 鐔x + 2y + z<=4 鐔 x >= 0, y >= 0, z >= 0
Linear Programming Objective Function max zT x Constraints s.t. A x y
Simplex Method - Intuition Objective: Min C = 3x + 4y Constraints: 鐔3x - 4y <= 12, 鐔x + 2y >= 4 鐔x >= 1, y >= 0.
Simplex Method - Intuition max zT x s.t. A x y Worst-Case: exponential Average-Case: polynomial Widely used in practice
Shadow Vertices
Shadow vertex pivot rule objective start z
Complexity Landscape
Complexity Landscape of Perturbed Problem
Some issues Problem max zT x s.t. A x y The perturbed problem is no longer the original problem we want to solve! Solution Reduce the original problem to another problem, where the perturb wont affect solution. Is this set of constraints bounded? Aw<=1
Intuition of the Algorithm Since the right hand side wont affect solution, we want to carefully choose it so that the Shadow-Vertex Simplex will run poly-time with high probability.
Intuition of the Proof P is the polytope of Aw<=1 Case 1: The polytope P is in k-near-isotropic position
K-near-isotropic position
Intuition of the Proof Case 1: The polytope is in k-near-isotropic position Case 2: The polytope is not in k-near-isotropic position
K-near-isotropic Case Upper bound of total shadow length (Shadow Size). Lower bound expected length of each edge. Number of edges of the shadow is poly in size w.h.p.
K-near-isotropic position
Randomization Each of vector is a independently exponentially distributed random variable with expectation Project onto a random plane
None-K-near-isotropic Case By Running the shadow vertex for a limited amount of time we can either: Find the optimal Or find a way to eliminate bad events w.h.p.
None-K-near-isotropic Case
K-near-isotropic Case Upper bound of the total shadow length. Lower bound the expected length of each edge. Number of edges of the shadow is poly in size w.h.p.
Upper Bound of Shadow Size Aw<=1 Aw<=1+r
Shadow Size in Case 1 The expected shadow size is at most:
Upper Bound of Shadow Size
K-near-isotropic Case Upper bound of the total shadow length. Lower bound the expected length of each edge. Number of edges of the shadow is poly in size w.h.p.
Expected Edge Length The Expected Edge Length is at least:
Case 1 Main Theorem The expected number of edges is at most
None-K-Isotropic Case The expected shadow size inside any given ball is small
None-K-near-Isotropic Case Upper bound of the total shadow length within the given ball. Lower bound the expected length of each edge within the given ball. Number of edges of the shadow is poly in size w.h.p.
Outline of the Algorithm Run Shadow Vertex Simplex on the Randomized Input If Find Optimal then halt Else transform the coordinates and run shadow vertex simplex on the transformed inputs Algorithm will halt in poly-time w.h.p.
Summery and Intuitions Deterministic algorithms run exponential time on some bad inputs By introducing some randomness into the algorithm fixed the problem. The Randomized algorithm run poly time on all inputs with high probability. Start with something strict, which is easy to prove the poly-bound, eliminate the bad events in poly-time.

More Related Content

Random Simplex for operation research.ppt