Decision making

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 by 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 with the steam 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.

Constructing an optimization problem

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.

Modeling a problem

The four steps in modeling an industrial problem are:

  • What are the data of the problem? to collect the problem data, to understand the problem;
  • How to model the problem? the three points of the decision support
    • What decisions should be made? to select/place objects, to define an order or quantity, to choose an event, to perform a particular operation;
    • What are the constraints of the problem? to respect abilities or precedence constraints;
    • What is the objective? to maximize profit, to minimize costs or quantity;
  • What is the complexity of this problem? polynomial, Np, Np-hard;
  • How to solve the problem ? to design algorithms (exact vs. approximate) giving feasible / optimal solutions, to develop alternative or hybrid methods

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).

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.