Multiobjective resolution

Lexicographic order

When solving a multiobjective model with LocalSolver, the objectives are treated in a lexicographic order. This means that the objectives are optimized in the order of declaration in the model : if k objectives 0, ..., k-1 are declared, each objective i can be optimized without degrading the values of objectives 0, ..., i-1 previously obtained and ignoring the values of objectives i+1, ..., k-1.

Taking the following example, a solution is improved if revenues are increased, or if revenues were maintained while decreasing the resources, regardless of desiderata value.

maximize revenues;
minimize resources;
maximize desiderata;
model.maximize(revenues)
model.minimize(resources)
model.maximize(desiderata)
model.maximize(revenues);
model.minimize(resources);
model.maximize(desiderata);
model.Maximize(revenues);
model.Minimize(resources);
model.Maximize(desiderata);
model.maximize(revenues);
model.minimize(resources);
model.maximize(desiderata);

This functionality is a powerful tool to tackle potentially violated requirements. The idea is to transform the requirement into a “soft” constraint, by setting it as a primary objective (goal programming). For example, if one wishes to use at most 5 trucks to visit the clients in a routing problem, but is unsure whether it is feasible or not, then the first objective of the problem can be to minimize the number of trucks above 5.

Phases

Since LocalSolver allows lexicographic multiobjective optimization, we allow you to parameterize the time or the number of iterations to spend in optimizing each objective, thanks to the LSPhase. A phase is the resolution step at which an objective i is tackled, while not worsening the previous objectives and ignoring the following ones.

If the optimal value of an objective is found before the end of the corresponding phase, the remaining iterations will be transferred to the next phase.