Linked Questions

Popular Questions

How to minimize the standard deviation in Or Tools?

Asked by At

I have a list of air routes with their length in minutes and the passenger demand. I want to arrange them in 168h circuits where the standard deviation of a circuit is as low as possible.

I found this resembles the multiple knapsacks problem and so that's my basis. I've got the 168h circuits but the demand is randomly assigned because of the current objective (maximize total demand within a circuit).

As advised in or-tools - Compute the stdev from a SumArray() I'm actually trying to minimize the sum of abs(val - average).

This is what I came up with but I realized that I'm minimizing the sum of abs(val - average of ALL routes). How do I compute the average demand in a circuit and add it to the formula ? It's also become painfully slow with this change, which I'm not sure why.

solver = pywraplp.Solver.CreateSolver('SCIP')
if solver is None:
    print('SCIP solver unavailable.')

# Variables.
# x[i, b] = 1 if item i is packed in bin b.
x = {}
for i in data['all_items']:
    for b in data['all_bins']:
        x[i, b] = solver.BoolVar(f'x_{i}_{b}')

# Constraints.
# Each item is assigned to at most one bin.
for i in data['all_items']:
    solver.Add(sum(x[i, b] for b in data['all_bins']) <= 1)

# The amount packed in each bin has to match it's capacity.
for b in data['all_bins']:
    solver.Add(
        sum(x[i, b] * data['weights'][i]
            for i in data['all_items']) == data['bin_capacities'][b])

# Objective.
# Maximize total value of packed items.
objective = solver.Objective()
for i in data['all_items']:
    for b in data['all_bins']:
        objective.SetCoefficient(x[i, b], abs(data['values'][i] - round(np.mean(data['values']), 0)))

objective.SetMinimization()
status = solver.Solve()

Thank you

Related Questions