# Differences

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

Next revision | Previous revision Next revision Both sides next revision | ||

blog:main:mixed_integer_linear_programming [2019/04/21 12:58] dkdutia created |
blog:main:mixed_integer_linear_programming [2019/04/28 20:21] 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. | ||

+ | | ||

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

+ | | ||

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

+ | | ||

+ | | ||

+ | | ||

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

+ | | ||

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

+ | [[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:// | ||