1. Mathematical Optimization#
What is mathematical optimization?#
Mathematical optimization is a broad term describing a way of mathematically describing decision problems and then solving them using dedicated algorithms. Optimization models consist of three parts:
the decision variables, which correspond to actions or choices that we can make in our decision problem: whether to open a new manufacturing facility, which supply routes to use, or for which prices we should sell our products.
the objective function, which is used to evaluate a specific solution (i.e. a specific choice of values for the decision variables introduced earlier). For the objective function, a âgoalâ should be specified, either maximize or minimize it. In other applications, the objective can be to minimize operational costs or to maximize the number of satisfied customers.
the constraints that restrict the possible values of our decision variables, i.e., conditions that must be satisfied. Other common examples of constraints are to require that a maximum allowed budget is satisfied, that all demand of important customers is met, or that the capacities of warehouses are not exceeded.
Both the objective function and the constraints are expressed as functions of the decision variables. The constraints define the feasible region of a model, i.e., the set of all candidate solutions that meet the constraints.
The goal of an optimization model is to find the best solution â the global optimum â among the values for the decision variables that meet all the constraints.
Applied mathematical optimization requires three types of skills, which can be related to three fundamental questions:
What to model? First, the modeler must translate a problem from the real world to an abstract mathematical representation. Not every aspect of the real world can or should be taken into account by the model, so there are many choices to be made in this first step, which typically have a significant impact on the model and solution approach.
How to model? There can be multiple equivalent model formulations. Conceptually, equivalent models solve the same optimization problem, but the applicable solution approaches or computational complexity may differ.
How to interpret the modelâs solution? After solving the model, the solution has to be evaluated and translated back to the original real-world problem
These three aspects should be treated as a continuous process, not as sequential steps. For example, if the final solution turns out to be impractical, we need to adjust the model. If certain desired properties cannot be modeled efficiently, perhaps we should re-evaluate what to include in the model. A mathematical model is a tool, not a goal (well, except for mathematicians to study). A model is âalways flawedâ and our challenge is to make a model useful.
Mathematically, we can describe optimization problems as follows. Given an objective function \(f: X \to \mathbb{R}\) to be minimized, with \(X\subseteq \mathbb R^n\) being the feasible region of candidate solutions, we seek to find \(x \in X\) satisfying the following condition \(f(y) \geq f(x) \: \forall \, y \in X\), i.e., that the solution we find is at least as good as all other possible solutions. Similarly, we can define a maximization problem by changing the last condition into \(f(y) \leq f(x) \: \forall \, y \in X\). In both cases, we refer to such solutions as optimal solutions. The general way to formulate a minimization problem is:
and similarly for a maximization problem. Different types of function \(f\) and set \(X\) lead to different types of optimization problems and to different solution techniques.
In this introductory chapter, we present a simple example of optimization in the context of production planning, which serves also as a tutorial introduction to optimization in the Python programming language and the AMPL optimization modeling language.
Go to the next chapter about linear optimization.