Multiple objective functions with binary variables Google OR-tools

Question

I have a set of U users and a set of S servers. I want to maximize the number of users allocated to a server while minimizing the number of servers used (this means that I have two objective functions).

Each user has some requirements w and each server has a total capacity of C.

The solver variables are the following:

# x[i,j] = True if user u[j] is allocated to server s[i]
# x[i,j] = False otherwise

# y[i] = True if server s[i] is used to serve users
# y[i] = False otherwise

As mentioned before, I want to maximize x[i,j] while minimizing y[i]

The constraints are the following:

• Capacity constraint: Since each server i has a certain capacity, the allocation of j users must not exceed that capacity
• Proximity constraint: Only users located within the range of the server can be allocated to it. A user can be located in the overlapping range of multiple servers
• Constraint family: Ensures every user is allocated to at most one server.

Using this library

from ortools.sat.python import cp_model

So far I've done:

• Create the solver variables (they are boolean)
• Create the constraints
• Maximize the x[i,j] variable
• Obtain the objective function

For instance, if I have 10 users and 4 servers all the 10 users are allocated among the 4 servers

What I need but haven't been able to accomplish:

• Maximize the x[i,j] variable AND Minimize the y[i] variable

For the same 10 users and the same 4 servers above, all the 10 users can be allocated among just 2 servers and not 4

I have tried the solution given in this post but it is not working since I got that the problem does not have an optimal solution

Answer 1

there are usually 2 approaches:

• weighted sum: a * obj1 + b * obj2
• lexicographic: optimize obj1, get optimal value, change objective to obj2, add constraint obj1 <= best_obj1_value (optional + slack). Then reoptimize. Bonus point when reusing the optimal solution with obj1 as a hint for the second solve.