Simplex method for multiple objectives

Question

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.

Answer 1

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.

Answer 2

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

• Multi-objective optimization with CP-Sat