Linear Programming

Contents

Back to Constrained Optimization or Continuous Optimization

Basic Concepts

The general form of a linear programming (LP) problem is to minimize a linear objective function of continuous real variables subject to linear constraints. For the purposes of describing and analyzing algorithms, the problem is often stated in standard form as
\[ \begin{array}{lll}
\min & c^T x & & \\
\mbox{s. t.} & A x & = & b \\
& x & \geq & 0
\end{array}
\]
where \(x\) is the vector of unknown variables, \(c\) is the cost vector, and \(A\) is the constraint matrix. The matrix \(A\) is generally not square; therefore, solving the LP is not as simple as just inverting the \(A\) matrix. Usually \(A\) has more columns than rows, which means that \(A\) is likely to be under-determined; as a result, there is great latitude in the choice of \(x\) that will minimize \(c^T x\) over the feasible region.

The feasible region is a polyhedron determined by the set
\[\{x \in \mathbb{R}^n \, | \, Ax = b, x \geq 0\}.\]
Any specification of values for the decision variables is a solution; a feasible solution is a solution for which all the constraints are satisfied. An optimal solution is a feasible solution that has the smallest value of the objective function for a minimization problem. An LP may have one, more than one or no optimal solutions. An LP has no optimal solutions if it has no feasible solutions or if the constraints are such that the objective function is unbounded. For more information about detecting and diagnosing infeasibility, see Topics in Linear Programming.

In a linear program, a variable can take on any continuous (fractional) value within its lower and upper bounds. For many applications, fractional values do not make sense. Integer programming (IP) problems are optimization problems in which the objective function and all of the constraint functions are linear but some or all of the variables are constrained to take integer values. Integer programming problems often have the advantage of being more realistic than linear programming problems but they have the disadvantage of being much more difficult to solve. While it may not be obvious that integer programming is a much harder problem than linear programming, it is both in theory and in practice. The most widely used general-purpose techniques for solving IPs use the solutions to a series of LPs to manage the search for integer solutions and to prove optimality. For more information, see Integer Linear Programming and its related pages.

Solution Techniques

The importance of linear programming derives both from its many applications and from the existence of effective general purpose techniques for finding optimal solutions. These techniques are general purpose in that they take as input an LP and determine a solution without reference to any information concerning the origin of the LP or any special structure of the LP. They are fast and reliable over a substantial range of problem sizes and applications.

Although all linear programs can be converted to standard form, it is not usually necessary to do so to solve them. Most LP solvers can handle other forms such as

  • general bounds: \(l \leq x \leq u\), where \(l\) and \(u\) are vectors of known lower and upper bounds
  • two-sided constraints: \(b_1 \leq Ax \leq b_2\) for arbitrary \(b_1\) and \(b_2\)
  • maximization problems: vector \(c\) is multiplied by -1

There are two families of techniques in wide use today, simplex methods and barrier or interior point methods. Both techniques generate an improving sequence of trial solutions until a solution is reached that satisfies the conditions for an optimal solution. Simplex methods were introduced by George Dantzig in the 1940s. Simplex methods visit basic solutions computed by fixing enough of the variables at their bounds to reduced the constraints \(Ax = b\) to a square system, which can be solved for unique values of the remaining variables. Basic solutions represent extreme boundary points of the feasible region defined by \(Ax = b\), \(x >= 0\), and the simplex method can be viewed as moving from one such point to another along the edges of the boundary. For more information, see the Simplex Method.

Barrier or interior-point methods by contrast visit points within the interior of the feasible region. These methods derive from techniques for nonlinear programming that were developed and popularized in the 1960s by Anthony Fiacco and Garth McCormick. Their application to linear programming dates back to Narendra Karmarkar's innovative analysis in 1984. For more information, see Interior-Point Methods.

Software Resources

Due to advances in solution techniques and in computing power over the past two decades, linear programming problems with tens or hundreds of thousands of continuous variables are routinely solved. Commercial LP solvers tend to be faster and more robust than ``free'' LP solvers but they tend to be expensive, except for very limited evaluation and student versions. The freely available solvers tend to be somewhat less robust but they are still useful for many problems. With either type of solver, the ability to solve any particular class of problems cannot easily be predicted in advance from problem size alone; some experimentation is usually necessary to establish difficulty. The 2013 Linear Programming Software Survey in OR/MS Today offers an extensive summary of commercial and free solvers. The companion article by Robert Fourer highlights some issues to consider when selecting software.

  • Linear Programming Software on the NEOS Server

    If you do not have access to an LP solver at your institution and you prefer not to download a demo version or a free solver, you can access for free a number of commercial and freely available Linear Programming Solvers on the NEOS Server.

    • BDMLP: simplex-based solver included with GAMS systems
    • BPMPD: primal-dual interior point algorithm solver for LP and convex QP problems
    • Clp: open source solver with primal and dual simplex algorithms
    • Gurobi: commercial solver for LP (and many other problem types)
    • MOSEK: commercial solver for LP (and other problem types)
    • OOQP: primal-dual interior point algorithm solver for LP and convex QP problems
    • XpressMP: commercial solver for LP (and other problem types)
  • Other Sources of LP Solvers

    Hans Mittelmann's Decision Tree for Optimization Software lists additional public domain and free-for-research codes. The list includes LP/MILP solvers, pure LP solvers, and exact LP solvers.

    Depending on the software available to you at your institution, you may already have access to LP solvers.

    • Most spreadsheet programs come with a limited linear/integer programming solver as a feature or add-in. Frontline Systems offers more powerful upgrades of the Excel solver. Lindo Systems, Inc. offers What'sBest!, an Excel add-on for solving linear, integer, and nonlinear optimization models.
    • SAS/OR Software includes procedures for solving linear, integer, network flow, and nonlinear programming problems.
    • The IMSL Numerical Libraries offer functions for linear and nonlinear programming problems.
    • If you have MATLAB, you can run a number of useful optimization packages that provide some linear programming features:
    • MAPLE provides an Optimization Package for solving various types of optimization problems.
    • Mathematica offers an Operations Research package for solving problems for linear optimization problems as well as other types of optimization problems.
  • Tools and Utilities for Linear Programming

    • AIMMS Math Program Inspector - tool to analyze and debug linear programming models
    • LP Grapher - tool to graph and solve linear programs in two variables
    • MPROBE - suite of tools to analyze mathematical programming models

Test Problems

  • NETLIB LP Test Set
  • NETLIB LP Test Set in CUTE
  • GAMS offers the GAMS Model Library, which includes models of many different types, and the GAMS Testlib Library, which includes models that GAMS uses for testing and quality control.
  • There is a collection called MP-TESTDATA available at Konrad-Zuse-Zentrum fuer Informations-technik Berlin (ZIB). This directory contains various subdirectories, each of which has a file named "index" containing further information.
  • John Beasley of Brunel University maintains the OR-Library, which lists linear programming and over 3 dozen other categories of optimization test problems.

References

Last updated: February 24, 2014