LinearOptimization
✖
LinearOptimization
finds values of variables vars that minimize the linear objective f subject to linear constraints cons.
finds a real vector x that minimizes the linear objective subject to the linear inequality constraints
.
takes xi to be in the domain domi, where domi is Integers or Reals.
Details and Options




- Linear optimization is also known as linear programming (LP) and mixed-integer linear programming (MILP).
- Linear optimization is a convex optimization problem that can be solved globally and efficiently with real, integer or complex variables.
- Linear optimization finds
that solves the primal problem: »
-
minimize subject to constraints where - Mixed-integer linear optimization finds
and
that solve the problem:
-
minimize subject to constraints where - When the objective function is real valued, LinearOptimization solves problems with
by internally converting to real variables
, where
and
.
- The variable specification vars should be a list with elements giving variables in one of the following forms:
-
v variable with name and dimensions inferred
v∈Reals real scalar variable v∈Integers integer scalar variable v∈Complexes complex scalar variable v∈ℛ vector variable restricted to the geometric region v∈Vectors[n,dom] vector variable in or
v∈Matrices[{m,n},dom] matrix variable in or
- The constraints cons can be specified by:
-
LessEqual scalar inequality GreaterEqual scalar inequality VectorLessEqual vector inequality VectorGreaterEqual vector inequality Equal scalar or vector equality Element convex domain or region element - With LinearOptimization[f,cons,vars], parameter equations of the form parval, where par is not in vars and val is numerical or an array with numerical values, may be included in the constraints to define parameters used in f or cons.
- The primal minimization problem has a related maximization problem that is the Lagrangian dual problem. The dual maximum value is always less than or equal to the primal minimum value, so it provides a lower bound. The dual maximizer provides information about the primal problem, including sensitivity of the minimum value to changes in the constraints.
- The Lagrangian dual problem for linear optimization is given by: »
-
maximize subject to constraints where - For linear optimization, strong duality always holds, meaning that if there is a solution to the primal minimization problem, then there is a solution to the dual maximization problem, and the dual maximum value is equal to the primal minimum value.
- The possible solution properties "prop" include:
-
"PrimalMinimizer" a list of variable values that minimize the objective function "PrimalMinimizerRules" values for the variables vars={v1,…} that minimize "PrimalMinimizerVector" 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 {"prop1","prop2",…} several solution properties - The following options can be given:
-
MaxIterations Automatic maximum number of iterations to use Method Automatic the method to use PerformanceGoal $PerformanceGoal aspects of performance to try to optimize Tolerance Automatic the tolerance to use for internal comparisons WorkingPrecision Automatic precision to use in internal computations - The option Method->method may be used to specify the method to use. Available methods include:
-
Automatic choose the method automatically "Simplex" simplex method "RevisedSimplex" revised simplex method "InteriorPoint" interior point method (machine precision only) "CLP" COIN library linear programming (machine precision only) "MOSEK" commercial MOSEK linear optimization solver "Gurobi" commercial Gurobi linear optimization solver "Xpress" commercial Xpress linear optimization solver - 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.

Examples
open allclose allBasic Examples (3)Summary of the most common use cases
Minimize subject to the constraints
:

https://wolfram.com/xid/0b8dztxl0i-5q6z40

The optimal point lies in a region defined by the constraints and where is smallest within the region:

https://wolfram.com/xid/0b8dztxl0i-riqa65

Minimize subject to the constraints
:

https://wolfram.com/xid/0b8dztxl0i-6i3vzl

Use the equivalent matrix representation:

https://wolfram.com/xid/0b8dztxl0i-kjxeti

Minimize subject to the constraints
:

https://wolfram.com/xid/0b8dztxl0i-ssv0pz

Use the equivalent matrix representation:

https://wolfram.com/xid/0b8dztxl0i-vex8jn

Scope (32)Survey of the scope of standard use cases
Basic Uses (16)
Minimize subject to the constraints
:

https://wolfram.com/xid/0b8dztxl0i-bmgx0j

Minimize subject to the constraints
and
:

https://wolfram.com/xid/0b8dztxl0i-7grjvm

Minimize subject to the constraints
and the bounds
:

https://wolfram.com/xid/0b8dztxl0i-gmr527

Use VectorLessEqual to express several LessEqual inequality constraints at once:

https://wolfram.com/xid/0b8dztxl0i-s5e3zm

Use v<=
to enter the vector inequality in a compact form:

https://wolfram.com/xid/0b8dztxl0i-0mtyw2

An equivalent form using scalar inequalities:

https://wolfram.com/xid/0b8dztxl0i-b9pt3y

Use VectorGreaterEqual to express several GreaterEqual inequality constraints at once:

https://wolfram.com/xid/0b8dztxl0i-32lhmf

Use v>=
to enter the vector inequality in a compact form:

https://wolfram.com/xid/0b8dztxl0i-v47628

Use Equal to express several equality constraints at once:

https://wolfram.com/xid/0b8dztxl0i-dkthbi

An equivalent form using several scalar equalities:

https://wolfram.com/xid/0b8dztxl0i-s527v9

Specify the constraints using a combination of scalar and vector inequalities:

https://wolfram.com/xid/0b8dztxl0i-ukfa1o

An equivalent form using scalar inequalities:

https://wolfram.com/xid/0b8dztxl0i-bb7218

Minimize subject to
. Use a vector variable
:

https://wolfram.com/xid/0b8dztxl0i-2enkzs

An equivalent form using scalar variables:

https://wolfram.com/xid/0b8dztxl0i-iqww3c

Use vector variables and vector inequalities to specify the problem:

https://wolfram.com/xid/0b8dztxl0i-rwa4vl

Minimize the function subject to the constraint
:

https://wolfram.com/xid/0b8dztxl0i-v9guvz
Use Indexed to access components of a vector variable, e.g. :

https://wolfram.com/xid/0b8dztxl0i-p46cfv

Use constant parameter equations to specify the coefficients of the objective and constraints:

https://wolfram.com/xid/0b8dztxl0i-x91sv

https://wolfram.com/xid/0b8dztxl0i-hwo4um

Use constant parameter equations to specify coefficients of several constraints:

https://wolfram.com/xid/0b8dztxl0i-lmthz4

https://wolfram.com/xid/0b8dztxl0i-55pxe9


https://wolfram.com/xid/0b8dztxl0i-g7dxg8

Minimize the function subject to
:

https://wolfram.com/xid/0b8dztxl0i-ov6zs8

https://wolfram.com/xid/0b8dztxl0i-cy4i5a


Use Vectors[n] to specify the dimension of vector variables when needed:

https://wolfram.com/xid/0b8dztxl0i-duoemo

Specify non-negative constraints using NonNegativeReals ():

https://wolfram.com/xid/0b8dztxl0i-qx6qyw

An equivalent form using vector inequalities:

https://wolfram.com/xid/0b8dztxl0i-7vl1

Specify non-positive constraints using NonPositiveReals ():

https://wolfram.com/xid/0b8dztxl0i-domqhv

An equivalent form using vector inequalities:

https://wolfram.com/xid/0b8dztxl0i-bim93z

Minimize subject to
by directly giving the matrix
and vectors
and
:

https://wolfram.com/xid/0b8dztxl0i-p0zccg

https://wolfram.com/xid/0b8dztxl0i-9hhi95

The equivalent form using variables and inequalities:

https://wolfram.com/xid/0b8dztxl0i-db4frw


https://wolfram.com/xid/0b8dztxl0i-jf030

Integer Variables (4)
Specify integer domain constraints using Integers:

https://wolfram.com/xid/0b8dztxl0i-qm91mh

Specify integer domain constraints on vector variables using Vectors[n,Integers]:

https://wolfram.com/xid/0b8dztxl0i-nwgmde

Specify non-negative integer constraints using NonNegativeIntegers ():

https://wolfram.com/xid/0b8dztxl0i-3mcv3z

An equivalent form using vector inequalities:

https://wolfram.com/xid/0b8dztxl0i-m1zx0f

Specify non-positive integer constraints using NonPositiveIntegers ():

https://wolfram.com/xid/0b8dztxl0i-ruhh20

An equivalent form using vector inequalities:

https://wolfram.com/xid/0b8dztxl0i-mpyf5l

Complex Variables (2)
Specify complex variables using Complexes:

https://wolfram.com/xid/0b8dztxl0i-g1eqo6

Minimize a real objective with complex variables and complex constraints
:

https://wolfram.com/xid/0b8dztxl0i-bzlu37

Suppose that ; then expanding out the constraint into real components gives:

https://wolfram.com/xid/0b8dztxl0i-ccbk3g


https://wolfram.com/xid/0b8dztxl0i-fo49g6

https://wolfram.com/xid/0b8dztxl0i-q13dq

Solve the problem with real-valued objective and complex variables and constraints:

https://wolfram.com/xid/0b8dztxl0i-d86vc6

Solve the same problem with real variables and constraints:

https://wolfram.com/xid/0b8dztxl0i-kyxjrh

Primal Model Properties (3)
Minimize the function subject to the constraints
:

https://wolfram.com/xid/0b8dztxl0i-fe0aet

Get the primal minimizer as a vector:

https://wolfram.com/xid/0b8dztxl0i-i6yow8


https://wolfram.com/xid/0b8dztxl0i-btyeyj

Obtain the primal minimum value using symbolic inputs:

https://wolfram.com/xid/0b8dztxl0i-c80uca

https://wolfram.com/xid/0b8dztxl0i-8sz25v

Extract the matrix-vector inputs of the optimization problem:

https://wolfram.com/xid/0b8dztxl0i-gb428l
Solve using the matrix-vector form:

https://wolfram.com/xid/0b8dztxl0i-rytp6s

Recover the symbolic primal value by adding the objective constant:

https://wolfram.com/xid/0b8dztxl0i-frspvb


https://wolfram.com/xid/0b8dztxl0i-f20som

Find the slack associated with a minimization problem:

https://wolfram.com/xid/0b8dztxl0i-9ai1m3

https://wolfram.com/xid/0b8dztxl0i-x9a799

Get the primal minimizer and the constraint matrices:

https://wolfram.com/xid/0b8dztxl0i-ykb1ow
The slack for inequality constraints is a vector
such that
:

https://wolfram.com/xid/0b8dztxl0i-omohh9

The slack for the equality constraints is a vector
such that
:

https://wolfram.com/xid/0b8dztxl0i-6ce0wf

The equality slack is typically a zero vector:

https://wolfram.com/xid/0b8dztxl0i-nzy9b1

Dual Model Properties (3)

https://wolfram.com/xid/0b8dztxl0i-eqga52

https://wolfram.com/xid/0b8dztxl0i-3glri

The dual problem is to maximize subject to
and
:

https://wolfram.com/xid/0b8dztxl0i-e96iz9

https://wolfram.com/xid/0b8dztxl0i-bkq9e0

The primal minimum value and the dual maximum value coincide because of strong duality:

https://wolfram.com/xid/0b8dztxl0i-st7rt

That is the same as having a duality gap of zero. In general, at optimal points:

https://wolfram.com/xid/0b8dztxl0i-hekvib

Construct the dual problem using constraint matrices extracted from the primal problem:

https://wolfram.com/xid/0b8dztxl0i-fngb7w

https://wolfram.com/xid/0b8dztxl0i-wtwm4l

Extract the objective vector and constraint matrices:

https://wolfram.com/xid/0b8dztxl0i-vm47it
The dual problem is to maximize subject to
and
:

https://wolfram.com/xid/0b8dztxl0i-hlqwj5

Get the dual maximum value directly using solution properties:

https://wolfram.com/xid/0b8dztxl0i-kpuy5d

Get the dual maximizer directly using solution properties:

https://wolfram.com/xid/0b8dztxl0i-83q78f

Sensitivity Properties (4)
Use "ConstraintSensitivity" to find the change in optimal value due to constraint relaxations:

https://wolfram.com/xid/0b8dztxl0i-e4vks
The first vector is inequality sensitivity and the second is equality sensitivity:

https://wolfram.com/xid/0b8dztxl0i-da0bee

Consider new constraints where
is the relaxation:

https://wolfram.com/xid/0b8dztxl0i-kjywq6
The expected new optimal value is given by:

https://wolfram.com/xid/0b8dztxl0i-334tm

Compare to directly solving the relaxed problem:

https://wolfram.com/xid/0b8dztxl0i-edvgma

Each sensitivity is associated with an inequality or equality constraint:

https://wolfram.com/xid/0b8dztxl0i-kawg90


https://wolfram.com/xid/0b8dztxl0i-v6akge
The inequality constraints and their associated sensitivity:

https://wolfram.com/xid/0b8dztxl0i-jdhr22

The equality constraints and their associated sensitivity:

https://wolfram.com/xid/0b8dztxl0i-bj3ghv

The change in optimal value due to constraint relaxation is proportional to the sensitivity value:

https://wolfram.com/xid/0b8dztxl0i-0u22ey
Compute the minimal value and constraint sensitivity:

https://wolfram.com/xid/0b8dztxl0i-nxbm6u

A zero sensitivity will not change the optimal value if the constraint is relaxed:

https://wolfram.com/xid/0b8dztxl0i-5e19w


https://wolfram.com/xid/0b8dztxl0i-pmmhrs

A negative sensitivity will decrease the optimal value:

https://wolfram.com/xid/0b8dztxl0i-dr65nc


https://wolfram.com/xid/0b8dztxl0i-wf7cfi

A positive sensitivity will increase the optimal value:

https://wolfram.com/xid/0b8dztxl0i-bqtuvf


https://wolfram.com/xid/0b8dztxl0i-snki22

The "ConstraintSensitivity" is related to the dual maximizer of the problem:

https://wolfram.com/xid/0b8dztxl0i-rs7ip4

The inequality sensitivity satisfies
, where
is the dual inequality maximizer:

https://wolfram.com/xid/0b8dztxl0i-did423

The equality sensitivity satisfies
, where
is the dual equality maximizer:

https://wolfram.com/xid/0b8dztxl0i-bbxdug

Options (9)Common values & functionality for each option
Method (5)
The default method for MachinePrecision input is "CLP":

https://wolfram.com/xid/0b8dztxl0i-kntucz

https://wolfram.com/xid/0b8dztxl0i-f4doef


https://wolfram.com/xid/0b8dztxl0i-rx5jkj

The default method for arbitrary or infinite WorkingPrecision is "Simplex":

https://wolfram.com/xid/0b8dztxl0i-brk0sq


https://wolfram.com/xid/0b8dztxl0i-jebn9w

All methods work for MachinePrecision input:

https://wolfram.com/xid/0b8dztxl0i-ilgat

https://wolfram.com/xid/0b8dztxl0i-wv2ee0

"Simplex" and "RevisedSimplex" can be used for arbitrary- and infinite-precision inputs:

https://wolfram.com/xid/0b8dztxl0i-b8gqe9


https://wolfram.com/xid/0b8dztxl0i-b5xdtf

Different methods have different strengths, which is typically problem and implementation dependent:

https://wolfram.com/xid/0b8dztxl0i-f49sns
"Simplex" and "RevisedSimplex" are good for small dense problems:

https://wolfram.com/xid/0b8dztxl0i-syrrej

"InteriorPoint" and "CLP" are good for large sparse problems:

https://wolfram.com/xid/0b8dztxl0i-qhr2yh


https://wolfram.com/xid/0b8dztxl0i-ctusf9

"InteriorPoint" or "CLP" methods may not be able to tell if a problem is infeasible or unbounded:

https://wolfram.com/xid/0b8dztxl0i-m1l0ph



https://wolfram.com/xid/0b8dztxl0i-bjxk3p


"Simplex" and "RevisedSimplex" can detect unbounded or infeasible problems:

https://wolfram.com/xid/0b8dztxl0i-dijf5w


Different methods may give different results for problems with more than one optimal solution:

https://wolfram.com/xid/0b8dztxl0i-lmesy9

"InteriorPoint" may return a solution in the middle of the optimal solution set:

https://wolfram.com/xid/0b8dztxl0i-cvhxpz

"Simplex" always returns a solution at a corner of the optimal solution set:

https://wolfram.com/xid/0b8dztxl0i-qc5bbo

Tolerance (2)
A smaller Tolerance setting gives a more precise result:

https://wolfram.com/xid/0b8dztxl0i-r49hti
Specify the constraint matrices:

https://wolfram.com/xid/0b8dztxl0i-ht5r3q
Find the error between computed and exact minimum value using different Tolerance settings:

https://wolfram.com/xid/0b8dztxl0i-lew19r

Visualize the change in minimum value error with respect to tolerance:

https://wolfram.com/xid/0b8dztxl0i-cqloft

A smaller Tolerance setting gives a more precise answer, but typically takes longer to compute:

https://wolfram.com/xid/0b8dztxl0i-mggi94
A smaller tolerance takes longer:

https://wolfram.com/xid/0b8dztxl0i-cicu9n


https://wolfram.com/xid/0b8dztxl0i-j4yqkt

The tighter tolerance gives a more precise answer:

https://wolfram.com/xid/0b8dztxl0i-csn2pu

WorkingPrecision (2)
LinearOptimization infers the WorkingPrecision to use from the input:

https://wolfram.com/xid/0b8dztxl0i-uk56

MachinePrecision input gives MachinePrecision output:

https://wolfram.com/xid/0b8dztxl0i-ory39i


https://wolfram.com/xid/0b8dztxl0i-jbt5jh

LinearOptimization can compute results using higher working precision:

https://wolfram.com/xid/0b8dztxl0i-r7sw7w

If the specified precision is less than the precision of the input arguments, a message is issued:

https://wolfram.com/xid/0b8dztxl0i-sf1s13



Applications (34)Sample problems that can be solved with this function
Basic Modeling Transformations (8)
Maximize subject to
. Solve a maximization problem by negating the objective function:

https://wolfram.com/xid/0b8dztxl0i-7aogom

Negate the primal minimum value to get the corresponding maximal value:

https://wolfram.com/xid/0b8dztxl0i-lmnvsg

Convert into a linear function using
and
:

https://wolfram.com/xid/0b8dztxl0i-zzofuh

Convert into a linear function using
and
:

https://wolfram.com/xid/0b8dztxl0i-dk3i33

https://wolfram.com/xid/0b8dztxl0i-68bxsz

Minimize subject to the constraints
. Convert
into a linear function using
:

https://wolfram.com/xid/0b8dztxl0i-c9xya9

The problem can also be converted using :

https://wolfram.com/xid/0b8dztxl0i-890v1p

Minimize subject to the constraints
. The constraint can be transformed to
:

https://wolfram.com/xid/0b8dztxl0i-rgjgbs

Minimize subject to the constraints
. The constraint
can be interpreted as
. Solve the problem with each constraint:

https://wolfram.com/xid/0b8dztxl0i-bourn8


https://wolfram.com/xid/0b8dztxl0i-27mtls

The optimal solution is the minimum of the two solutions:

https://wolfram.com/xid/0b8dztxl0i-llaoru


https://wolfram.com/xid/0b8dztxl0i-ythwb6

Minimize subject to
, where
is a nondecreasing function, by instead minimizing
. The primal minimizer
will remain the same for both problems. Consider minimizing
subject to
:

https://wolfram.com/xid/0b8dztxl0i-iplhrk

https://wolfram.com/xid/0b8dztxl0i-qbqu1n

The true minimum value can be obtained by applying the function to the primal minimum value:

https://wolfram.com/xid/0b8dztxl0i-pkk8xy


https://wolfram.com/xid/0b8dztxl0i-l7wv9y
Since , solve the problem with
:

https://wolfram.com/xid/0b8dztxl0i-qd9hxq

The true minimum value can be obtained by applying the function to the primal minimum value:

https://wolfram.com/xid/0b8dztxl0i-fztpat

Data-Fitting Problems (4)
Find a robust linear fit to discrete data by minimizing . Using auxiliary variables
, the problem is transformed to minimize
subject to the constraints
, which is a linear optimization problem:

https://wolfram.com/xid/0b8dztxl0i-p3c1ok


https://wolfram.com/xid/0b8dztxl0i-jk84fy

A plot of the line shows that it is robust to the outliers:

https://wolfram.com/xid/0b8dztxl0i-qvj0ze

Compare with the fit obtained using LeastSquares:

https://wolfram.com/xid/0b8dztxl0i-6m9hox


https://wolfram.com/xid/0b8dztxl0i-fzgkzc

Find a linear fit by minimizing such that the line should pass through the first data point:

https://wolfram.com/xid/0b8dztxl0i-0oucms
By adding the constraint a〚1〛.xb〚1〛, the line is forced to pass through the first point:

https://wolfram.com/xid/0b8dztxl0i-5r63ys

The plot shows that the line passes through the first data point while still maintaining a robust fit:

https://wolfram.com/xid/0b8dztxl0i-mldtt5

Find a robust fit to nonlinear discrete data by minimizing . Generate some noisy data:

https://wolfram.com/xid/0b8dztxl0i-ujbkq1

Fit the data using the bases . The approximating function will be
:

https://wolfram.com/xid/0b8dztxl0i-c8dotz
Find the coefficients of the approximating function:

https://wolfram.com/xid/0b8dztxl0i-1jf1jq

https://wolfram.com/xid/0b8dztxl0i-wco61m

Compare the approximating model with the reference and the least squares fit:

https://wolfram.com/xid/0b8dztxl0i-fraqyp

https://wolfram.com/xid/0b8dztxl0i-c1na99

Find a linear fit to discrete data by minimizing . Since
, by introducing the scalar auxiliary variable
, the problem can be transformed to minimize
, subject to the constraints
:

https://wolfram.com/xid/0b8dztxl0i-bhjray


https://wolfram.com/xid/0b8dztxl0i-thzqe4

The line represents the "best-worst case" fit:

https://wolfram.com/xid/0b8dztxl0i-pz1dcn

The function Fit can be used directly to compute the coefficients:

https://wolfram.com/xid/0b8dztxl0i-43xzj6

Classification Problems (3)
Find a line that separates two groups of points
and
:

https://wolfram.com/xid/0b8dztxl0i-mq8mpw

For separation, set 1 must satisfy and set 2 must satisfy
:

https://wolfram.com/xid/0b8dztxl0i-z9p593


https://wolfram.com/xid/0b8dztxl0i-mm9axc


https://wolfram.com/xid/0b8dztxl0i-qddxuk

Find a quadratic polynomial that separates two groups of points
and
:

https://wolfram.com/xid/0b8dztxl0i-lhfzi6

For separation, set 1 must satisfy and set 2 must satisfy
:

https://wolfram.com/xid/0b8dztxl0i-lf9f0q
The coefficients of the quadratic polynomial are:

https://wolfram.com/xid/0b8dztxl0i-qsox9w


https://wolfram.com/xid/0b8dztxl0i-4tdo74


https://wolfram.com/xid/0b8dztxl0i-45f2kr

Find the minimum-degree polynomial that can separate two sets of points in the plane:

https://wolfram.com/xid/0b8dztxl0i-ckvfyt
Define a polynomial power function that avoids issues when or
is 0:

https://wolfram.com/xid/0b8dztxl0i-kzie1a
Define a function that gives a polynomial of degree with coefficient
as a function of
:

https://wolfram.com/xid/0b8dztxl0i-dfhc7g
The variables for a degree are the coefficients:

https://wolfram.com/xid/0b8dztxl0i-fbgxzm
The constraints enforce separation between set 1 and set 2:

https://wolfram.com/xid/0b8dztxl0i-cb5hbp
For example, the constraints for quadratics are:

https://wolfram.com/xid/0b8dztxl0i-b4de6y

For separation, the only condition is that all the constraints must be satisfied. The objective vector is set to 0:

https://wolfram.com/xid/0b8dztxl0i-fyqq6l

Find a separating polynomial and show it with the points:

https://wolfram.com/xid/0b8dztxl0i-jbxkej


https://wolfram.com/xid/0b8dztxl0i-dbe0h6

Manufacturing Problems (3)
Find the mix of products to manufacture that maximizes the profits of a company. The company makes three products. The revenue per unit, cost per unit and maximum capacity are given by:

https://wolfram.com/xid/0b8dztxl0i-jrblnn
Each product is made using a combination of four machines. The time a machine spends on each product is:

https://wolfram.com/xid/0b8dztxl0i-bjeio

https://wolfram.com/xid/0b8dztxl0i-z3pxi

The profit equals revenue minus cost times the number of units for product
:

https://wolfram.com/xid/0b8dztxl0i-j7rpe7

Each machine can run at most 2400 minutes per week:

https://wolfram.com/xid/0b8dztxl0i-hc78jb
The company makes between zero and the capacity for each product:

https://wolfram.com/xid/0b8dztxl0i-m5i9b
The optimal product mix is given by:

https://wolfram.com/xid/0b8dztxl0i-hxt6ac

The resulting profit is given by:

https://wolfram.com/xid/0b8dztxl0i-r1oktw

The breakdown of machining time for each product is:

https://wolfram.com/xid/0b8dztxl0i-6rqlyh

The same company wants to find out what capacity to change that will have the largest impact on profit. The optimal product mix and profit as formulated previously are given by:

https://wolfram.com/xid/0b8dztxl0i-davq8w
The profit based on the current capacity is:

https://wolfram.com/xid/0b8dztxl0i-41g62q

Extract all the data needed to analyze the impact of the capacity change on profit:

https://wolfram.com/xid/0b8dztxl0i-yfb44

The sensitivity gives the derivative of the profit wrt each of the constraints. Extract the constraints that have any sensitivity at all:

https://wolfram.com/xid/0b8dztxl0i-lldiyc

Extract the sensitive constraints from :

https://wolfram.com/xid/0b8dztxl0i-or2mr6

If the production capacity for product 3 is increased, there should be an increase in profit:

https://wolfram.com/xid/0b8dztxl0i-bgpwzs

https://wolfram.com/xid/0b8dztxl0i-gkd4se

The resulting increase in profit:

https://wolfram.com/xid/0b8dztxl0i-cfqczt

This corresponds exactly to the predicted increase from the sensitivity:

https://wolfram.com/xid/0b8dztxl0i-c3qs40

If the production capacity of product 1, product 2 or both is changed, the profit does not increase:

https://wolfram.com/xid/0b8dztxl0i-p7xm97

https://wolfram.com/xid/0b8dztxl0i-nbmy10

Find the mix of products to manufacture that maximizes the profits of a company. The company makes three products . The revenue per unit is:

https://wolfram.com/xid/0b8dztxl0i-wepo6n
The factory is only open for 100 days. It takes days, respectively, to make each unit:

https://wolfram.com/xid/0b8dztxl0i-tl9r3
Each product contains gold and tin. The total gold and tin available are 30 and 200 units, respectively:

https://wolfram.com/xid/0b8dztxl0i-bdt73t
The company incurs a setup cost for each product if that product is manufactured:

https://wolfram.com/xid/0b8dztxl0i-z7td35
Because of the relatively high setup costs, it may be desirable not to manufacture some of the products at all. Let be a decision variable such that
if product
is manufactured and otherwise
. The limit
ensures that if
is 0, so is
, without limiting the size of
more than other constraints do:

https://wolfram.com/xid/0b8dztxl0i-0nws73
The objective is to maximize the profit:

https://wolfram.com/xid/0b8dztxl0i-hzpc04

https://wolfram.com/xid/0b8dztxl0i-jt2oi4

Transportation Problems (1)
John Conner has learned that Skynet is planning on attacking five settlements. He needs to deploy soldiers from three base camps to the settlements to meet the threat. The fuel cost to transport one soldier from base camp to settlement
is:

https://wolfram.com/xid/0b8dztxl0i-x03zxe

https://wolfram.com/xid/0b8dztxl0i-8x46qf

Let represent the number of soldiers to be shipped from base camp
to settlement
. The cost function to minimize is:

https://wolfram.com/xid/0b8dztxl0i-e7o1xf
Each base camp needs to distribute a maximum of 100 soldiers between the settlements:

https://wolfram.com/xid/0b8dztxl0i-fcr57d
Each settlement needs at least 50 soldiers from a combination of the base camps:

https://wolfram.com/xid/0b8dztxl0i-6wl6l1
The number of soldiers to be deployed from each base camp to each settlement is:

https://wolfram.com/xid/0b8dztxl0i-bj9utg

The breakdown of soldier deployment from each base camp is:

https://wolfram.com/xid/0b8dztxl0i-gwe6nl

Optimal Assignment Problems (2)
The Jedi Order is fighting the separatist armies led by Dooku. Dooku and two of his generals, Asajj Ventress and General Grievous, have attacked three outer colonies. The Jedi Order sends three Jedi to assist the outer colonies. Let be the odds of Jedi
beating Sith
:

https://wolfram.com/xid/0b8dztxl0i-3wsg5r

https://wolfram.com/xid/0b8dztxl0i-gdgk1r

Let be a matrix variable where
is 1 if Jedi
battles Sith
, and 0 otherwise. The cost function is the expected number of defeats given by
and constructed using Inactive[Times]:

https://wolfram.com/xid/0b8dztxl0i-hemao8
Since the outer colonies are far apart, each Jedi may only be assigned to one Sith, and vice versa. Also, since is 0 or 1, then
:

https://wolfram.com/xid/0b8dztxl0i-lurhfc
Find the appropriate Jedi to face the Sith to minimize the chances of defeat:

https://wolfram.com/xid/0b8dztxl0i-zo3bo3

This means that Obi-Wan Kenobi is sent to General Grievous, Mace Windu is sent to Asajj Ventress and Ki-Adi-Mundi is sent to Dooku. The expected number of defeats is:

https://wolfram.com/xid/0b8dztxl0i-5vnvya

Solve a bipartite matching problem between two sets and
that minimizes the total weight:

https://wolfram.com/xid/0b8dztxl0i-dc5ja
Let be a matrix variable, where
is 1 when
is matched to
and 0 otherwise. The total weight of the matching is given by
and constructed using Inactive[Times]:

https://wolfram.com/xid/0b8dztxl0i-jk8ms5
The row and column sums of need to be 1 and also
:

https://wolfram.com/xid/0b8dztxl0i-cfryud
Use LinearOptimization to solve the problem:

https://wolfram.com/xid/0b8dztxl0i-b02x5k

The matching permutation may be extracted by converting the matrix into a graph. Round is used to truncate small values that may occur due to numerical error in some methods:

https://wolfram.com/xid/0b8dztxl0i-ge6m5q
Use the adjacency graph to build a bipartite graph:

https://wolfram.com/xid/0b8dztxl0i-m88s9y

Inventory Control Problems (2)
Find the inventory that a retail store must order for a product per week to minimize cost. Let
be the stock available at the beginning of the week
. Let
be the stock order received from the wholesaler at the beginning of the week
. The cost to purchase one unit from the wholesaler is $3:

https://wolfram.com/xid/0b8dztxl0i-wlgc6n
The cost of holding excess or negative inventory is $1 per unit. The inventory cost is , which is not linear but can be represented as
:

https://wolfram.com/xid/0b8dztxl0i-h1j995
The total cost to minimize is :

https://wolfram.com/xid/0b8dztxl0i-mwt125
Let be the demand at the beginning of the week
. The demand over a period of 52 weeks is given by
for
. The store inventory evolves as
:

https://wolfram.com/xid/0b8dztxl0i-uo377
At week 0, there is an existing inventory units and stock order
units. The store cannot purchase more than 10 units per week from the wholesaler:

https://wolfram.com/xid/0b8dztxl0i-gf7lzk
Find the optimal inventory to keep in store and order from the wholesaler by minimizing cost:

https://wolfram.com/xid/0b8dztxl0i-x164wj
Here is a plot of inventory, stock order and demand that shows that after week 26, the store does not need to carry any inventory, hence minimizing inventory cost:

https://wolfram.com/xid/0b8dztxl0i-dxopmy

Find the inventory that a retail store must order for a product per week to minimize cost without back orders. Let
be the stock order received from the wholesaler at the beginning of the week
. The cost of purchasing one unit from the wholesaler is $3:

https://wolfram.com/xid/0b8dztxl0i-607cut
The cost of holding excess or negative inventory is $1 per unit:

https://wolfram.com/xid/0b8dztxl0i-eze3wi
Let be the demand at the beginning of the week
. The demand over a period of 52 weeks is given by
for
. The store inventory evolves as
:

https://wolfram.com/xid/0b8dztxl0i-2p5jm2
The initial inventory is units and
units, and the maximum purchase from the wholesaler is 10 units:

https://wolfram.com/xid/0b8dztxl0i-ln603s
The company wants to make sure that there are no back orders, i.e. :

https://wolfram.com/xid/0b8dztxl0i-ut65rx
Find the optimal inventory to keep in store and order from the wholesaler by minimizing cost:

https://wolfram.com/xid/0b8dztxl0i-78m2ut
This plot shows that in order to avoid back orders, excess inventory must be purchased earlier in the weeks to meet the demand. The store has no inventory costs by weeks 20–21:

https://wolfram.com/xid/0b8dztxl0i-h77wgt

Structural Optimization Problems (2)
Minimize the weight of a two-beam truss subject to stress and displacement constraints:
The weight is , where
is the density, and
and
are the cross-sectional areas of bar 1 and bar 2. For this problem, assume
:

https://wolfram.com/xid/0b8dztxl0i-ns34ky
The forces acting along the axes of bar 1 and bar 2 are:

https://wolfram.com/xid/0b8dztxl0i-uqdb4j
The stress , where
is the force acting along the bar, must be less than a specified stress
:

https://wolfram.com/xid/0b8dztxl0i-cdf4rk
The displacement at the free node is . The component of this displacement along the axis of the bar must equal the displacement
, where
is Young's modulus:

https://wolfram.com/xid/0b8dztxl0i-u3vhdy
The vertical displacement of the free node must be less than a given :

https://wolfram.com/xid/0b8dztxl0i-fpxwzg
The material being used is aluminium. The design parameters are:

https://wolfram.com/xid/0b8dztxl0i-0newlt
Compute the minimum weight and the optimal cross-sectional areas of the beam:

https://wolfram.com/xid/0b8dztxl0i-xo2zpg

Find the range of angle and length for which the truss weight does not exceed 180 kg:

https://wolfram.com/xid/0b8dztxl0i-sp8rv0

https://wolfram.com/xid/0b8dztxl0i-7pjj0m

Minimize the weight of a two-beam truss subject to stress and displacement constraints, and find the constraints that have a major effect on the design of the truss:
The weight is , where
is the density, and
and
are the cross-sectional areas of bar 1 and bar 2. For this problem, assume
:

https://wolfram.com/xid/0b8dztxl0i-xvg8ob
The constraint due to the forces acting on the bars is:

https://wolfram.com/xid/0b8dztxl0i-4e829t
The material being used is aluminium. The design parameters are:

https://wolfram.com/xid/0b8dztxl0i-3a8lr8
Minimize the weight of the truss by finding the optimal cross-sectional area of the bars:

https://wolfram.com/xid/0b8dztxl0i-m7ch9j

Large constraint sensitivity values indicate a greater influence on the design:

https://wolfram.com/xid/0b8dztxl0i-9n52x9


https://wolfram.com/xid/0b8dztxl0i-3phxq4

The critical constraint influencing the design is the force constraint acting on bar 1:

https://wolfram.com/xid/0b8dztxl0i-47tnct

Sequential Linear Optimization (1)
Minimize a nonlinear function subject to nonlinear constraints
. The minimization can be done by approximating
as
and the constraints as
as
. This leads to a linear minimization problem that can be solved iteratively. Consider a case where
and
:

https://wolfram.com/xid/0b8dztxl0i-8y6k8v
The gradients of the minimizing function and constraints are:

https://wolfram.com/xid/0b8dztxl0i-bacuzk
The subproblem is to find by minimizing
subject to
:

https://wolfram.com/xid/0b8dztxl0i-db44j1
Iterate, starting with an initial guess of . The next iterate is
, where
is the step length to ensure that the constraints are always satisfied:

https://wolfram.com/xid/0b8dztxl0i-o2o4am

Visualize the convergence of the result. The final result is the green point:

https://wolfram.com/xid/0b8dztxl0i-q2t9ta

Sudoku Game (3)
Solve the following sudoku puzzle:

https://wolfram.com/xid/0b8dztxl0i-5jwvhe

Let be the variable for subsquare
. Let
, be the element
of vector
. When
, then
holds the number
. Each
contains only one number, so
can contain only one nonzero element, i.e.
:

https://wolfram.com/xid/0b8dztxl0i-tahviv
Each row must contain all the numbers, i.e. , where
is a nine-dimensional vector of ones:

https://wolfram.com/xid/0b8dztxl0i-yqujs0
Each column must contain all the numbers, i.e. :

https://wolfram.com/xid/0b8dztxl0i-g8cwh0
Each 3×3 block must contain all the numbers, i.e. :

https://wolfram.com/xid/0b8dztxl0i-o6lxog
Collectively, these together make the sudoku constraints for any puzzle:

https://wolfram.com/xid/0b8dztxl0i-bxqv4d

https://wolfram.com/xid/0b8dztxl0i-dlx5ch
Convert the known values into constraints. If subsquare holds number
, then
:

https://wolfram.com/xid/0b8dztxl0i-m0ckua

https://wolfram.com/xid/0b8dztxl0i-ojbgw2

https://wolfram.com/xid/0b8dztxl0i-f72u0h

Generate random sudoku boards by randomly specifying the first row. Define a solver function based on the procedure outlined:

https://wolfram.com/xid/0b8dztxl0i-r7b2rv

https://wolfram.com/xid/0b8dztxl0i-oz9ifr
Find a feasible solution and compare to the starting board:

https://wolfram.com/xid/0b8dztxl0i-xsby0n

Generate sudoku puzzles by randomly generating a board and removing one element at a time. Define a function to solve the sudoku puzzle. If a negative number is specified on the sudoku board, then the function assumes that the number at that position is not allowed:

https://wolfram.com/xid/0b8dztxl0i-4xzibw
Generate a random reference sudoku board by randomly specifying the first row of the board:

https://wolfram.com/xid/0b8dztxl0i-bvnuen

Specify the minimum number of elements to keep:

https://wolfram.com/xid/0b8dztxl0i-uhn61z
Repeatedly remove one randomly selected element from the board at a time until no more elements can be removed without losing the uniqueness of the solution. A removal is tested by solving the sudoku puzzle, with the added condition that the removed element cannot have the removed number. If a feasible solution is found, the number at that position is not unique and the element is retained; otherwise, it is removed from the board:

https://wolfram.com/xid/0b8dztxl0i-ehc8lc
Visualize the resulting puzzle:

https://wolfram.com/xid/0b8dztxl0i-bn8glq

Solve the resulting puzzle and compare with the reference sudoku board:

https://wolfram.com/xid/0b8dztxl0i-goc3e7

Graph-Coloring Problem (1)
Find the minimum number of colors needed to color the nodes of a graph such that no two adjacent nodes have the same color. Start with more than a sufficient number of colors for any graph:

https://wolfram.com/xid/0b8dztxl0i-d5slnm

https://wolfram.com/xid/0b8dztxl0i-mx54yg
Extract the adjacency matrix associated with the graph. Since the matrix is symmetric, only use the upper-triangular part of the matrix:

https://wolfram.com/xid/0b8dztxl0i-8qviqc
Let be a matrix such that
if node
is assigned color
. Let
be a vector such that
if color
is used in the final set. Each node must be given a color:

https://wolfram.com/xid/0b8dztxl0i-c6yai3
If two nodes share an edge, then they both cannot be assigned the same color:

https://wolfram.com/xid/0b8dztxl0i-m73b0s
If node is assigned color
, then color
is used in the final set of colors:

https://wolfram.com/xid/0b8dztxl0i-cia15s
The matrix and the vector
are binary variables:

https://wolfram.com/xid/0b8dztxl0i-rfytw3
Solve the graph-coloring problem:

https://wolfram.com/xid/0b8dztxl0i-sjvlwq
The minimum number of colors used is:

https://wolfram.com/xid/0b8dztxl0i-uy2hq2


https://wolfram.com/xid/0b8dztxl0i-wp1t9y

Set-Covering Problems (3)
Find the combination of doctors a hospital emergency room (ER) must keep on call so that the ER can perform a list of procedures. Each doctor can only perform a certain number of procedures:

https://wolfram.com/xid/0b8dztxl0i-ol1813

The cost for keeping each doctor on call is:

https://wolfram.com/xid/0b8dztxl0i-y2ljxv
Let be a decision vector such that
if doctor
is on call. The objective is to minimize cost:

https://wolfram.com/xid/0b8dztxl0i-5njuy4
At least one doctor must perform procedure :

https://wolfram.com/xid/0b8dztxl0i-5hyt43
Find the combination of doctors to keep on call:

https://wolfram.com/xid/0b8dztxl0i-w0fkyg

Find the minimum number of fire stations that a city containing six districts must build such that there is at least one fire station within 15 minutes of each district. The time required to drive between districts is:

https://wolfram.com/xid/0b8dztxl0i-79z4kh

Let be a decision vector such that
if a fire station is built in district
. The objective is to minimize the number of fire stations:

https://wolfram.com/xid/0b8dztxl0i-2pb8gd
At least one fire station must be within 15 minutes of each district:

https://wolfram.com/xid/0b8dztxl0i-mrw4tq
Find the districts in which a fire station should be built:

https://wolfram.com/xid/0b8dztxl0i-bysyh6

Find the minimum number of storage depots a company needs build to distribute to six of its retail stores. The company has selected five possible storage sites. The cost to supply each store from each depot is:

https://wolfram.com/xid/0b8dztxl0i-2jal6r

The operating cost and construction cost for each depot is:

https://wolfram.com/xid/0b8dztxl0i-3ja8zr
Let be a decision variable such that
if depot
is built. Let
represent the fraction of goods that depot
supplies to store
. The objective is to minimize cost:

https://wolfram.com/xid/0b8dztxl0i-j3o2pj
Depot must supply all of its goods to the selected stores:

https://wolfram.com/xid/0b8dztxl0i-7g29kj
Find which of the five depots should be constructed:

https://wolfram.com/xid/0b8dztxl0i-l6mnxz

Find the depots that will be built:

https://wolfram.com/xid/0b8dztxl0i-q1vyrl

Traveling Salesman Problem (1)
Find the path that a salesman should take through cities such that each city is only visited once and that minimizes the distance. Generate the locations:

https://wolfram.com/xid/0b8dztxl0i-zamrzn
Let be the distance between city
and city
. Let
be a decision variable such that if
, the path goes from city
to city
. The objective is to minimize distance:

https://wolfram.com/xid/0b8dztxl0i-mduy7z
The salesman can arrive from exactly one city and can depart to exactly one other city:

https://wolfram.com/xid/0b8dztxl0i-780msv
The salesman cannot arrive at one city and depart to the same city:

https://wolfram.com/xid/0b8dztxl0i-6yp0jv
The salesman must travel to all the locations in a single tour:

https://wolfram.com/xid/0b8dztxl0i-eqj9wj
The decision variable is a binary variable and the dummy variable is :

https://wolfram.com/xid/0b8dztxl0i-5wz5x5
Find the path that minimizes the distance:

https://wolfram.com/xid/0b8dztxl0i-lwmwmb


https://wolfram.com/xid/0b8dztxl0i-7hg34c


https://wolfram.com/xid/0b8dztxl0i-6glieb

Use FindShortestTour to solve the traveling salesman problem much more efficiently:

https://wolfram.com/xid/0b8dztxl0i-7a0cx7

Properties & Relations (9)Properties of the function, and connections to other functions
LinearOptimization gives the global minimum of the objective function:

https://wolfram.com/xid/0b8dztxl0i-tfrr3g


https://wolfram.com/xid/0b8dztxl0i-id49or

Minimize also gives global exact results for linear optimization problems:

https://wolfram.com/xid/0b8dztxl0i-nh3k1m

NMinimize can be used to obtain approximate results using global methods:

https://wolfram.com/xid/0b8dztxl0i-rp50if

FindMinimum can be used to obtain approximate results using local methods:

https://wolfram.com/xid/0b8dztxl0i-6ce2oe

LinearFractionalOptimization uses LinearOptimization for solving problems:

https://wolfram.com/xid/0b8dztxl0i-hfq6ub

Transform the objective and constraints using :

https://wolfram.com/xid/0b8dztxl0i-lhs1ui

https://wolfram.com/xid/0b8dztxl0i-jdegsi

Obtain the solution to the original problem by applying the inverse transformation:

https://wolfram.com/xid/0b8dztxl0i-q40jls

QuadraticOptimization is a generalization of LinearOptimization:

https://wolfram.com/xid/0b8dztxl0i-xe2wfh


https://wolfram.com/xid/0b8dztxl0i-wl8v3h

SecondOrderConeOptimization is a generalization of LinearOptimization:

https://wolfram.com/xid/0b8dztxl0i-rgvq0j


https://wolfram.com/xid/0b8dztxl0i-f4tv0a

SemidefiniteOptimization is a generalization of LinearOptimization:

https://wolfram.com/xid/0b8dztxl0i-fmsmc6


https://wolfram.com/xid/0b8dztxl0i-495knv

ConicOptimization is a generalization of LinearOptimization:

https://wolfram.com/xid/0b8dztxl0i-w94vev


https://wolfram.com/xid/0b8dztxl0i-u8b73s

Possible Issues (6)Common pitfalls and unexpected behavior
Constraints specified using strict inequalities may not be satisfied:

https://wolfram.com/xid/0b8dztxl0i-n6kzxg

The reason is that LinearOptimization solves :

https://wolfram.com/xid/0b8dztxl0i-dlbd4u

The minimum value of an empty set or infeasible problem is defined to be :

https://wolfram.com/xid/0b8dztxl0i-breti6


The minimizer is Indeterminate:

https://wolfram.com/xid/0b8dztxl0i-uacgr


The minimum value for an unbounded set or unbounded problem is :

https://wolfram.com/xid/0b8dztxl0i-iqfpj3


The minimizer is Indeterminate:

https://wolfram.com/xid/0b8dztxl0i-bc0yq0


Dual related solution properties for mixed-integer problems may not be available:

https://wolfram.com/xid/0b8dztxl0i-jf100q

Mixed-integer problems can only be solved in machine precision:

https://wolfram.com/xid/0b8dztxl0i-w41tvz


Constraints with complex values need to be specified using vector inequalities:

https://wolfram.com/xid/0b8dztxl0i-gw60b6

Just using GreaterEqual will not work:

https://wolfram.com/xid/0b8dztxl0i-btpkne



Wolfram Research (2019), LinearOptimization, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearOptimization.html (updated 2020).
Text
Wolfram Research (2019), LinearOptimization, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearOptimization.html (updated 2020).
Wolfram Research (2019), LinearOptimization, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearOptimization.html (updated 2020).
CMS
Wolfram Language. 2019. "LinearOptimization." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2020. https://reference.wolfram.com/language/ref/LinearOptimization.html.
Wolfram Language. 2019. "LinearOptimization." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2020. https://reference.wolfram.com/language/ref/LinearOptimization.html.
APA
Wolfram Language. (2019). LinearOptimization. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearOptimization.html
Wolfram Language. (2019). LinearOptimization. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearOptimization.html
BibTeX
@misc{reference.wolfram_2025_linearoptimization, author="Wolfram Research", title="{LinearOptimization}", year="2020", howpublished="\url{https://reference.wolfram.com/language/ref/LinearOptimization.html}", note=[Accessed: 06-June-2025
]}
BibLaTeX
@online{reference.wolfram_2025_linearoptimization, organization={Wolfram Research}, title={LinearOptimization}, year={2020}, url={https://reference.wolfram.com/language/ref/LinearOptimization.html}, note=[Accessed: 06-June-2025
]}