# Differences

This shows you the differences between two versions of the page.

Next revision | Previous revision | ||

blog:main:mixed_integer_linear_programming [2019/04/21 12:58] dkdutia created |
blog:main:mixed_integer_linear_programming [2019/06/02 22:04] dkdutia |
||
---|---|---|---|

Line 1: | Line 1: | ||

====== Mixed Integer Linear Programming ====== | ====== Mixed Integer Linear Programming ====== | ||

- | 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. NEOS Guide [2] provides an optimization taxonomy, see Figure, focused mainly on the subfields of deterministic optimization with a single objective function. | + | 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, | ||

+ | | ||

+ | \\ | ||

+ | === Introduction === | ||

+ | | ||

+ | In the context of mathematical optimization,equations involved in the optimization problem are linear, we speak of ". 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 is, thus, deterministic,optimization. Mixed integer refers to the combination of integers and continuous decision variables. 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). | + | __Linear programming deals with optimization problems that are deterministic,__ |

+ | | ||

+ | 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. | ||

+ | | ||

+ | Below is an example of a MILP model. | ||

+ | {{ : | ||

+ | | ||

+ | | ||

+ | \\ | ||

+ | Equation 1 represents the objective function of the formulation, | ||

+ | | ||

+ | | ||

+ | \\ | ||

+ | === Discussion === | ||

+ | > "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 ' | ||

+ | | ||

+ | [[https:// | ||

+ | | ||

+ | \\ | ||

+ | The flexibility of MILP is what makes them the widely preferred method [2] 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 tightening the formulation by removing undesirable fractional solutions, termed as *cutting planes*. Some solvers use pre-existing knowledge of the defined problem and tighten the model to get solutions faster. Additionally, | ||

+ | | ||

+ | \\ | ||

+ | === Solvers === | ||

+ | Several commercial and open source optimization solvers are available in the user can simply focus on formulating the model rather than dealing with details of the actual solution algorithm. Notable software includes IBM ILOG CPLEX Optimization Studio and Gurobi Optimizer. These have optimization IDE as well as support to a model in other languages like C++, Python, MATLAB, R, etc. | ||

+ | | ||

+ | | ||

+ | [[https:// | ||

+ | - MATLAB | ||

+ | - IBM CPLEX | ||

+ | - Gurobi | ||

+ | - AMPL | ||

+ | - Artelys Knitro for Knitro | ||

+ | - COIN-OR | ||

+ | - FICO for the Xpress Optimization Suite | ||

+ | - GAMS | ||

+ | - Lindo Systems, Inc. for LINDOGlobal | ||

+ | - Mosek | ||

+ | - OpenSolver | ||

+ | \\ | ||

+ | === Useful Resources === | ||

+ | [[https:// | ||

+ | [[https:// | ||

+ | \\ | ||

=== References === | === References === | ||

[1] “Morgridge Institute for Research and Wisconsin Institute for Discovery, NEOS Server, ”https:// | [1] “Morgridge Institute for Research and Wisconsin Institute for Discovery, NEOS Server, ”https:// | ||

+ | [2] C. A. Floudas and X. Lin, “Mixed integer linear programming in process scheduling: | ||