CMSC 451 Linear Programming Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Linear Programming Suppose you are given A matrix A with m rows and n columns A vector b of length n A vector c of length n Find a length n vector x such that A x b and so that c x n X j 1 is as large as possible cj xj Linear Algebra The matrix inequality A x b in pictures Each row of A gives coefficients of a linear expression P j aij xj Each row of A along with an entry of b specifies a linear inequality P j aij xj bi A little more general maximize X cj xj j subject to A x b What if you want to minimize What if you want to include a constraint a i x bi What if you want to include a constraint A little more general maximize X cj xj j subject to A x b What if you want to minimize Rewrite to maximize P j cj xj What if you want to include a constraint a i x bi What if you want to include a constraint A little more general maximize X cj xj j subject to A x b What if you want to minimize Rewrite to maximize P j cj xj What if you want to include a constraint a i x bi Include the constraint ai x bi instead What if you want to include a constraint A little more general maximize X cj xj j subject to A x b What if you want to minimize Rewrite to maximize P j cj xj What if you want to include a constraint a i x bi Include the constraint ai x bi instead What if you want to include a constraint Include both the and constraints Hence we can use and constraints and maximize if we want History of LP Algorithms The Simplex Method Oldest method Not a polynomial time algorithm for all proposed variants there are examples LPs that take exponential time to solve Still very widely used because it is fast in practice The Ellipsoid Method Discovered in the 1970s First polynomial time algorithm for linear programming Horribly slow in practice and essentially never used Interior Point Methods Polynomial Practical In Practice There is lots of software to solve linear programs CPLEX commercial seems to be the undisputed winner GLPK GNU Linear Programming Solver this is what we will use COIN OR CLP Another open source solver NEOS server http www neos mcs anl gov Even Microsoft Excel has a built in LP solver though may not be installed by default What is Linear Programming Good For Maximum Flow Maximum Flow Given a directed graph G V E capacities c e for each edge e and two vertices s t V find a flow f in G from s to t of maximum value What does a valid flow f look like 0 f e c e for all e P u v E f u v P v w E for all v V except s t f v w Maximum Flow as LP Create a variable xuv for every edge u v E The xuv values will give the flow f u v xuv Then we can write the maximum flow problem as a linear program X maximize xuv u t E subject to 0 xuv cuv X X xuv xvw u v E for every u v E for all v V s t v w E The first set of constraints ensure the capacity constraints are obeyed The second set of constraints enforce flow balance Maximum Flow as MathProg set V set E within V cross V param C u v in E 0 param s in V param t in V rep vertices rep edges capacities source sink var X u v in E 0 C u v var for each edge maximize flow sum u t in E X u t subject to balance v in V setminus s t sum u v in E X u v sum v w in E X v w solve printf u v in E X u v 0 s s f u v X u v end General MathProg Organization Declarations Objective Function Constraints Output Maximum Flow Data The model on the previous slide can work any graph and capacities The data file of the MathProg program gives the specific instance of the problem Support your graph was this 2 4 7 1 6 2 3 1 1 4 6 4 3 10 5 7 Maximum Flow Data data set V 1 7 set E 1 2 1 3 1 4 2 4 2 7 3 5 4 6 4 5 5 7 6 7 param C 1 2 3 4 5 6 7 1 3 1 7 2 2 6 3 9 4 1 5 4 6 4 7 param s 1 param t 7 end Maximum Bipartite Matching People Tasks a 1 b 2 c 3 d 4 e 5 L R Maximum Bipartite Matching Given a bipartite graph G V E choose as large a subset of edges M E as possible that forms a matching The red text gives an objective function The blue text gives constraints Maximum Bipartite Matching set A set B set E within A cross B a bipartite graph var X e in E 0 1 variable for each edge maximize numedges sum u v in E X u v s t matchA u in A sum u v in E X u v 1 s t matchB v in B sum u v in E X u v 1 end Bipartite Matching Data data set A a b c d e f set B 1 5 set E 1 2 3 4 5 a b c d e f end Integer Linear Programming If we add one more kind of constraint we get an integer linear program ILP X maximize cj xj j subject to A x b xi 0 1 for all i 1 n ILPs seem to be much more powerful and expressive than just LPs In particular solving an ILP is NP hard and there is no known polynomial time algorithm and if P6 NP there isn t one However because of its importance lots of optimized code and heuristics are available CPLEX and GLPK for example provide solvers for ILPs Minimum Vertex Cover Minimum Vertex Cover Given graph G V E choose a subset of vertices C V such that every edge in E is incident to some vertex in C Why is this useful In a social network choose a set of people so that every possible friendship has a representative On what nodes should you place sensors in an electric network to make sure you monitor every edge Vertex Cover as an ILP Create a variable xu for every vertex u in V We can then model the vertex cover problem as the following linear program X minimize xv v V subject to xu xv 1 xu 0 1 for every …