Linear programming problem has the form of

If the formulation contains anything nonlinear (strictly speaking, non-convex), it cannot be solved easily in general. This is helpful to write the problem in a modelling language like AMPL and feed into a LP solver.

Minima and Maxima

If a minimum or maximum function is involved, e.g.

it can be linearized by introducing an additional variable and the constraints

Minimax objective

Minimizing the objective function of can be transformed into minimizing the decision variable with extra constraints defining z:

Absolute values

In case any absolute value of a free variable (i.e. ) is involved, say , we may convert it by introducing additional variables , and additional constraints:

If we minimize the sum of and in objective function, one of them will be equal to zero. This will not work for maximization problem or problem without objective functions. For the latter, simple minimize for the sum of non-negative parts converted. For the former, switch the problem into minimization of negative of objective function.

Fractions in objective function

This is a method introduced by A. Charnes and W.W. Cooper in their paper, Programming with Linear Fractional Functional, Naval Research Logistics Quaterly, Vol.9 pp.181–186, 1962.

Consider the case that a faction of polynomials is at the objective, e.g.

We define

and change the problem into:

In other words, we linearize the objective function by substituting for , and convert all existing constraints by multiplying them with . Finally, we introduce the additional constraint that multiply by the denominator of the original fraction shall equal to one.

In such a converted problem, the decision variables are transformed into , together with the newly introduced variable , we can recover after the solution is found.

Either-or constraints

Either or but not necessarily both as constraints: We can find some fairly large bounds such that we are quite sure and in the domain we concerned. Then set up:

for an extra binary variable . Similar binary variable trick can be applied to objective functions that takes different value based on some conditions. If the two constraints are mututally exclusive, however, we should add

The bounds with binary variable trick can help imposing constraints like both-or-nothing as well. Below is an example of imposing exactly out of constraints active:

Multiplication

Multiplication in general cannot be linearized. However, if one of the two multiplicands is range-bounded, their product can be converted into linear form.

Let’s introduce for the product :

and notice that

Then we can convert a multiplication into difference of variables and , on the condition that their introduction can make the system remain linear.

Alternatively, consider , which is a free variable (or lower-bounded only) but . Then we have

or, by realizing that ,

Thus we can replace the product by using the RHS of the above inequalities, optionally with some modification to the corresponding constraint to reflect the substitution is not exact.

In the particular case of binary variables, say, the product , it can be replaced by a new binary variable such that:

In another case of a binary variable multiply by a bounded real number , the product can be replaced by a new variable such that:

For other cases, such as multiplication of two unbounded real number, we may need approximation techniques, i.e. approximate a convex curve by piecewise linear functions.

Discontinuity, Indicator Variables, and Upper-Bounds (MILP)

Let the range of a decision variable to be either or which . We may introduce an indicator variable to represent this:

Another case that indicator variables can apply is a conditional equation. Let there be a quantity

Then we can replace the definition of by

for a fairly large value to serve as the upper-bound of .

The introduction of an upper-bound is useful to incorporate exotic constraints in the linear programming. For example, either one of two constraints must be satisfied, but not necessarily both. Say, we have the following constraints:

where at least one of them must be satisfied. Then we can introduce an upper-bound and an indicator variable to invalidate one of them, i.e.

In general, we can mandate at least out of such constraints must be satisfied:

This provide each constraint with an independent indicator variable , which tells if it have to be relaxed. Thus we can control the least number of constraints satisfied () by controlling the most number of constraints not satisfied ().

A variation of such either-or constraints is the all-or-nothing constraints. Consider the two constraints case above, if it is an all-or-nothing rule, it means an either-or rule for the below:

Similarly, for the case of -constraints case, the all-or-nothing rule means

Reference

H.P. Williams, Model building in mathematical programming, 5th ed., John Wiley & Sons, 2013.