Mixed Integer Linear Programming

The typical flow of thought undergoing in a human mind is constantly planning the things to be done: within a certain time-frame, before the deadline, increasing profits, minimizing the travel redundancies along-with routine survival chores. Such parallel processing and/or planning are not yet mastered by robots. The field of mathematics which deals with this situation is Mathematical Optimization a.k.a. Linear Programming.

*Keywords:* Operations research, mathematical optimization, linear programming, mathematical modeling

The term programming means planning and linear implies that all equations involved in a problem would be linear. The technique of linear programming first invented by the Russian Mathematician L. V. Kantorovich and developed later by George B. Dantzig. Linear Programming is a mechanism for mathematical modeling and optimizing decisions. NEOS Guide [2] provides an optimization taxonomy, see Figure, focused mainly on the subfields of deterministic optimization with a single objective function.

Linear programming is, thus, deterministic, continuous and linearly constrained optimization.

A linear programming problem is one in which some function is either maximized or minimized relative to a given set of alternatives. The function to be minimized or maximized is called the objective function and the set of alternatives is called the feasible region determined by a system of linear inequalities (constraints).

Mixed integer refers to the combination of integers and continuous decision variables.

Since all linear functions are convex, linear programming problems are intrinsically easier to solve than general nonlinear (NLP) problems, which may be non-convex. In a non-convex NLP, there may be more than one feasible region and the optimal solution might be found at any point within any such region. In contrast, an LP has at most one feasible region with 'flat faces' (i.e. no curves) on its outer surface, and the optimal solution will always be found at a 'corner point' on the surface where the constraints intersect. This means that an LP Solver needs to consider many fewer points than an NLP Solver, and it is always possible to determine (subject to the limitations of finite precision computer arithmetic) that an LP problem (i) has no feasible solution, (ii) has an unbounded objective, or (iii) has a globally optimal solution (either a single point or multiple equivalent points along a line).

List of Solvers

1. MATLAB
2. IBM CPLEX
3. Gurobi
4. AMPL
5. Artelys Knitro for Knitro
6. COIN-OR
7. FICO for the Xpress Optimization Suite
8. GAMS
9. Lindo Systems, Inc. for LINDOGlobal
10. Mosek
11. OpenSolver

Linear Programming CPLEX Tutorial

[1] “Morgridge Institute for Research and Wisconsin Institute for Discovery, NEOS Server, ”https://neos-guide.org/.