Introduction to optimization
Very often, the problem is stated in a raw way, that is to say by a text or a specification. The industrial was not expert in the field of writing a mathematical problem, the specifications include all kinds of data, useful or not for its modeling.
Even where you are a sponsor, you may not know the extent of your problem, and you may discover over time various constraints and variables.
Another problem is when the mathematical modeling is done: what computer tool is used to solve this problem? which algorithm to choose? its simulation? its complexity? its optimality?
Optimization and decision making
Constructing an optimization problem
To better understand both notions, let’s take an example:
This kind of problem has different ways to be modeling according to what one wishes to do: to be the fastest, to favor densely tourist areas, etc. It is necessary to select a decision among a set of possible decision so as to optimize the chosen criterion.
The problem is studied in a certain context that will be translated into parameters. All relationships between those are represented in the model. The latter can either take the form of a mathematical model or a graph.
The modeling is only a schematic representation of the problem, only the elements deemed relevant are retained in the construction of the decision. It proceeds by simplifications and omissions.
The model environment can also play a role. Whether deterministic or uncertain, it is present via laws of probability, stochastic, and so on within the constraints.
The selection criterion can lead to different solutions depending on the parameter put forward. In some cases, the model has only one criterion, which is called operational research.
All models are made up of three basic components:
- Result variables are outputs. The reflect the level of effectiveness of the system. These are dependent variables.
- Decision variables describe alternative actions.
- Uncontrollable variables are factors that affect the result but are not under control of the decision maker. Either these factors are fixed or they can vary.
The components are linked together by mathematical expressions in a structure of quantitative models. A principle of choice is a criterion that describes the acceptabilité of a solution approach.
A model can be a normative model or a descriptive model. In the first one, the chosen solution is demonstrably the best of all possible alternatives. To find it, one should examine all alternatives and prove that the one selected is indeed the best one. The process is basically Optimization. Descriptive models investigate alternate actions under different configurations of inputs and processes. All the alternatives are not checked, only a given set are.
Modeling a problem
Depending on the mathematical modeling, the model can also be used as simulation. It is then possible to see the impact of certain decisions in a context different from the one studied (like the study of sensitivity of the simplex).
Decision making involves three major phases followed by the validation phase:
- Information gathering: To examine and to identify the problem (variables, functions, values, etc.).
- Problem identification: Identification of organized goals and objectives related to an issue. To determine whether a problem exists, identify its symptoms, determine its magnitude, and explicitly define it. Some issues may arise during data collection and estimation like lack of data, inoccurate or inprecise data, bad estimation, information overload, only simulated data, etc.
- Problem classification: Problem classification is the placement of a problem in a definable category. This leads to a standard solution approach.
- Problem decomposition: Many complex problems can be divided into sub-problems. Some unstructured problems may have some highly structured sub-problems.
- Design: To construct a model that represents the system.
- To understand the problem: Modelling involves abstracting the problem to quantitative and/or qualitative forms.
- A model is constructed, tested, and validated: For a mathematical model, the variables are identified and the relationships among them are established. All models are made up of three basic components: decision variables, uncontrollable variables, and result variables. Mathamtical relationships link these components together. In a non-quantitative model, the relationships are symbolic or qualitative.
- Choice: To select a solution to the model.
- Recommendation of a solution: When the problem is solved, a solution is chosen based on the model. This one is recommended over the set of solutions.
- Evaluation of a solution: Evaluation is possible if the result variables give a quantitative solution. A preference relation over the set of solution give an order: f(a)⪯ f(b) means that f(b) is better or equal to f(a) where a, b are variables and f(.) is a mathematical function based on result variables. b is the best solution iff: f(x)⪯f(b) for any x in the set of solution.
- Implementation: To implemente a software to solve any instance of the model.
- Classic, iterative implementation: Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems.
- Recursion: A recursive algorithm is one that makes reference to itself repeatedly until a termination condition matches.
- Logical: A logical algorithm is composed by logic component and control component.
- Deterministic or non-deterministic: Deterministic algorithms solve the problem with exact decision at every step of the algorithm whereas non-deterministic algorithms solve problems via guessing. A deterministic algorithm is an algorithm which, given a particular input, will always produce the same output.
- Exact or approximate: While many algorithms reach an exact solution, approximation algorithms seek an approximation that is close to the true solution. When it is not possible to find a best solution in human time, one can seek for an approximate solution by less complex algorithms.
- Serial, parallel or distributed: Those implementations depend of computer architectures, i.e. number of processors that can work on a problem at the same time, and how to decompose the whole process into independent processes.
- Paradigm: Brute-force; Divide and conquer; Dynamic programming; Search; Randomized; Reduction. Then we need to check the termination, correctness and completeness of the algorithm.
- Validation: To validate the software if it shows reasonable computing time and good solution.
- Best-case complexity: This is the complexity of solving the problem for the best input of size n.
- Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.
- Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.
Solution and decision
Once the model has been created and a solution has been found, it is important to analyze it to validate the model. The latter was only a schematic representation of the problem, it may not be suitable for the intended purpose. One solution highlights the validity of decision choices and model choices. Only the decision-maker / sponsor can validate the approach taken.
The diagram (in french) of the decision support process is as follows:
Decision support requires a great capacity for abstraction, a good knowledge of algorithmic and graph theory, as well as problems of computational completeness.