Optimization helps to find the best result, which brings profit, reduces costs or sets a parameter that causes business process failures.
This process is also called mathematical programming. It solves the problem of determining the distribution of limited resources necessary to achieve the goal by the head of the optimization task. Of all the acceptable options, it is desirable to find one that maximizes (or decreases) the controlling parameter, for example, profit or value. Optimization models are also called prescriptive or normative, as they seek to find a possible strategy for the business.
The history of development
Linear programming (LP) works with a class of optimization problems where all constraints are linear.
Presents a brief history of drug development:
- In 1762, Lagrange solved simple optimization problems with equality constraints.
- In 1820, Gauss solved a linear system of equations using exclusion.
- In 1866, Wilhelm Jordan improved the method of searching for least-square errors as a criterion of correspondence. Now this is called the Gauss-Jordan method.
- In 1945, a digital computer appeared.
- In 1947, Danzig invented simplex methods.
- In 1968, Fiakko and McCormick introduced the Inner Point method.
- In 1984, Karmarkar applied the interior method to solve linear programs, adding his own innovative analysis.
LP turned out to be an extremely powerful tool both for modeling real problems and as a widely used mathematical theory. However, many interesting optimization problems are nonlinear.
What to do in this case? The study of such problems includes a diverse mixture of linear algebra, multidimensional calculus, numerical analysis and computational methods. Scientists are developing computational algorithms, including internal point methods for linear programming, geometry, analyzing convex sets and functions, and studying specially structured problems such as quadratic programming.
Nonlinear optimization provides a fundamental understanding of mathematical analysis and is widely used in various fields such as design, regression analysis, inventory management, geophysical exploration and economics.
Classification of optimization problems
An important step in the optimization process is the classification of models, since their decision algorithms are adapted to a specific type.
1. Tasks with discrete and continuous optimization. Some models make sense only if the variables take values from a discrete set of subsets of integers. Others contain data that can take on any real value. They are usually easier to solve. Improvements in algorithms, combined with advances in computer technology, have dramatically increased the size and complexity of the optimization task of linear programming.
2. Unlimited and limited optimization. Another important difference is tasks in which there is no restriction on variables. It can vary widely from simple estimates to systems of equalities and inequalities that model complex relationships between data. Such optimization problems can be further classified by the nature of the functions (linear and nonlinear, convex and smooth, differentiable and non-differentiable).
3. Tasks of feasibility. Their goal is to find the values of variables that satisfy the constraints of the model without any specific optimization goal.
4. Tasks of complementarity. They are widespread in technology and economics. The goal is to find a solution that satisfies the conditions of complementarity. In practice, tasks with several goals are often reformulated into single objective ones.
5. Deterministic versus stochastic optimization. In deterministic optimization, it is assumed that the data for the task is absolutely accurate. However, for many pressing issues they cannot be known for a number of reasons.
The first is due to a simple measurement error. The second reason is more fundamental. It lies in the fact that some data provide information about the future, for example, demand for a product or price for a future period of time. In optimization under stochastic optimization, uncertainty is included in the model.
Main components
The objective function is one that needs to be minimized or maximized. Most types of optimization tasks have one objective function. If not, they can often be reformulated so that they are implemented.
Two exceptions to this rule:
1. The task of finding the goal. In most business applications, the manager wants to achieve a specific goal while satisfying the limitations of the model. The user does not particularly want to optimize something, so it makes no sense to determine the objective function. This type is commonly called the feasibility problem.
2. Many objective functions. Often, the user would like to optimize several different goals at once. Usually they are incompatible. Variables that optimize one goal may not be the best for others.
Component Types:
- Managed input is a set of decision variables that affect the value of the objective function. In a production task, variables may include the distribution of various available resources or the labor required for each action.
- Constraints are the relationships between decision variables and parameters. For a production problem, it does not make sense to spend a large amount of time on any activity, therefore all “temporary” variables are limited.
- Possible and optimal solutions. The value of the solution for the variables at which all constraints are satisfied is called feasible. Most algorithms first find it, then try to improve it. Finally, they modify the variables to move from one feasible solution to another. This process is repeated until the objective function reaches its maximum or minimum. This result is called the optimal solution.
Widely used algorithms for optimization problems developed for the following mathematical programs:
- Convex.
- Shared.
- Quadratic.
- Geometric.
Google Linear Solvers
Linear optimization or programming is the name given to the computational process for the optimal solution to a problem. It is modeled as a set of linear relationships that arise in many scientific and engineering disciplines.
Google offers three ways to solve linear optimization problems:
- Glop Open Source Library.
- Linear Optimization Add-in for Google Sheets.
- Linear Optimization Service in Google Apps Script.
Glop is Google’s built-in linear solver. It is available with open source. You can access Glop through the OR-Tools linear solver packer, which is the shell for Glop.
Linear optimization module for Google Sheets allows you to perform a linear statement of the optimization problem by entering data into a spreadsheet.
Quadratic programming
The Premium Solver platform employs an extended LP / Quadratic version of the Simplex method with restrictions on processing LP and QP tasks up to 2000 variable solutions.
SQP Solver for large-scale tasks uses a modern implementation of the active set method with sparseness to solve quadratic programming (QP) problems. The XPRESS Solver engine uses a natural extension of the "Inside Point" or Newton-Barrier method to solve QP problems.
MOSEK Solver uses the methods of the implemented "Inner Point" and auto-dual. This is especially effective for loosely coupled QP tasks. It can also solve the problems of large-scale quadratic constraint (QCP) and second-order cone programming (SOCP).
Multioperational Computing
They are quite successfully used using the capabilities of Microsoft Office, for example, solving optimization problems in Excel.
In the table above, the following notation:
- K1 - K6 - customers who need to provide goods.
- S1 - S6 are potential production sites that can be built for this. 1,2,3,4,5 or all 6 locations can be created.
For each object there are fixed costs indicated in column I (Fix).
If the location does not change anything, it will not be taken into account. Then there will be no fixed costs.
Identify potential locations to get the lowest cost.
In these conditions, the location is either set or not. These two states are: "TRUE - FALSE" or "1 - 0". There are six states for six locations, for example, only sixth is set for 000001, all for 111111.
In the binary system, there are exactly 63 different variants from 000001 (1) to 111111 (63).
L2-L64 should now have {= MULTIPLE OPERATION (K1)}, these are the results of all alternative solutions. Then the minimum value is = Min (L), and the corresponding alternative is INDEX (K).
Integer CPLEX Programming
Sometimes linear relationships are not enough to grasp the essence of a business problem. This is especially true when solutions include discrete choices, such as opening a warehouse in a specific location or not. In these situations, integer programming is required.
If the problem includes both discrete and continuous choices, this is a mixed integer program. It can have linear, convex quadratic problems and the same second-order constraints.
Integer programs are much more complex than linear ones, but they have important business applications. CPLEX software uses sophisticated mathematical methods to solve integer problems. His methods include a systematic search for possible combinations of discrete variables using linear or quadratic program relaxations to calculate the boundaries of the optimal solution value.
They also use LP and other methods for solving optimization problems to calculate constraints.
Standard Microsoft Excel Solver
This technology uses the basic implementation of the basic Simplex method to solve LP problems. It is limited to 200 variables. Premium Solver uses an improved primary simplex method with two-way boundaries for variables. The Premium Solver platform uses an extended version of LP / Quadratic Simplex Solver to solve an optimization problem with a number of variable solutions up to 2000.
The large-scale LP for the Premium Solver platform uses a modern implementation of the simple and double simplex method, which uses sparseness in the LP model to save time and memory, advanced strategies for updating and refactoring matrices, multiple and partial pricing and rotations, as well as to overcome degeneracy. This mechanism is available in three versions (with the ability to process up to 8,000, 32,000, or an unlimited number of variables and restrictions).
MOSEK Solver includes a primary and dual simplex - a method that also exploits sparseness and uses advanced strategies to update the matrix and "refactorization". It solves problems of unlimited size, has been tested on linear programming problems with millions of variable solutions.
Step-by-step example in EXCEL
To determine the model of the optimization task in Excel, perform the following steps:
- Organize data for the problem in a spreadsheet in a logical form.
- Select a cell to store each variable.
- Create a formula in the cell for calculating the target mathematical model of the optimization problem.
- Formulas are created to calculate the left side of each constraint.
- Use the dialogs in Excel to inform Solver about the decision variables, goals, limitations and the desired boundaries of these parameters.
- Launch Solver to find the best solution.
- Create an Excel worksheet.
- Sort the data for the problem in Excel, where the formula for the objective function and constraint is calculated.
In the above table, cells B4, C4, D4 and E4 were reserved to represent decision variables X 1, X 2, X 3 and X 4. Examples of solutions:
- The product range model (profit for each type of product 450, 1150, 800 and 400 dollars) was introduced in cells B5, C5, D5 and E5, respectively. This allows you to calculate the target in F5 = B5 * B4 + C5 * C4 + D5 * D4 + E5 * E4 or F5: = SUMPRODUCT (B5: E5, B4: E4).
- In B8, the amount of resources required to manufacture each type of product is introduced.
- The formula for F8: = SUMPRODUCT (B8: E8, $ B $ 4: $ E $ 4).
- Copy this formula to F9. $ B $ 4: $ E $ 4 dollar signs indicate that this range of cells remains constant.
- The G8 introduces the available amount of resources of each type, corresponding to the values of restrictions on the right. This allows us to express them like this: F11 <= G8: G11.
- This is equivalent to the four constraints F8 <= G8, F9 <= G9, F10 <= G10 and F11 <= G11. You can enter this set directly in the Solver dialogs along with the non-negativity conditions B4: E4> = 0
Areas of practical application of the method
Linear optimization has many practical applications as an example of an optimization problem:
A company can make several products with a known contribution margin. The production unit of each product requires a certain amount of limited resources. The task is to create a production program to determine how much each product should be produced so that the company's profit is maximum, without violating resource constraints.
Mixing problems are the solution to optimization problems associated with combining ingredients into a final product. An example of this is the diet problem studied by George Danzig in 1947. A number of raw materials are given, for example, oats, pork and sunflower oil, as well as the content of nutrients in them, for example, protein, fat, vitamin A and their price per kilogram. The challenge is to mix one or more finished products from raw materials with minimal costs, subject to the minimum and maximum limits for their nutritional value.
A classic application of the linear optimization problem is to determine the routing for traffic needs in telecommunication or transport networks. In this case, the flows must be routed through the network so that all traffic requirements are met without violating the bandwidth conditions.
In the framework of mathematical theory, linear optimization can be used to calculate optimal strategies in zero-sum games for two people. In this case, the probability distribution for each participant is calculated, which is the coefficient of random mixing of his strategies.
Without optimization, no successful business process in the world is possible. There are many optimization algorithms available. Some methods are only suitable for certain types of problems. It is important to be able to recognize their characteristics and select the appropriate solution method.