Sandbox::https://reference.wolfram.com/language/tutorial/ConstrainedOptimizationLinearProgramming.html

Wolfram Language & System Documentation Center

Linear Optimization

Introduction	Application Examples of Linear Optimization
The LinearOptimization Function	Algorithms for Linear Optimization
Examples	References
Importing Large Datasets and Solving Large-Scale Problems

Introduction

Linear optimization problems are defined as problems where the objective function and constraints are all linear.

The Wolfram Language has a collection of algorithms for solving linear optimization problems with real variables, accessed via LinearOptimization, FindMinimum, FindMaximum, NMinimize, NMaximize, Minimize and Maximize. LinearOptimization gives direct access to linear optimization 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 optimization problems in equation and inequality form.

This solves a linear optimization problem

using Minimize:

Wolfram Language code: Minimize[{x + 2 y, -5x + y == 7 && x + y ≥ 26 && x ≥ 3 && y ≥ 4}, {x, y}]

This solves the same problem using NMinimize. NMinimize returns a machine-number solution:

Wolfram Language code: NMinimize[{x + 2 y, -5x + y == 7 && x + y ≥ 26 && x ≥ 3 && y ≥ 4}, {x, y}]

This solves the same problem using LinearOptimization:

Wolfram Language code: LinearOptimization[x + 2y, {-5x + y == 7, x + y >= 26, x >= 3, y >= 4}, {x, y}]

The LinearOptimization Function

LinearOptimization is the main function for linear optimization with the most flexibility for specifying the methods used, and is the most efficient for large-scale problems.

Linear optimization finds that solves the primal problem:

	minimize
	subject to constraints
	where

The Lagrangian dual problem for linear optimization is given by:

	maximize
	subject to constraints
	where

The following options are accepted:

option name	default value
Method	Automatic	method used to solve the linear optimization problem
Tolerance	Automatic	convergence tolerance
MaxIterations	Automatic	maximum number of iterations to use
PerformanceGoal	$PerformanceGoal	aspects of performance to try to optimize
WorkingPrecision	Automatic	precision to be used in internal computations

Options for LinearOptimization

The Method option specifies the algorithm used to solve the linear optimization problem. Possible values are Automatic, "Simplex", "RevisedSimplex", "InteriorPoint", "CLP", "MOSEK" and "Gurobi". 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.

With WorkingPrecision->Automatic, the precision is taken automatically from the precision of the input arguments unless a method is specified that only works with machine precision, in which case machine precision is used.

There are a number of solution properties that can be accessed through the LinearOptimization function:

"PrimalMinimizer"	{,…}	A list of variable values that minimize the objective function
"PrimalMinimizerRules"	{v₁,…}	values for the variables vars={v₁,…} that minimize
"PrimalMinimizerVector"	x^*	the vector that minimizes
"PrimalMinimumValue"		the minimum value
"DualMaximizer"		the vector that maximizes
"DualMaximumValue"		the dual maximum value
"DualityGap"		the difference between the dual and primal optimal values (0 because of strong duality)
"Slack"		the constraint slack vector
"ConstraintSensitivity"		sensitivity of to constraint perturbations
"ObjectiveVector"		the linear objective vector
"LinearInequalityConstraints"		the linear inequality constraint matrix and vector
"LinearEqualityConstraints"		the linear equality constraint matrix and vector
{"prop₁","prop₂",...}		several solution properties

Solution properties for LinearOptimization.

Examples

Difference between Interior Point and Simplex and/or Revised Simplex

The simplex and revised simplex algorithms solve a linear optimization 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 optimization, 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 optimization problems, the interior point method is more efficient and should be used.

This solves a linear optimization problem that has multiple solutions (any point that lies on the line segment between {0,1} and {1,0} is a solution); the interior point algorithm gives a solution that lies in the middle of the solution set:

Wolfram Language code: LinearOptimization[-x - y, x + y <= 1, {x, y}, Method -> "InteriorPoint"]

Using Simplex or RevisedSimplex, a solution at the boundary of the solution set is given:

Wolfram Language code: LinearOptimization[-x - y, x + y <= 1, {x, y}, Method -> "RevisedSimplex"]

This shows that the interior point method is much faster for the following random sparse linear optimization problem of 200 variables and gives similar optimal value:

Wolfram Language code:

m = SparseArray[RandomChoice[{0.1, 0.9} -> {1., 0.}, {50, 200}]];
xi = LinearOptimization[Range[200].x, {m.x0, x0}, x, "PrimalMinimizerVector", Method -> "InteriorPoint"]; //Timing

Wolfram Language code: xs = LinearOptimization[Range[200].x, {m.x0, x0}, x, "PrimalMinimizerVector", Method -> "Simplex"]; //Timing

Wolfram Language code: Range[200].(xi - xs)

Finding Dual Variables

Given the general linear optimization problem

its dual is

It is useful to know solutions for both for some applications.

The relationship between the solutions of the primal and dual problems is given by the following table.

if the primal is	then the dual problem is
feasible	feasible
unbounded	infeasible or unbounded
infeasible	unbounded or infeasible

When both problems are feasible, then the optimal values of (P) and (D) are the same, and the following complementary conditions hold for the primal solution and dual solution .

The dual maximizer can be obtained from LinearOptimization using the "DualMaximizer" solution property.

This solves the primal problem

as well as the dual problem

Wolfram Language code:

primal = LinearOptimization[3x + 4y, {x + 2y >= 5, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, {"PrimalMinimizerRules", "DualMaximizer"}]

Solve the dual problem to confirm the results:

Wolfram Language code:

dual = LinearOptimization[-(5Subscript[λ, 1] + Subscript[λ, 2] - 4Subscript[λ, 3] + Subscript[λ, 4] - 4Subscript[λ, 5]), {Subscript[λ, 1] + Subscript[λ, 2] - Subscript[λ, 3] == 3, 
	2Subscript[λ, 1] + Subscript[λ, 4] - Subscript[λ, 5] == 4, Subscript[λ, 1] >= 0, Subscript[λ, 2] >= 0, Subscript[λ, 3] >= 0, Subscript[λ, 4] >= 0, Subscript[λ, 5] >= 0}, {Subscript[λ, 1], Subscript[λ, 2], Subscript[λ, 3], Subscript[λ, 4], Subscript[λ, 5]}]

This confirms that the primal and dual give the same objective value:

Wolfram Language code: {3, 4}.{x, y} /. primal[[1]]

Wolfram Language code: {5, 1, -4, 1, -4}.{Subscript[λ, 1], Subscript[λ, 2], Subscript[λ, 3], Subscript[λ, 4], Subscript[λ, 5]} /. dual

Confirm the primal and dual objective values directly using solution properties:

Wolfram Language code: LinearOptimization[3x + 4y, {x + 2y >= 5, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, {"PrimalMinimumValue", "DualMaximumValue"}]

The dual of the constraint

, which means that for one unit of increase in the right-hand side of the constraint, there will be two units of increase in the objective. This can be confirmed by perturbing the right-hand side of the constraint by 0.001:

Wolfram Language code: pval = LinearOptimization[3x + 4y, {x + 2y >= 5 + 0.001, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, "PrimalMinimumValue"]

Indeed, the objective value increases by twice that amount:

Wolfram Language code: pval - {3, 4}.{x, y} /. primal[[1]]

Use the "ConstraintSensitivity" property to see the effect of the perturbations

on the constraints

Wolfram Language code:

{a, b} = {{{1, 2}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}, {-5, -1, 4, -1, 4}};
{p^ * , {Subscript[s, λ], Subscript[s, ν]}} = LinearOptimization[3x + 4y, a.{x, y} + b0, {x, y}, {"PrimalMinimumValue", "ConstraintSensitivity"}]

Wolfram Language code: p^ * + Subscript[s, λ].{-0.001, 0, 0, 0, 0}

Dealing with Infeasibility and Unboundedness in the Interior Point Method

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.

A heuristic catches infeasible/unbounded problems and issues a suitable message:

Wolfram Language code: LinearOptimization[x + y, {x + y <= 1, x + y >= 2}, {x, y}, Method -> "InteriorPoint"]

Sometimes the heuristic cannot tell with certainty if a problem is infeasible or unbounded:

Wolfram Language code: LinearOptimization[-x - y, {x + y >= 1, x >= 0, y >= 0}, {x, y}, Method -> "InteriorPoint"]

Using the Simplex method shows that the problem is unbounded:

Wolfram Language code: LinearOptimization[-x - y, {x + y >= 1, x >= 0, y >= 0}, {x, y}, Method -> "Simplex"]

The Method Options of "InteriorPoint"

"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.

Large problems that contain dense columns typically benefit from dense column treatment:

Wolfram Language code:

A = SparseArray[{{i_, i_} -> 1., {i_, 1} -> 1.}, {300, 300}];
c = Table[1, {300}];
b = A.Range[300];

Wolfram Language code:

{x1 = LinearOptimization[c.x, {A.xb, x0}, x, "PrimalMinimizerVector", Method -> "InteriorPoint"]; // Timing, 
	x2 = LinearOptimization[c.x, {A.xb, x0}, x, "PrimalMinimizerVector", Method -> {"InteriorPoint", "TreatDenseColumns" -> False}];//Timing}

Wolfram Language code: x1.c - x2.c

Importing Large Datasets and Solving Large-Scale Problems

A commonly used format for documenting linear optimization problems is the Mathematical Programming System (MPS) format. This is a text format consisting of a number of sections.

Importing MPS Formatted Files in Equation Form

The Wolfram Language is able to import MPS formatted files. By default, Import of MPS data returns a linear optimization problem in equation form, which can then be solved using LinearOptimization, Minimize or NMinimize.

This solves the linear optimization problem specified by the MPS file "afiro.mps":

Wolfram Language code: {eqns, vars} = Import["Optimization/Data/afiro.mps"]

Wolfram Language code: LinearOptimization[eqns[[1]], Rest[eqns], vars]

Large-Scale Problems: Importing in Matrix and Vector Form

For large-scale problems, it is more efficient to import the MPS data file and represent the linear optimization using matrices and vectors, then solve using LinearOptimization.

This shows that for MPS formatted data, the following three elements can be imported:

Wolfram Language code: Import["Optimization/Data/ganges.mps", "Elements"]

This imports the problem "ganges", with 1309 constraints and 1681 variables:

Wolfram Language code: {c, linIneq, linEq} = Import["Optimization/Data/ganges.mps", "LinearOptimizationData"];

This solves the problem and finds the optimal value:

Wolfram Language code: x = LinearOptimization[c, linIneq, linEq];

Wolfram Language code: c.x

The "ConstraintMatrix" specification can be used to get the sparse constraint matrix only:

Wolfram Language code: p = Import["Optimization/Data/ganges.mps", "ConstraintMatrix"]

Free Formatted MPS Files

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.

This string describes an MPS file in free format:

Wolfram Language code:

txt = "NAME TESTPROB
ROWS
 N COST
 L CON1
 G CON2
 E CON3 
COLUMNS
 x COST 1 CON1 2
 x CON2 3
 y COST 4 CON1 5
 y CON3 6
 Z COST 7 CON2 8
 Z CON3 9
RHS
 RHS1 CON1 10 CON2 11
 RHS1 CON3 12
BOUNDS
 UP BND1 x 13
 LO BND1 y 14
 UP BND1 y 15
ENDATA
";

This gets a temporary file name and exports the string to the file:

Wolfram Language code:

file = Close[OpenWrite[]];
Export[file, txt, "Text"];

This imports the file, using the "FreeFormat"->True option:

Wolfram Language code: Import[file, "MPS", "FreeFormat" -> True]

Linear Optimization Test Problems

Through the ExampleData function, all NetLib linear optimization test problems can be accessed.

This finds all problems in the Netlib set:

Wolfram Language code: ExampleData["LinearOptimization"]

This imports the problem "afiro" and solves it:

Wolfram Language code: afiroData = ExampleData[{"LinearOptimization", "afiro"}]

Wolfram Language code: LinearOptimization@@afiroData

This shows other properties that can be imported for the "afiro" problem:

Wolfram Language code: ExampleData[{"LinearOptimization", "afiro"}, "Properties"]

This imports "afiro" in equation form and can be used directly to solve the problem:

Wolfram Language code: afiroEqns = ExampleData[{"LinearOptimization", "afiro"}, "Equations"]

Wolfram Language code: LinearOptimization[Sequence@@afiroEqns[[1]], afiroEqns[[2]]]

Application Examples of Linear Optimization

L1-Norm Minimization

It is possible to solve an minimization problem

by turning the system into a linear optimization problem

Define the input and output points:

Wolfram Language code:

{input, output} = IconizedObject[«Block»];
dataplot = ListPlot[output, PlotRange -> All]

This fits the data:

Wolfram Language code:

Clear[a, b, s, x];
res = LinearOptimization[Total[s], {a == input, b == output, -sa.x - bs}, {x, s}]

This plots the line and shows that it is robust to the outliers:

Wolfram Language code: Show[ dataplot, Plot[Evaluate[x.{1, t} /. res], {t, 1, 30}]]

Compare with the fit obtained using LeastSquares:

Wolfram Language code: line = Fit[output, {1, t}, t]

Wolfram Language code: Show[ dataplot, Plot[Evaluate[{x.{1, t} /. res, line}], {t, 1, 30}]]

Design of Optimal Truss

The example is adopted from [2]. 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.

Each link represents a rigid rod that has a thickness, with its weight proportional to the force on it and its length. The aim is to minimize the total material used, which is

Hence mathematically this is a linearly constrained minimization problem, with objective function a sum of absolute values of linear functions.

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 optimization problem.

Select a few specific positions where the truss is anchored to the wall.

Wolfram Language code: anchorPoints = Thread[{0, Range[-3, 3]}];

The position where the load is applied is at the end of the truss.

Wolfram Language code: forcingPoint = {30, 0};

The truss can be modeled using links and nodes. Each node is connected to the neighboring node by a link. The connectivity pattern is given by:

Wolfram Language code:

connectivityPattern = Partition[Flatten[{Thread[{{-1, 1}, 0}], Outer[List, Range[-3, 3], {-1, 1}], Outer[List, {-3, -1, 1, 3}, {-2, 2}], Outer[List, {-2, -1, 1, 2}, {-3, 3}]}], 2];

The candidate nodes are placed in a rectangular lattice.

Wolfram Language code:

bounds = {{0, 30}, {-10, 10}};
nodes   = Flatten[Outer[List, Sequence@@Apply[Range, bounds, 1]], 1];
np = Length[nodes];

Visualize the node positions, the anchor positions, the position where force is applied and the connectivity of a single node in the middle of the truss.

Wolfram Language code:

mid  = Round[Map[Mean, bounds]];
cmid = Map[Plus[mid, #]&, connectivityPattern];
Graphics[{Point[nodes], Blue, Map[Circle[#, .5]&, anchorPoints], Red, Arrow[{forcingPoint, forcingPoint - {0, 2}}], Map[Line[{mid, #}]&, cmid]}, ImageSize -> Medium]

Each node is associated with a unique index. Association efficiently provides a fast lookup table.

Wolfram Language code:

toIndex = AssociationThread[nodes -> Range[np]];
fromIndex = AssociationThread[Range[np] -> nodes];

Find the indices associated with anchor and forcing points.

Wolfram Language code:

anchorPointIndex = Lookup[toIndex, anchorPoints];
forcePointIndex   = toIndex[forcingPoint];

Construct a function that provides the connectivity of any lattice point for any given connectivity pattern.

Wolfram Language code:

connectivity[index_, pat_] := Module[{point = fromIndex[index], connectedPoints, connectedIndexes}, 
	connectedPoints  = Map[Plus[point, #]&, pat];
	connectedIndexes = Cases[Map[toIndex, connectedPoints], Except[_Missing]];
	Thread[{index, Sort[connectedIndexes]}]];

Describe the set of links by

. Construct a sparse connectivity matrix

for the nodes using the pattern defined previously where

if the link

and

otherwise.

Wolfram Language code:

nodePosition = Join@@Map[connectivity[#,   connectivityPattern]&, Range[np]];
nodeConnectivityMatrix = SparseArray[nodePosition -> 1, {np, np}]

Wolfram Language code:

links = DeleteDuplicates[Map[Sort, nodeConnectivityMatrix["NonzeroPositions"]]];
nlinks = Length[links];

A convenient way to describe the links in

is to have an indexing of links.

Wolfram Language code: linkToIndex = AssociationThread[links -> Range[nlinks]];

The objective is to minimize

, where

is the length between node

and

is the force exerted by the link formed by

on its end joint.

Wolfram Language code:

links = DeleteDuplicates[Map[Sort, nodeConnectivityMatrix["NonzeroPositions"]]];
nlinks = Length[links];
linkLengths = Map[EuclideanDistance@@nodes[[#]]&, links];

The function

is nonlinear but can be expressed as a linear function by introducing

such that

and

. The objective is:

Wolfram Language code: objective = linkLengths.(xp + xm);

At each node except the forcing point, there are no external forces applied.

Wolfram Language code: nodeForce = ConstantArray[0., {np, 2}];

At the forcing point there is a vertical downward unit force applied.

Wolfram Language code: nodeForce[[forcePointIndex]] = {0., -1.};

At each non-anchoring node there must be a force balance

where

is the position of the node

Wolfram Language code:

columns = nodeConnectivityMatrix["MatrixColumns"];
linkToIndex = AssociationThread[links -> Range[nlinks]];
linkConstraints = Table[
	mi = columns[[i]];
	vii = Map[Sort, Thread[{i, mi}]];
	vi = Map[Indexed[xp, linkToIndex[#]] - Indexed[xm, linkToIndex[#]]&, vii];
	s = Map[(nodes[[#]] - nodes[[i]])&, mi];
	lhs = Total[Map[# / Norm[#]&, s] * vi];
	Thread[lhs == nodeForce[[i]]]
	, {i, Complement[Range[np], anchorPointIndex]}];

The final constraints are:

Wolfram Language code: constraints = Join[Flatten[linkConstraints], {xp0, xm0}];

Solve the resulting system.

Wolfram Language code:

res = LinearOptimization[objective, constraints, {xp∈Vectors[nlinks], 
	xm∈Vectors[nlinks]}];

Visualize the optimal truss with shades of blue indicating compression of links and shades of red indicating expansion of links.

Wolfram Language code:

totalf = (xp - xm) /. res;
maxForce = Max[Abs[totalf]];
index = Pick[Range[nlinks], Thread[Abs[totalf] / maxForce ≥ 0.001], True];
allLinks = Table[
	f = totalf[[i]] / maxForce;
	vlink = nodes[[links[[i]]]];
	{Hue[(1 + f) / 2.5], Thickness[.025 Abs[f]], Line[vlink]}, 
	{i, index}];
Graphics[{allLinks, {PointSize[0.02], Point[anchorPoints]}, {EdgeForm[StandardGray], FaceForm[None], Rectangle[{-1, -10}, {0.01, 10}]}}, ImageSize -> Medium]

Algorithms for Linear Optimization

Simplex and Revised Simplex Algorithms

The simplex and revised simplex algorithms solve linear optimization 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 optimization 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.

This sets up a random linear optimization problem with 20 constraints and 200 variables:

Wolfram Language code:

SeedRandom[123];
{m, n} = {20, 100};
c = RandomInteger[{1, 10}, n];
A = RandomInteger[{-100, 100}, {m, n}];
b = A.ConstantArray[1, n];
constraints = {A.xb, -10x10};

This solves the problem. Typically, for a linear optimization problem with many more variables than constraints, the revised simplex algorithm is faster. On the other hand, if there are many more constraints than variables, the simplex algorithm is faster:

Wolfram Language code:

t = Timing[res = LinearOptimization[c.x, constraints, x, 
	"PrimalMinimizerVector", Method -> "Simplex"];]; Print["time = ", t[[1]], " optimal value = ", c.res, " or ", N[c.res]]

Wolfram Language code:

t = Timing[res = LinearOptimization[c.x, constraints, x, 
	"PrimalMinimizerVector", Method -> "RevisedSimplex"];]; Print["time = ", t[[1]], " optimal value = ", c.res, " or ", N[c.res]]

If only machine-number results are desired, then the problem should be converted to machine numbers, and the interior point algorithm should be used:

Wolfram Language code:

t = Timing[res = LinearOptimization[c.x, constraints, x, 
	"PrimalMinimizerVector", Method -> "InteriorPoint"];];
Print["time = ", t[[1]], " optimal value = ", c.res]

Interior Point Algorithm

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 optimization 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 optimization problems, the interior point method is more efficient and should be used.

Interior Point Formulation

Consider the standardized linear optimization problem

where , , . This problem can be solved using a barrier function formulation to deal with the positive constraints.

The first-order necessary condition for the preceding problem gives:

Let denote the diagonal matrix made of the vector , and .

This is a set of linear/nonlinear equations with constraints. It can be solved using Newton's method

with

One way to solve this linear system is to use Gaussian elimination to simplify the matrix into block triangular form.

To solve this block triangular matrix, the so-called normal system can be solved, with the matrix in this normal system:

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 [1].

Convergence Tolerance

General linear optimization problems are first converted to the standard form

with the corresponding dual

The convergence criterion for the interior point algorithm is

with the tolerance set, by default, to .

References

[1] Vanderbei, R. Linear Programming: Foundations and Extensions. Springer-Verlag, 2001.

[2] Mehrotra, S. "On the Implementation of a Primal-Dual Interior Point Method." SIAM Journal on Optimization 2 (1992): 575–601.

Top

More Learning

Tech Support

Data Science, Finance & Business

Engineering

Science & Technology

Technology for Education

Education Initiatives

Get Started

Grow Your Skills

Work with Us

Educational Programs for Adults

Educational Programs for Youth

Read

Linear Optimization

Introduction

The LinearOptimization Function

Examples

Difference between Interior Point and Simplex and/or Revised Simplex

Finding Dual Variables

Dealing with Infeasibility and Unboundedness in the Interior Point Method

The Method Options of "InteriorPoint"

Importing Large Datasets and Solving Large-Scale Problems

Importing MPS Formatted Files in Equation Form

Large-Scale Problems: Importing in Matrix and Vector Form

Free Formatted MPS Files

Linear Optimization Test Problems

Application Examples of Linear Optimization

L1-Norm Minimization

Design of Optimal Truss

Algorithms for Linear Optimization

Simplex and Revised Simplex Algorithms

Interior Point Algorithm

Interior Point Formulation

Convergence Tolerance

References

Linear Optimization

Introduction

The LinearOptimization Function

Examples

Difference between Interior Point and Simplex and/or Revised Simplex

Finding Dual Variables

Dealing with Infeasibility and Unboundedness in the Interior Point Method

The Method Options of "InteriorPoint"

Importing Large Datasets and Solving Large-Scale Problems

Importing MPS Formatted Files in Equation Form

Large-Scale Problems: Importing in Matrix and Vector Form

Free Formatted MPS Files

Linear Optimization Test Problems

Application Examples of Linear Optimization

L1-Norm Minimization

Design of Optimal Truss

Algorithms for Linear Optimization

Simplex and Revised Simplex Algorithms

Interior Point Algorithm

Interior Point Formulation

Convergence Tolerance

References

Related Tech Notes