Linear Programming Explanation
In this section, you’ll learn the basics of linear programming and a related discipline, mixed-integer linear programming. In the next section, you’ll see some practical linear programming examples. Later, you’ll solve linear programming and mixed-integer linear programming problems with Python.
What Is Linear Programming?
Imagine that you have a system of linear equations and inequalities. Such systems often have many possible solutions. Linear programming is a set of mathematical and computational tools that allows you to find a particular solution to this system that corresponds to the maximum or minimum of some other linear function.
What Is Mixed-Integer Linear Programming?
Mixed-integer linear programming is an extension of linear programming. It handles problems in which at least one variable takes a discrete integer rather than a continuous value. Although mixed-integer problems look similar to continuous variable problems at first sight, they offer significant advantages in terms of flexibility and precision.
Integer variables are important for properly representing quantities naturally expressed with integers, like the number of airplanes produced or the number of customers served.
A particularly important kind of integer variable is the binary variable. It can take only the values zero or one and is useful in making yes-or-no decisions, such as whether a plant should be built or if a machine should be turned on or off. You can also use them to mimic logical constraints.
Why Is Linear Programming Important?
Linear programming is a fundamental optimization technique that’s been used for decades in science- and math-intensive fields. It’s precise, relatively fast, and suitable for a range of practical applications.
Mixed-integer linear programming allows you to overcome many of the limitations of linear programming. You can approximate non-linear functions with piecewise linear functions, use semi-continuous variables, model logical constraints, and more. It’s a computationally intensive tool, but the advances in computer hardware and software make it more applicable every day.
Often, when people try to formulate and solve an optimization problem, the first question is whether they can apply linear programming or mixed-integer linear programming.
Some use cases of linear programming and mixed-integer linear programming are illustrated in the following articles:
The importance of linear programming, and especially mixed-integer linear programming, has increased over time as computers have gotten more capable, algorithms have improved, and more user-friendly software solutions have become available.
The basic method for solving linear programming problems is called the simplex method, which has several variants. Another popular approach is the interior-point method.
Mixed-integer linear programming problems are solved with more complex and computationally intensive methods like the branch-and-bound method, which uses linear programming under the hood. Some variants of this method are the branch-and-cut method, which involves the use of cutting planes, and the branch-and-price method.
There are several suitable and well-known Python tools for linear programming and mixed-integer linear programming. Some of them are open source, while others are proprietary. Whether you need a free or paid tool depends on the size and complexity of your problem as well as on the need for speed and flexibility.
It’s worth mentioning that almost all widely used linear programming and mixed-integer linear programming libraries are native to and written in Fortran or C or C++. This is because linear programming requires computationally intensive work with (often large) matrices. Such libraries are called solvers. The Python tools are just wrappers around the solvers.
Python is suitable for building wrappers around native libraries because it works well with C/C++. You’re not going to need any C/C++ (or Fortran) for this tutorial, but if you want to learn more about this cool feature, then check out the following resources:
출처 : realpython.com/linear-programming-python/#linear-programming-explanation
'optimizer > linear programming' 카테고리의 다른 글
| Linear Programming Solvers (0) | 2021.04.19 |
|---|---|
| Linear Programming Resources (0) | 2021.04.19 |