|Introduction||Application Examples of Linear Programming|
|The LinearProgramming Function||Algorithms for Linear Programming|
|Importing Large Datasets and Solving Large-Scale Problems|
The Wolfram Language has a collection of algorithms for solving linear optimization problems with real variables, accessed via LinearProgramming, FindMinimum, FindMaximum, NMinimize, NMaximize, Minimize, and Maximize. LinearProgramming gives direct access to linear programming algorithms, provides the most flexibility for specifying the methods used, and is the most efficient for large-scale problems. FindMinimum, FindMaximum, NMinimize, NMaximize, Minimize, and Maximize are convenient for solving linear programming problems in equation and inequality form.
LinearProgramming is the main function for linear programming with the most flexibility for specifying the methods used, and is the most efficient for large-scale problems.
|Method||Automatic||method used to solve the linear optimization problem|
Options for LinearProgramming.
The Method option specifies the algorithm used to solve the linear programming problem. Possible values are Automatic, "Simplex", "RevisedSimplex", and "InteriorPoint". The default is Automatic, which automatically chooses from the other methods based on the problem size and precision.
The Tolerance option specifies the convergence tolerance.
The simplex and revised simplex algorithms solve a linear programming problem by moving along the edges of the polytope defined by the constraints, from vertices to vertices with successively smaller values of the objective function, until the minimum is reached. The Wolfram Language's implementation of these algorithms uses dense linear algebra. A unique feature of the implementation is that it is possible to solve exact/extended precision problems. Therefore these methods are suitable for small-sized problems for which non-machine-number results are needed, or a solution on the vertex is desirable.
Interior point algorithms for linear programming, loosely speaking, iterate from the interior of the polytope defined by the constraints. They get closer to the solution very quickly, but unlike the simplex/revised simplex algorithms, do not find the solution exactly. The Wolfram Language's implementation of an interior point algorithm uses machine-precision sparse linear algebra. Therefore for large-scale machine-precision linear programming problems, the interior point method is more efficient and should be used.
if the primal is
then the dual problem is
|unbounded||infeasible or unbounded|
|infeasible||unbounded or infeasible|
The primal-dual interior point method is designed for feasible problems; for infeasible/unbounded problems it will diverge, and with the current implementation, it is difficult to find out if the divergence is due to infeasibility, or unboundedness.
"TreatDenseColumn" is a method option of "InteriorPoint" that decides if dense columns are to be treated separately. Dense columns are columns of the constraint matrix that have many nonzero elements. By default, this method option has the value Automatic, and dense columns are treated separately.
Standard MPS formatted files use a fixed format, where each field occupies a strictly fixed character position. However some modeling systems output MPS files with a free format, where fields are positioned freely. For such files, the option "FreeFormat"->True can be specified for Import.
The example is adopted from . The aim is to design an anchor that uses as little material as possible to support a load.
This problem can be modeled by discretizing and simulating it using nodes and links. The modeling process is illustrated using the following figure. Here a grid of 7×10 nodes is generated. Each node is then connected by a link to all other nodes that are of Manhattan distance of less than or equal to three. The three red nodes are assumed to be fixed to the wall, while on all other nodes, compression and tension forces must balance.
The absolute values in the objective function can be replaced by breaking down into a combination of compression and tension forces, with each non-negative. Thus assume is the set of links, the set of nodes, the length of the link between nodes and , and and the compression and tension forces on the link; then the above model can be converted to a linear programming problem
The simplex and revised simplex algorithms solve linear programming problems by constructing a feasible solution at a vertex of the polytope defined by the constraints, and then moving along the edges of the polytope to vertices with successively smaller values of the objective function until the minimum is reached.
Although the sparse implementation of simplex and revised algorithms is quite efficient in practice, and is guaranteed to find the global optimum, the algorithms have a poor worst-case behavior: it is possible to construct a linear programming problem for which the simplex or revised simplex method takes a number of steps exponential in the problem size.
The Wolfram Language implements simplex and revised simplex algorithms using dense linear algebra. The unique feature of this implementation is that it is possible to solve exact/extended precision problems. Therefore these methods are more suitable for small-sized problems for which non-machine number results are needed.
Although the simplex and revised simplex algorithms can be quite efficient on average, they have a poor worst-case behavior. It is possible to construct a linear programming problem for which the simplex or revised simplex methods take a number of steps exponential in the problem size. The interior point algorithm, however, has been proven to converge in a number of steps that are polynomial in the problem size.
Furthermore, the Wolfram Language simplex and revised simplex implementation use dense linear algebra, while its interior point implementation uses machine-number sparse linear algebra. Therefore for large-scale, machine-number linear programming problems, the interior point method is more efficient and should be used.
This matrix is positive definite, but becomes very ill-conditioned as the solution is approached. Thus numerical techniques are used to stabilize the solution process, and typically the interior point method can only be expected to solve the problem to a tolerance of about , with tolerance explained in "Convergence Tolerance". The Wolfram Language uses Mehrotra's predictor-corrector scheme .