Linear Programming#

Overview#

Linear Programming (LP, also called linear optimization) is a tool to solve linear programs, i.e., achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Potential applications include product mix optimization, portfolio optimization, inventory optimization, etc.

Linear programs can be formulated as follows:

\[\begin{split} \begin{array}{ll} \text{Find a vector} & \mathbf{x} \\ \text{that maximizes} & \mathbf{c}^\mathsf{T} \mathbf{x} \\ \text{subject to} & \mathbf{A} \mathbf{x} \leq \mathbf{b} \\ \text{and} & \mathbf{x} \geq \mathbf{0}. \end{array} \end{split}\]

In this standard formulation, \(\mathbf{x}\) is a vector of the variables to be determined, \(\mathbf{c}\) and \(\mathbf{b}\) are given vectors of the coefficients, and \(\mathbf{A}\) is a given matrix.

Linear Programming requires a formula cell evaluating the objective function \(\mathbf{c}^\mathsf{T} \mathbf{x}\) based on the variable cells. Bounds and constraints of variables can also be added if applicable. Linear Programming also supports mixed-integer linear programming (MILP) where some variables can be restricted to be integers. These integer constraints are frequently used in real world examples, e.g., the numbers of products should be integers.

Compared to General Optimizer, Linear Programming can only be applied to linear programs, but it is more efficient to solve this specific type of problem.

Videos#

Note

Video goes here.

Examples#

Here is a step-by-step example of using Linear Programming to solve a 2D mixed-integer problem:

\[\begin{split} \begin{array}{ll} \text{Find} & x_1 \in \mathbb{Z}, x_2 \in \mathbb{R} \\ \text{that maximizes} & x_1 + x_2 \\ \text{subject to} & 5 x_1 + 2 x_2 \leq 30 \\ & 2 x_1 + 5 x_2 \leq 30 \\ \text{and} & x_1, x_2 \geq \mathbf{0}. \end{array} \end{split}\]

  1. Prepare an Excel sheet with cells of objective function, variables, bounds and constraints.

    The following formula cells must use the format of =SUMPRODUCT(__:__,__:__) so that the solver can find the coefficients by parsing the formula.

    • Objective function at A3: =SUMPRODUCT(C3:C4,B3:B4)

    • Constraint left-hand side at D6: =SUMPRODUCT(C3:C4,D3:D4)

    • Constraint left-hand side at E6: =SUMPRODUCT(C3:C4,E3:E4)

  2. Open Finplicity, and then click Optimize > Linear Programming. The form of Linear Programming will appear, as shown below.

  3. In Step 1, select the Excel cell for the objective function. In this example, select A3.

  4. In Step 1, select “Maximize” if you want to maximize the objective function or “Minimize” if you want to minimize. In this example, select “Maximize.”

  5. In Step 1, select the variable cells from the dropdown menu. The two provided options are the arguments of the SUMPRODUCT function in the objective function cell. In this example, select C3:C4. Now you have finished the first step in this form as shown below, and you can click “Next” to continue.

  6. In Step 2, select the integer constraints. In this example, select “Custom” and then select F3:F4. Now you have finished the second step in this form as shown below, and you can click “Next” to continue.

  7. In Step 3, select the lower bounds and the upper bounds. In this example, select G3:G4 and H3:H4. Now you have finished the third step in this form as shown below, and you can click “Next” to continue.

  8. In Step 4, add the constraints. Note that one side of the constraint must be a formula cell in the =SUMPRODUCT(__:__,__:__) format, and the other side must be a constant number.

    • If you click “Add,” you can add constraints by selecting the left-hand side, the symbol, and the right-hand side.

    • If you click “Add Boolean,” you can add Boolean constraints, which are formula cells (e.g., =D6<=D8 and =E6<=E8 in this example) evaluating whether the constraints are satisfied.

    In this example, click “Add,” select D6:E6, <=, D8:E8, and click “Save” to add the constraints.

  9. Now you have finished all the steps in this form, and you can click “Run” to run optimization solver or click “Save” to save this task. Below is the optimization result. As you can see, the maximum 8.4 can be achieved with C3=4, C4=4.4.

FAQ#

  • How to implement the formula of the objective function/constraint using SUMPRODUCT?

First, put all variables into a row/column of cells, e.g., C3:C4. Then, put all linear coefficients into a row/column of cells, e.g., B3:B4. Finally, use SUMPRODUCT and the two rows/columns to compute, e.g., use =SUMPRODUCT(C3:C4,B3:B4) to compute B3*C3+B4*C4.

  • Why is it necessary to use SUMPRODUCT in the formula?

Unlike General Optimizer, Linear Programming parses the formula, extracts the linear coefficients, and evaluates the formula by the solver itself, instead of directly by Excel. While this strategy improves efficiency, it is hard to parse an arbitrary formula and hence we require a standard format: =SUMPRODUCT(__:__,__:__). Note that the two arguments should be both column/row vectors, without any further nested functions.

  • Is it necessary to provide initial values of variables?

No.

  • What if my linear program has no bounds/constraints?

Bounds and constraints are not required in Linear Programming, and you can directly click the “Next” button to skip the corresponding step. Consider using a reasonably large upper bound when the variable only has a lower bound, and vice versa. Although bounds and constraints are not required, they cannot be both empty, otherwise the optimum will be infinite.

  • What if I input wrong bounds/constraints by accident?

For bounds, re-select the area or click “Delete bounds”. For constraints, select the wrong constraints and click “Delete” or “Edit.”

  • Does Linear Programming guarantee to find a solution?

No, especially for large-scale or ill-formed linear programs. If it takes too long or just fails, here are a few things to try. (1) Check formula format. (2) Make sure the optimum is finite. (3) Relax some of the constraints (especially integer constraints).

  • Why do I get an error “Please make sure you have inputted correctly in your constraints and objective function”?

This happens if a formula is not successfully parsed. Please make sure your constraints and objective function are formula cells in the standard format: =SUMPRODUCT(__:__,__:__). Read more in “FAQ: Why is it necessary to use SUMPRODUCT in the formula?.”

  • Why do I get an error “Warning: Optimization did not successfully terminate.”?

One of the most common reasons why the optimization failed is that the optimizer cannot even find a feasible solution that satisfy all constraints, not to mention optimizing. A simple example is requiring x <= 0 and x >= 1 at the same time. To fix this problem, try to relax some of the constraints (especially equality constraints & integer constraints). Moreover, please make sure your constraints and objective function are formula cells in the standard format =SUMPRODUCT(__:__,__:__). Note that the two arguments should be both column/row vectors, without any further nested functions.

On this page