# Introduction to optimization

Any industrial problem consists, under certain conditions, in maximizing a profit or minimizing the expenses. In this context, profit and expenditure do not always refer to a monetary variable, it can also be translated to time, distance or others.

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?

Constructing and solving an industrial problem requires rigor, flexibility of mind and a precise modeling approach.

## Optimization and decision making

A problem D is a decision if the answer is binary: Yes or No. We denote Yes (D) the set of instances that are answered Yes.

Consider the following decision problem: is a weighted G graph, is there a tree covering? Yes(D)={connected acyclic subgraph of G}. The problem: existence of a spanning tree of weight ≤ k is also a problem of decision. The optimization problem is to find the value k so that it is minimal.

To better understand both notions, let’s take an example: You want to take a tour of Europe, visiting a number of cities in a period of 6 months. In addition, you want to stay a certain time in each place to visit the tourist areas and admire the landscape.

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 modeling involves a search of minimum or maximum, it is an optimization. The decision support problems contain all three points:

• The type of decision: what we want to do (here we seek an optimization)
• The possible decisions: what we can do (the definition domain)
• The selection criterion: how we choose (the modeling of the problem).

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.

## 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:

## Aside

Decision support requires a great capacity for abstraction, a good knowledge of algorithmic and graph theory, as well as problems of computational completeness.