Optimise a plan

Status

Variants

Simulate outcomes

Sample inputs or model errors from distributions and summarise the outcomes.

Solve an optimisation problem

Find the inputs that maximise or minimise an objective under constraints.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

Industries that use linear programming models include transportation, energy, telecommunications and manufacturing.^[2] Linear programming has proven useful in modelling problems in planning, routing, scheduling, assignment and design.^[2] Linear programming is used to achieve the best outcome, such as maximum profit or lowest cost, in a mathematical model whose requirements and objective are linear.^[2]

A linear program need not have an optimal solution: if its constraints are inconsistent, no feasible solution exists and the program is called infeasible.^[2] A linear program can also attain no optimal value when the region its constraints allow is unbounded in the direction the objective improves, because it is always possible to do better than any finite value.^[2]

When some or all variables must be integers, as in an integer program, solving without that requirement and rounding the answer may give a result that is not optimal or that violates a constraint.^[4] Where a plan counts whole things, such as lorries, staff or shipments, say so in the model rather than rounding a continuous answer afterwards. (Meridian's view)

A local minimum is at least as good as any nearby element, while a global minimum is at least as good as every feasible element.^[1] Unless the objective function is convex in a minimisation problem, there may be several local minima.^[1] Many algorithms for nonconvex problems, including the majority of commercially available solvers, cannot distinguish locally optimal solutions from globally optimal ones.^[1] With a nonlinear objective, treat a solver's answer as the best it found, not as proof that nothing better exists. (Meridian's view)

For Monte Carlo integration, quadrupling the number of sampled points halves the error, regardless of the number of dimensions.^[3] Choose the number of simulation runs from how precise the summary needs to be, since precision is bought slowly. (Meridian's view) Alteryx Designer's Simulation Sampling tool takes a random seed for its sampling and a number of iterations, the number of samples to select.^[5] Keep the seed with a simulation's results, so that the same draws can be made again and a change in the outcome can be traced to a change in the model. (Meridian's view)

The method

Linear programs can be expressed in standard form as finding a vector of variables that maximises a linear objective subject to linear inequality constraints and non-negativity of the variables.^[2] In the late 1930s, Soviet mathematician Leonid Kantorovich and American economist Wassily Leontief independently delved into the practical applications of linear programming.^[2] From 1946 to 1947 George B. Dantzig independently developed a general linear programming formulation for planning problems in the US Air Force.^[2] In 1947 Dantzig also invented the simplex method, which for the first time efficiently tackled the linear programming problem in most cases.^[2]

Leonid Khachiyan first showed in 1979 that the linear programming problem is solvable in polynomial time, and in 1984 Narendra Karmarkar introduced an interior-point method for solving linear programming problems.^[2] The simplex algorithm finds an optimal solution by traversing the edges between vertices on a polyhedral set, whereas interior-point methods move through the interior of the feasible region.^[2] The current opinion is that good implementations of simplex-based methods and interior-point methods are similar in efficiency for routine applications of linear programming.^[2]

If only some of the variables are required to be integers, the problem is called a mixed integer linear programming (MILP) problem.^[2] Cutting plane methods solve the LP relaxation of an integer program, the same problem without the integer requirement, and add linear constraints that drive the solution towards integers without excluding any integer feasible point.^[4] Branch and bound algorithms can be terminated early and, as long as at least one integral solution has been found, return a feasible, although not necessarily optimal, solution.^[4] In branch and bound, the solutions of the LP relaxations can be used to give a worst-case estimate of how far from optimality the returned solution is.^[4]

HiGHS is open-source serial and parallel software for solving large-scale sparse linear programming, mixed-integer programming and quadratic programming models, freely available under the MIT licence.^[6] HiGHS is based on a dual revised simplex solver developed by Qi Huangfu, an interior point solver developed by Lukas Schork, an active set solver for quadratic programs written by Michael Feldmeier and a branch-and-cut solver for mixed-integer programs written by Leona Gottwald.^[6]

The secret work of John von Neumann and Stanisław Ulam needed a code name, and their colleague Nicholas Metropolis suggested Monte Carlo, after the Monte Carlo Casino in Monaco.^[3] Von Neumann, Metropolis and others programmed the ENIAC computer to perform the first fully automated Monte Carlo calculations, of a fission weapon core, in the spring of 1948.^[3] Pseudo-random number sampling algorithms transform uniformly distributed pseudo-random numbers into numbers distributed according to a given probability distribution.^[3]

Alteryx Designer's Simulation Sampling tool samples data parametrically from a distribution, from input data, or as a combination best fitting to a distribution.^[5] Alteryx Designer's Simulation Sampling tool offers Monte Carlo or simple sampling, and Latin hypercube or stratified sampling.^[5] Alteryx Designer's Simulation Scoring tool samples from an approximation of a model's error distribution, so that it gives a range of possible values rather than only the mean predicted value.^[7]

Compared with the alternatives

Prescriptive analytics is the third and final phase of business analytics, which also includes descriptive and predictive analytics.^[8] Predictive analytics answers the question of what is likely to happen.^[8] Prescriptive analytics goes beyond predicting future outcomes, also suggesting actions to benefit from the predictions and showing the implications of each decision option.^[8] Rapidminer's Prescriptive Analytics operator reverses predictive modelling: starting with a model and a desired output, it prescribes an optimised input to achieve the desired outcome.^[9] Rapidminer's Prescriptive Analytics operator uses an evolutionary optimisation method based on the model.^[9]

Sources

1. [1]Mathematical optimization - Wikipediasecondary source
2. [2]Linear programming - Wikipediasecondary source
3. [3]Monte Carlo method - Wikipediasecondary source
4. [4]Integer programming - Wikipediasecondary source
5. [5]Simulation Sampling Tooldocumentation
6. [6]HiGHS - High-performance parallel linear optimization softwaredocumentation
7. [7]Simulation Scoring Tooldocumentation
8. [8]Prescriptive analytics - Wikipediasecondary source
9. [9]Prescriptive Analytics - Rapidminer Documentationdocumentation