Google OR-Tools: Solving an objective function containing max function of multiple variables

Question

I'm aiming to optimize an objective function that includes a max function of multiple variables. Is this possible with OR-Tools given it seems to only have linear solvers and the max function is nonlinear? I've seen from this and this that it's possible to linearize constraints or objective functions, but only in the case of two variables.

# Build data model
data = {}
data['constraint_coeffs'] = [
    [1 for x in range(10)],
]
data['bounds'] = [100]
data['max_power'] = 500
data['demand_coeffs'] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
data['energy_coeffs'] = [1, 1, 1, 1, 2, 2, 2, 6, 6, 6]
data['num_vars'] = 10
data['num_constraints'] = len(data['constraint_coeffs'])

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

# Set variables
x = {}
for j in range(data['num_vars']):
    x[j] = solver.NumVar(0, solver.infinity(), 'x[%i]' % j)

# Set energy constraint
for i in range(data['num_constraints']):
    constraint_expr = [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
    solver.Add(sum(constraint_expr) == data['bounds'][i])

# Set max power constraints
for j in range(data['num_vars']):
    solver.Add(x[j] <= data['max_power'])

Here's where the problem occurs:

obj_expr = [data['energy_coeffs'][j] * x[j] / 60 for j in range(data['num_vars']) + max(data['demand_coeffs'][j] * x[j] for j in range(data['num_vars']))]
solver.Minimize(solver.Sum(obj_expr))

status = solver.Solve()

And here's the error message:

ValueError                    Traceback (most recent call last)
<ipython-input-10-03aba3620a74> in <module>
----> 1 obj_expr = [data['energy_coeffs'][j] * x[j] / 60 for j in range(data['num_vars']) + max(data['demand_coeffs'][j] * x[j] for j in range(data['num_vars']))]

~/anaconda3/envs/.../lib/python3.7/site-packages/ortools/linear_solver/linear_solver_natural_api.py in __gt__(self, arg)
    152   def __gt__(self, arg):
    153     raise ValueError(
--> 154         'Operators "<" and ">" not supported with the linear solver')
    155 
    156   def __ne__(self, arg):

ValueError: Operators "<" and ">" not supported with the linear solver

Answer 1

Yes, this is possible in any solver. If you want to minimize the maximum of a set of values, you can simply introduce a new dummy variable and constrain it to be greater than each of the values in the set and then use that dummy variable in your objective. So in pseudocode:

Let:
c[i] = some indexed set of coefficients
x[i] = some indexed variable

Desire:
minimax (c[i]*x[i])

Introduce:
my_max = real valued variable, non-indexed

Make constraint
for i in I:
  my_max >= c[i]*x[i]

Then you can use my_max (or whatever you call it) in your objective (minimization) function instead of the max()