2
$\begingroup$

I am a user of Google OR Tools, which can interface with many LP & MIP solvers, plus it's own SAT based constraint programming solver.

My question, in the context of OR-Tools, is: how should I best handle optimization problems where there are multiple objectives? For example if I want to minimize distance traveled in a warehouse while also minimizing proximity of workers.

$\endgroup$

2 Answers 2

3
$\begingroup$

I would say that you first of all need to figure out what you mean by an optimal solution to a multi objective optimisation problem. Are you searching for all Pareto optimal solutions (a set of solutions), just one (more or less arbitrary) Pareto optimal solution, a lexicographic optimal solution, a max-ordering solution, or something else?

When you have decided on your notation of optimality, you should find a method that uses your single objective SAT solver to find a solution meeting your criteria.

One popular approach is to simply weigh each of your $p$ objective functions, $f_i$, using positive weights, $w_i>0$ and then solve the single objective optimisation problem: \begin{equation} \min_{x\in {X}} \sum_{i=1}^p w_if_i(x) \end{equation} where $X$ is your set of feasible solutions. This approach will guarantee a Pareto optimal solution, but it can be quite difficult to predict which values of the weights will lead to solutions of your liking. This require some experimentation.

If you are after a lexigraphically optimal solution, the approach described by @A.Omidi in the code sample is the way to go:

  1. Optimise the most important objective $f_1(x)$ and find an optimal solution with value $f_1^*$.
  2. Add a constraint to your model: $f_1(x)=f_1^*$
  3. Change the objective from $f_1(x)$ to $f_2(x)$ and optimize.
  4. Continue this approach until you have no more objetive functions, or the feasible set is a singleton.

This last approach requires a strict ordering of your objectives from most important to least important. This will give you more control over what solution you end up with, but you also restrict the search for interesting solutions quite considerably. The resulting solution is also guaranteed to be Pareto optimal.

$\endgroup$
1
  • $\begingroup$ Weighting various objectives into a single objective is probably the best approach for me. My objective function is essentially "1/ minimize travel distance of forklifts while 2/ maximizing distance between forklifts" where obj 1 is twice as important as obj 2. Because I can't minimize and maximize the function simultaneously, I might be able to scale obj 1 by -1 where the maximization of this obj is the minimization of its dual. $\endgroup$
    – jbuddy_13
    Dec 1, 2022 at 17:01
3
$\begingroup$

Please be aware that, Simplex is an algorithm to solve Linear programming and Not a method to solve MOO. In the context of linear or mixed-integer linear programming, there are some ways to do what you want. For example, the weighted sum method, goal programming, and $\epsilon$-constraint have frequently been used in literature and industries. For more details about MMO using google or-tools sat solver, the following example and link would be helpful.

from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()
x = model.NewIntVar(0, 10, "x")
y = model.NewIntVar(0, 10, "y")

# Maximize x
model.Maximize(x)
solver.Solve(model)
print("x", solver.Value(x))
print("y", solver.Value(y))
print()

# Hint (speed up solving)
model.AddHint(x, solver.Value(x))
model.AddHint(y, solver.Value(y))

# Maximize y (and constraint prev objective)
model.Add(x == round(solver.ObjectiveValue()))  # use <= or >= if not optimal
model.Maximize(y)
solver.Solve(model)

print("x", solver.Value(x))
print("y", solver.Value(y))
$\endgroup$
4
  • 1
    $\begingroup$ There are simplex algorithms for multi objective linear programming. Se for instance chapter 6 of Ehrgott's "Multicriteria optimization", 2nd edition $\endgroup$
    – Sune
    Nov 30, 2022 at 13:09
  • $\begingroup$ Thanks, @Sune. I think the questioner is looking for a way to solve MOO by or-tools sat solver than wants to solve it in an algorithmic manner. I will check your mentioned reference and update the answer. $\endgroup$
    – A.Omidi
    Nov 30, 2022 at 13:41
  • $\begingroup$ Thanks, this is insightful! What about combining objectives? In the context of your example above, would model.Maximize(x+y) be an appropriate alternative? $\endgroup$
    – jbuddy_13
    Nov 30, 2022 at 15:54
  • $\begingroup$ @jbuddy_13, your welcome. Actually, I am not a or-tools sat user, but As far as I know, in the MOO it can be possible to combine any linear objective functions. For example, in the weighted sum. By the way, it would be worth trying that. $\endgroup$
    – A.Omidi
    Nov 30, 2022 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.