Integer programs solvable as LP Sommer Gentry November 18, 2003 Transportation problem ? ? 50 widgets Baltimore Detroit Atlanta Denver Pittsburgh Boston Houston 20 widgets 30 widgets 75 widgets 40 widgets 20 widgets 15 widgets $9 $7 $4 Sources and sinks connected by links Objective: Minimize shipment cost Assignment problem ? ? Manny Valves Moe Jack Carburetor Tires Fluids 9 minutes 7 minutes 4 minutes Transportation LP , ... ... ... ...Subject to .........Maximize 11 21 112111 21 111211 112121111111 tt      || mn ji nmnnn m mmnmm n mnmnnnnn xx ba bxxx bxxx axxx axxx xcxcxcxcxcZ    Supplies Demands Persons and tasks connected by links Objective: Minimize total task time .0,0 Basis theory ? as the number of constraints. The simplex algorithm only searches feasible bases by design, but any set of m variables is not guaranteed to form a feasible basis. subject to: -2/3x2+ x3 +1/3x5 = 4 x2 +x4 = 0 x1 +2/3x2 + 3x5 = -2 x1 >0, …, x5 >0 Find a starting basic feasible solution ? have all less-than inequalities. In these cases the starting feasible basis is obvious: all the slack variables are basic and the others non-basic. How can we find a feasible basis if given equality constraints? , ... ...Subject to ...Maximize 1 11 11111 11 tt    n mnmnm nn nn xx bxaxa bxaxa Z   Every basis contains the same number of variables The simplex algorithm examples shown so far .0,0 xcxc Courtesy of Sommer Gentry. Used with permission. Answer: write this as a new LP! ? artificial variable. Objective: Minimize the sum of the artificial variables. b i 0.0, ... ...Subject to ...Minimize 11 11 111111 1 tttt        mnnn mmnnmnm nnn mnn xxxx bxxaxa bxxaxa xxZ   Phase I of simplex algorithm ? general simplex algorithm. Note that an inconsistent system of equations will be revealed as such by a positive Phase I optimum. Thus, LP can function as a check for consistency of linear systems of equations. ? point solution found in Phase I. Add to each equation one – Multiply by –1 if necessary to find positive ,0,0 The new LP on the previous slide is phase I of the Phase II uses as a starting basis the feasible corner Transportation Basis ? m+n equations in a transportation problem, but one row is dependent so there are m+n-1 rows in each simplex tableau. ? mn-(m+n-1) zero, equations can be reordered triangularly. ? integers, every corner point solution is integer. Integer basic feasible solutions nklmlmk mklmljkikij klmljklkijjk bxxx axxxxx axxxxxx    ... ... 1  There are Theorem: All bases are triangular. – with nonbasic variables set to Theorem: If supplies and demands are Proof: All bases are triangular ? variable variables. Let k be the number of basic variables. Then there are at least 2n basic variables in the supplies section, and at least 2m basic variables in the demands section, thus k >2n , k >2m , so k >m+n. But since there are only m+n-1 independent equations, there is a contradiction. Proof: All bases are triangular ? from the original system leaves an equation in exactly one basic variable. – equation. Let k’ be the new number of basic variables. Again make the contrary assumption to get k’ >2(n-1) , k >2m. There was at least one basic entry in the equation excluded, so k >k’+1. Then k >m+n-1/2, which again contradicts k <m+n-1. ? basic variable and repeat the argument for the reduced array, establishing the theorem. Lemma: Some row has exactly one basic – Assume each row has at least two basic Lemma: Exclusion of any redundant equation Drop some equation as redundant, say, the last demand Then, successively delete the row having a single Network optimization ? network optimization problem. More complex problems include transshipment nodes, arc capacities, and nonlinear objective functions. Network optimization is a well-developed computer science field offering specialized algorithms and approximation techniques for myriad practical problems. Shortest paths, maximum flow, traveling salesman problem, minimal delay routing problems are further examples. The transportation problem is the simplest