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

Introduction

In the context of mathematical optimization, the term “programming” refers to the concept of planning. When the equations involved in the optimization problem are linear, we speak of “linear programming”. The technique of linear programming was first invented by the Russian mathematician L. V. Kantorovich and developed later by George B. Dantzig. NEOS Guide [1] provides an optimization taxonomy, reported in Figure, focused mainly on the subfields of deterministic optimization with a single objective function.

Linear programming deals with optimization problems that are deterministic, continuous and linearly constrained.

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, mixed integer linear programming problems are intrinsically easier to solve than non-linear problem types. The flexibility of MILP is what makes them the widely preferred method in process scheduling problems. However, consider a model has n binary variables, there would be 2^n possible configurations to search from. There are several techniques to speed up the generation of an optimal solution. One of them is the Branch and Bound technique. Initially, the integrality restrictions are removed and the problem is solved as a Linear Programming (LP) problem. This is known as LP relaxation of the original MILP. Usually, a perfect fit for the original problem is not found by simply relaxing the integer constraints. The next step is to select some variable (restricted as an integer), whose optimal value in the LP relaxation is fractional. This becomes the branching variable and we get two different branches, this process is continued till a solution is found which fits the integer bounds, which can be considered the best solution found so far known as incumbent. The generated search tree is explored for other such solutions having better values of the objective function. If they exist we have an optimality gap, otherwise, we have found our optimal solution. The practitioner can also improve the computation runtime by providing integer bounds in the constraint set of the model despite defining them while the decision variable declaration. This helps in cutting planes to prevent undesirable solutions. Some solvers use pre-existing knowledge of the defined problem and tighten the model to get solutions faster. Additionally, heuristic algorithms can be applied to sacrifice optimality and find a solution to the problem faster. This technique provides an initial feasible solution or incumbent to kick-start the search of the optimal solution.

References

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