# Differences

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

Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||

blog:main:mixed_integer_linear_programming [2019/04/21 16:07] dkdutia |
blog:main:mixed_integer_linear_programming [2019/04/28 20:22] dkdutia |
||
---|---|---|---|

Line 7: | Line 7: | ||

=== Introduction === | === Introduction === | ||

- | 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. | + | In the context of mathematical optimization,term "programming" refers to the concept of planning. When the 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.__ | + | __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).// | + | 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. |

- | 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 //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//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,. |

=== Discussion === | === 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 ' | + | "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:// |

=== Solvers === | === 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:// | [[https:// | ||

- MATLAB | - MATLAB |