search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
10.97k stars 2.1k forks source link

routing.solver().Cumulative() not working for IntervalVars #1937

Closed Stepka closed 3 years ago

Stepka commented 4 years ago

I made a little test for 6 interval vars using cp_model. And it work as I great!

But the same test, but for routing solver does not work! Can it be a bug or I missed something?

Below tests for both solvers:

from __future__ import print_function

from ortools.sat.python import cp_model
from datetime import datetime, timedelta

def get_time_string(x):
    if x > pow(2, 32) or x < -pow(2, 32):
        return "-1:-1"
    x = int(x)
    if x < 0:
        return datetime(1900, 1, 1, 0, 0).strftime("%H:%M")
    elif x / 60 < 24:
        return datetime(1900, 1, 1, int(x / 60), x % 60).strftime("%H:%M")
    else:
        return str(timedelta(minutes=x))[:-3]

def create_data_model():
    """Stores the data for the problem."""
    data = {}

    data['starts'] = [
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
    ]

    data['ends'] = [
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
    ]

    data['durations'] = [
        (0, 215),
        (0, 20),
        (0, 215),
        (0, 20),
        (0, 215),
        (0, 20),
    ]
    return data

def main():
    """Solve the VRP with time windows."""
    data = create_data_model()

    model = cp_model.CpModel()

    # 1 CREATE INTERVALS
    intervals = []
    starts = []
    ends = []
    durations = []
    for i in range(len(data['starts'])):
        start_interval = model.NewIntVar(data['starts'][i][0], data['starts'][i][1], 'start_%i' % i)
        end_interval = model.NewIntVar(data['ends'][i][0], data['ends'][i][1], 'end_%i' % i)
        duration_interval = model.NewIntVar(data['durations'][i][0], data['durations'][i][1], 'duration_%i' % i)
        interval = model.NewIntervalVar(start_interval, duration_interval, end_interval, 'interval_%i' % i)
        intervals.append(interval)
        starts.append(start_interval)
        ends.append(end_interval)
        durations.append(duration_interval)

    # 2 ADD SHARED RESOURCE CONSTRAINT
    model.AddCumulative(intervals, [1 for _ in intervals], 2)

    # 3 MAXIMIZE DURATIONS
    model.Maximize(sum(durations))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30.0
    solver.parameters.log_search_progress = True

    status = solver.Solve(model)

    if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
        plan_output = ""
        for i in range(len(intervals)):
            plan_output += 'Wait ({} - {}; duration: {}), \n'.format(
                get_time_string(solver.Value(starts[i])),
                get_time_string(solver.Value(ends[i])),
                get_time_string(solver.Value(durations[i])),
            )
        print(plan_output)
    else:
        print('The problem does not have an optimal solution.')

if __name__ == '__main__':
    main()

and 

from __future__ import print_function
from __future__ import absolute_import
from __future__ import division
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from datetime import datetime, timedelta

def get_time_string(x):
    if x > pow(2, 32) or x < -pow(2, 32):
        return "-1:-1"
    x = int(x)
    if x < 0:
        return datetime(1900, 1, 1, 0, 0).strftime("%H:%M")
    elif x / 60 < 24:
        return datetime(1900, 1, 1, int(x / 60), x % 60).strftime("%H:%M")
    else:
        return str(timedelta(minutes=x))[:-3]

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = [
        [ 0, 10, 15],
        [10,  0, 30],
        [15, 30,  0],
    ]
    data['num_vehicles'] = 4
    data['depot'] = 0

    data['starts'] = [
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
    ]
    data['ends'] = [
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
        (455, 670),
        (650, 670),
    ]
    data['durations'] = [
        (0, 215),
        (0, 20),
        (0, 215),
        (0, 20),
        (0, 215),
        (0, 20),
    ]
    return data

def print_solution(solution, intervals, durations):
    """Prints solution on console."""
    plan_output = ""
    for wait_interval in intervals:
        plan_output += 'Wait ({0}..{1} - {2}..{3}; duration: {4}..{5}), \n'.format(
            get_time_string(solution.StartMin(wait_interval)),
            get_time_string(solution.StartMax(wait_interval)),
            get_time_string(solution.EndMin(wait_interval)),
            get_time_string(solution.EndMax(wait_interval)),
            get_time_string(solution.DurationMin(wait_interval)),
            get_time_string(solution.DurationMax(wait_interval)),
        )
    for duration in durations:
        plan_output += 'Duration ({}: {} - {}), \n'.format(
            get_time_string(solution.Value(duration)),
            get_time_string(solution.Min(duration)),
            get_time_string(solution.Max(duration)),
        )
    print(plan_output)

def main():
    """Solve the VRP with time windows."""
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['time_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        1200,  # allow waiting time
        1200,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)

    cumul_vars = []
    # TODO: I found that NextVar()>max() == 160. Why?
    for node in range(0, 160):
        if node < len(data['time_matrix']):
            index = manager.NodeToIndex(node)
            cumul_vars.append(time_dimension.CumulVar(index))
            routing.AddToAssignment(time_dimension.SlackVar(index))
            routing.AddToAssignment(time_dimension.TransitVar(index))
        else:
            cumul_vars.append(routing.solver().IntVar(0, 1200, "cumul%i" % node))

    intervals = []
    durations = []
    # 1 CREATE INTERVALS
    for i in range(len(data['starts'])):

            wait_interval = routing.solver().IntervalVar(
                0,               # start min
                1200,            # start max
                0,               # min duration
                1200,            # max duration
                0,               # end min
                1200,            # end max
                True, "wait_on_%i" % i)
            intervals.append(wait_interval)

            start_interval = routing.solver().IntVar(data['starts'][i][0], data['starts'][i][1], 'start_%i' % i)
            end_interval = routing.solver().IntVar(data['ends'][i][0], data['ends'][i][1], 'end_%i' % i)
            duration_interval = routing.solver().IntVar(data['durations'][i][0], data['durations'][i][1], 'duration_%i' % i)

            routing.solver().Add(wait_interval.StartExpr() >= start_interval)
            routing.solver().Add(wait_interval.DurationExpr() <= duration_interval)
            routing.solver().Add(wait_interval.EndExpr() <= end_interval)

            #

            wait_duration = routing.solver().IntVar(
                0,
                1200,
                "wait_duration_%i" % i
            )
            routing.solver().Add(wait_interval.DurationExpr() == wait_duration)

            durations.append(wait_duration)

            #

            routing.AddIntervalToAssignment(wait_interval)
            routing.AddToAssignment(wait_duration)

    # 2 ADD SHARED RESOURCE CONSTRAINT
    routing.solver().Add(routing.solver().Cumulative(intervals, [1 for _ in intervals], 2, 'waits'))

    # 3 MAXIMIZE DURATIONS
    slack_durations_sum = routing.solver().IntVar(
        0,
        1200,
        "wait_duration_sun"
    )
    routing.solver().Add(slack_durations_sum == routing.solver().Sum(durations))
    routing.AddVariableMaximizedByFinalizer(slack_durations_sum)

    # Add penalties for use a vehicle to minimize number of used vehicles
    routing.SetFixedCostOfAllVehicles(10000)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(solution, intervals, durations)
    else:
        print("no solution")

if __name__ == '__main__':
    main()

And here is outputs:

cp_model solver output (not more than 2 intervals simultaneously, as I expected):

Wait (07:35 - 07:35; duration: 00:00), 
Wait (10:50 - 10:50; duration: 00:00), 
Wait (07:35 - 11:10; duration: 03:35), 
Wait (10:50 - 11:10; duration: 00:20), 
Wait (07:35 - 10:50; duration: 03:15), 
Wait (10:50 - 10:50; duration: 00:00),

routing solver output (all intervals simultaneously, but I expect not more than 2):

Wait (07:35..07:35 - 11:10..11:10; duration: 03:35..03:35), 
Wait (10:50..10:50 - 11:10..11:10; duration: 00:20..00:20), 
Wait (07:35..07:35 - 11:10..11:10; duration: 03:35..03:35), 
Wait (10:50..10:50 - 11:10..11:10; duration: 00:20..00:20), 
Wait (07:35..07:35 - 11:10..11:10; duration: 03:35..03:35), 
Wait (10:50..10:50 - 11:10..11:10; duration: 00:20..00:20),

So, please help. Am I missed something or it is a bug of the OR Tools?

I use:

Mizux commented 4 years ago

Don't get it, Using CP-SAT solver (in sat directory) you try to solve a scheduling probleme...

Actually, in constraint_solver you have two "stages" the first one which is the CP solver and on top of it you have the VRP Solver (using the CP solver internally). In you second example you try to solve it using the VRP/TSP Solver which is not really intended for this. Also you set the number of vehicle to 4 so you can do 4 "tasks" (i.e. visiting locations) in parallel...

Stepka commented 4 years ago

It is just simplified test. In real task I have more complex vrptw problem with scheduling. In my case I need to constraint SlackVars on a group of the nodes with routing.solver().Cumulative().

If you want more details:

And both tests shows how I think I can add constraits for SlackVars(). I just make IntrevalVars that shouls match with SlackVars and constrain them using Cumulative() function.

But when I use CP-SAT solver all is work perfectly. But when I try to do same things using Routing solver - it is does not work.

P.S. incrementing num of vehicles to 6 has no effect too.

lperron commented 4 years ago

This code works fine on the CP solver

def main(): """Solve the VRP with time windows.""" data = create_data_model()

solver = pywrapcp.Solver('')

# 1 CREATE INTERVALS
intervals = []
starts = []
durations = []
for i in range(len(data['starts'])):
    interval = solver.IntervalVar(
        data['starts'][i][0], data['starts'][i][1],
        data['durations'][i][0], data['durations'][i][1],
        data['ends'][i][0], data['ends'][i][1], False, 'interval_%i' %

i) starts.append(interval.StartExpr().Var()) durations.append(interval.DurationExpr().Var())

    intervals.append(interval)

# 2 ADD SHARED RESOURCE CONSTRAINT
solver.Add(solver.Cumulative(intervals, [1 for _ in intervals], 2,

'cumul'))

# 3 MAXIMIZE DURATIONS
obj_var = sum(interval.DurationExpr().Var() for interval in

intervals).Var() obj = solver.Maximize(obj_var, 1)

db1 = solver.Phase(starts, solver.CHOOSE_FIRST_UNBOUND,
                   solver.ASSIGN_MIN_VALUE)
db2 = solver.Phase(durations, solver.CHOOSE_FIRST_UNBOUND,
                   solver.ASSIGN_MAX_VALUE)
db3 = solver.Phase([obj_var], solver.CHOOSE_FIRST_UNBOUND,
                   solver.ASSIGN_MIN_VALUE)
db = solver.Compose([db1, db2, db3])

log = solver.SearchLog(1000000, obj)

count = 0
solver.NewSearch(db, [obj, log])
while solver.NextSolution():
    count += 1
    print('Solution', count)
    for interval in intervals:
        print('Wait ([{}..{}] - [{}..{}]; duration: {}), \n'.format(
            interval.StartMin(),
            interval.StartMax(),
            interval.EndMin(),
            interval.EndMin(),
            interval.DurationExpr().Var().Value()))
solver.EndSearch()

Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le jeu. 26 mars 2020 à 13:51, Stepka notifications@github.com a écrit :

It is just simplified test. In real task I have more complex vrptw problem with scheduling. In my case I need to constraint SlackVars on a group of the nodes with routing.solver().Cumulative().

And both tests shows how I think I can add constraits for SlackVars(). I just make IntrevalVars that shouls match with SlackVars and constrain them using Cumulative() function.

But when I use CP-SAT solver all is work perfectly. But when I try to do same things using Routing solver - it is does not work.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1937#issuecomment-604413121, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3NC7BNGR3DJGKOJAMTRJNFWNANCNFSM4LTW4F2Q .

Stepka commented 4 years ago

Yes it works for routing model with this:

    routing.solver().NewSearch(db, [time_limit, obj, log])
    while routing.solver().NextSolution():
        ...
    routing.solver().EndSearch()

but I still need solution for vrptw.

How can I merge your code with this:

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(solution, intervals, durations)

?

duca755 commented 4 years ago

Hello!

Do you have any follow up on the latest response from Stepka to your post?

Would appreciate it!

Thanks!

This code works fine on the CP solver def main(): """Solve the VRP with time windows.""" data = create_datamodel() solver = pywrapcp.Solver('') # 1 CREATE INTERVALS intervals = [] starts = [] durations = [] for i in range(len(data['starts'])): interval = solver.IntervalVar( data['starts'][i][0], data['starts'][i][1], data['durations'][i][0], data['durations'][i][1], data['ends'][i][0], data['ends'][i][1], False, 'interval%i' % i) starts.append(interval.StartExpr().Var()) durations.append(interval.DurationExpr().Var()) intervals.append(interval) # 2 ADD SHARED RESOURCE CONSTRAINT solver.Add(solver.Cumulative(intervals, [1 for _ in intervals], 2, 'cumul')) # 3 MAXIMIZE DURATIONS obj_var = sum(interval.DurationExpr().Var() for interval in intervals).Var() obj = solver.Maximize(obj_var, 1) db1 = solver.Phase(starts, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db2 = solver.Phase(durations, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MAX_VALUE) db3 = solver.Phase([obj_var], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db = solver.Compose([db1, db2, db3]) log = solver.SearchLog(1000000, obj) count = 0 solver.NewSearch(db, [obj, log]) while solver.NextSolution(): count += 1 print('Solution', count) for interval in intervals: print('Wait ([{}..{}] - [{}..{}]; duration: {}), \n'.format( interval.StartMin(), interval.StartMax(), interval.EndMin(), interval.EndMin(), interval.DurationExpr().Var().Value())) solver.EndSearch() Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le jeu. 26 mars 2020 à 13:51, Stepka notifications@github.com a écrit : … It is just simplified test. In real task I have more complex vrptw problem with scheduling. In my case I need to constraint SlackVars on a group of the nodes with routing.solver().Cumulative(). And both tests shows how I think I can add constraits for SlackVars(). I just make IntrevalVars that shouls match with SlackVars and constrain them using Cumulative() function. But when I use CP-SAT solver all is work perfectly. But when I try to do same things using Routing solver - it is does not work. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1937 (comment)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3NC7BNGR3DJGKOJAMTRJNFWNANCNFSM4LTW4F2Q .

This code works fine on the CP solver def main(): """Solve the VRP with time windows.""" data = create_datamodel() solver = pywrapcp.Solver('') # 1 CREATE INTERVALS intervals = [] starts = [] durations = [] for i in range(len(data['starts'])): interval = solver.IntervalVar( data['starts'][i][0], data['starts'][i][1], data['durations'][i][0], data['durations'][i][1], data['ends'][i][0], data['ends'][i][1], False, 'interval%i' % i) starts.append(interval.StartExpr().Var()) durations.append(interval.DurationExpr().Var()) intervals.append(interval) # 2 ADD SHARED RESOURCE CONSTRAINT solver.Add(solver.Cumulative(intervals, [1 for _ in intervals], 2, 'cumul')) # 3 MAXIMIZE DURATIONS obj_var = sum(interval.DurationExpr().Var() for interval in intervals).Var() obj = solver.Maximize(obj_var, 1) db1 = solver.Phase(starts, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db2 = solver.Phase(durations, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MAX_VALUE) db3 = solver.Phase([obj_var], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db = solver.Compose([db1, db2, db3]) log = solver.SearchLog(1000000, obj) count = 0 solver.NewSearch(db, [obj, log]) while solver.NextSolution(): count += 1 print('Solution', count) for interval in intervals: print('Wait ([{}..{}] - [{}..{}]; duration: {}), \n'.format( interval.StartMin(), interval.StartMax(), interval.EndMin(), interval.EndMin(), interval.DurationExpr().Var().Value())) solver.EndSearch() Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le jeu. 26 mars 2020 à 13:51, Stepka notifications@github.com a écrit :

… It is just simplified test. In real task I have more complex vrptw problem with scheduling. In my case I need to constraint SlackVars on a group of the nodes with routing.solver().Cumulative(). And both tests shows how I think I can add constraits for SlackVars(). I just make IntrevalVars that shouls match with SlackVars and constrain them using Cumulative() function. But when I use CP-SAT solver all is work perfectly. But when I try to do same things using Routing solver - it is does not work. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1937 (comment)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3NC7BNGR3DJGKOJAMTRJNFWNANCNFSM4LTW4F2Q .

lperron commented 4 years ago

My code shows the constraint works. The tricky part to make it work was the search part. Can you try adapting it to your example ? Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le mar. 31 mars 2020 à 22:44, duca755 notifications@github.com a écrit :

Hello!

Do you have any follow up on the latest response from Stepka to your post?

Would appreciate it!

Thanks!

This code works fine on the CP solver def main(): """Solve the VRP with time windows.""" data = create_datamodel() solver = pywrapcp.Solver('') # 1 CREATE INTERVALS intervals = [] starts = [] durations = [] for i in range(len(data['starts'])): interval = solver.IntervalVar( data['starts'][i][0], data['starts'][i][1], data['durations'][i][0], data['durations'][i][1], data['ends'][i][0], data['ends'][i][1], False, 'interval%i' % i) starts.append(interval.StartExpr().Var()) durations.append(interval.DurationExpr().Var()) intervals.append(interval)

2 ADD SHARED RESOURCE CONSTRAINT solver.Add(solver.Cumulative(intervals,

[1 for _ in intervals], 2, 'cumul')) # 3 MAXIMIZE DURATIONS obj_var = sum(interval.DurationExpr().Var() for interval in intervals).Var() obj = solver.Maximize(obj_var, 1) db1 = solver.Phase(starts, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db2 = solver.Phase(durations, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MAX_VALUE) db3 = solver.Phase([obj_var], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db = solver.Compose([db1, db2, db3]) log = solver.SearchLog(1000000, obj) count = 0 solver.NewSearch(db, [obj, log]) while solver.NextSolution(): count += 1 print('Solution', count) for interval in intervals: print('Wait ([{}..{}]

  • [{}..{}]; duration: {}), \n'.format( interval.StartMin(), interval.StartMax(), interval.EndMin(), interval.EndMin(), interval.DurationExpr().Var().Value())) solver.EndSearch() Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le jeu. 26 mars 2020 à 13:51, Stepka notifications@github.com a écrit : … <#m-5810027570700119166> It is just simplified test. In real task I have more complex vrptw problem with scheduling. In my case I need to constraint SlackVars on a group of the nodes with routing.solver().Cumulative(). And both tests shows how I think I can add constraits for SlackVars(). I just make IntrevalVars that shouls match with SlackVars and constrain them using Cumulative() function. But when I use CP-SAT solver all is work perfectly. But when I try to do same things using Routing solver - it is does not work. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1937 (comment) https://github.com/google/or-tools/issues/1937#issuecomment-604413121>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3NC7BNGR3DJGKOJAMTRJNFWNANCNFSM4LTW4F2Q .

This code works fine on the CP solver def main(): """Solve the VRP with time windows.""" data = create_datamodel() solver = pywrapcp.Solver('') # 1 CREATE INTERVALS intervals = [] starts = [] durations = [] for i in range(len(data['starts'])): interval = solver.IntervalVar( data['starts'][i][0], data['starts'][i][1], data['durations'][i][0], data['durations'][i][1], data['ends'][i][0], data['ends'][i][1], False, 'interval%i' % i) starts.append(interval.StartExpr().Var()) durations.append(interval.DurationExpr().Var()) intervals.append(interval)

2 ADD SHARED RESOURCE CONSTRAINT solver.Add(solver.Cumulative(intervals,

[1 for _ in intervals], 2, 'cumul')) # 3 MAXIMIZE DURATIONS obj_var = sum(interval.DurationExpr().Var() for interval in intervals).Var() obj = solver.Maximize(obj_var, 1) db1 = solver.Phase(starts, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db2 = solver.Phase(durations, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MAX_VALUE) db3 = solver.Phase([obj_var], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) db = solver.Compose([db1, db2, db3]) log = solver.SearchLog(1000000, obj) count = 0 solver.NewSearch(db, [obj, log]) while solver.NextSolution(): count += 1 print('Solution', count) for interval in intervals: print('Wait ([{}..{}]

  • [{}..{}]; duration: {}), \n'.format( interval.StartMin(), interval.StartMax(), interval.EndMin(), interval.EndMin(), interval.DurationExpr().Var().Value())) solver.EndSearch() Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le jeu. 26 mars 2020 à 13:51, Stepka notifications@github.com a écrit :

… <#m-5810027570700119166> It is just simplified test. In real task I have more complex vrptw problem with scheduling. In my case I need to constraint SlackVars on a group of the nodes with routing.solver().Cumulative(). And both tests shows how I think I can add constraits for SlackVars(). I just make IntrevalVars that shouls match with SlackVars and constrain them using Cumulative() function. But when I use CP-SAT solver all is work perfectly. But when I try to do same things using Routing solver - it is does not work. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1937 (comment) https://github.com/google/or-tools/issues/1937#issuecomment-604413121>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3NC7BNGR3DJGKOJAMTRJNFWNANCNFSM4LTW4F2Q .

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1937#issuecomment-606864784, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3NDPCFWQPZKDVIAXK3RKJI3HANCNFSM4LTW4F2Q .

Stepka commented 4 years ago

I'm trying to adapt your code to my task and faced with print routes problem. This code failed:

    count = 0
    routing.solver().NewSearch(db, [time_limit, obj, log])
    while routing.solver().NextSolution():
        count += 1
        plan_output = 'Solution #{}\n'.format(count)

        for vehicle_id in range(data['num_vehicles']):
            index = routing.Start(vehicle_id)
            plan_output += 'Route for vehicle {}:\n'.format(vehicle_id)
            while not routing.IsEnd(index):
                node_index = manager.IndexToNode(index)

                plan_output += '[ #{} -> \n'.format(
                    node_index
                )

                index = routing.NextVar(index).Value()
        for interval in intervals:
            plan_output += 'Wait ([{}..{}] - [{}..{}]; duration: {}), \n'.format(
                get_time_string(interval.StartMin()),
                get_time_string(interval.StartMax()),
                get_time_string(interval.EndMin()),
                get_time_string(interval.EndMin()),
                get_time_string(interval.DurationExpr().Var().Value()))

        print(plan_output)
    routing.solver().EndSearch()

Code prints: 

WARNING: Logging before InitGoogleLogging() is written to STDERR
I0402 10:55:39.796936 12248 search.cc:253] Start search (memory used = 64.69 MB)
I0402 10:55:39.797935 12248 search.cc:253] Root node processed (time = 0 ms, constraints = 48, memory used = 64.98 MB)
I0402 10:55:39.809952 12248 search.cc:253] Solution #0 (objective value = 40, time = 12 ms, branches = 1262, failures = 627, depth = 635, memory used = 65.29 MB, limit = 0%)
F0402 10:55:39.814927 12248 expressions.cc:1340] Check failed: min_.Value() == max_.Value() (0 vs. 13)  variable Nexts0(0..13) is not bound.
*** Check failure stack trace: ***

This line is wrong:index = routing.NextVar(index).Value() What I doing wrong?

lperron commented 4 years ago

of course, the routing model is only 'solved' if you use the routing.Solve() method. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le jeu. 2 avr. 2020 à 11:01, Stepka notifications@github.com a écrit :

I'm trying to adapt your code to my task and faced with print routes problem. This code failed:

count = 0
routing.solver().NewSearch(db, [time_limit, obj, log])
while routing.solver().NextSolution():
    count += 1
    plan_output = 'Solution #{}\n'.format(count)

    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output += 'Route for vehicle {}:\n'.format(vehicle_id)
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)

            plan_output += '[ #{} -> \n'.format(
                node_index
            )

            index = routing.NextVar(index).Value()
    for interval in intervals:
        plan_output += 'Wait ([{}..{}] - [{}..{}]; duration: {}), \n'.format(
            get_time_string(interval.StartMin()),
            get_time_string(interval.StartMax()),
            get_time_string(interval.EndMin()),
            get_time_string(interval.EndMin()),
            get_time_string(interval.DurationExpr().Var().Value()))

    print(plan_output)
routing.solver().EndSearch()

Code prints:

WARNING: Logging before InitGoogleLogging() is written to STDERR I0402 10:55:39.796936 12248 search.cc:253] Start search (memory used = 64.69 MB) I0402 10:55:39.797935 12248 search.cc:253] Root node processed (time = 0 ms, constraints = 48, memory used = 64.98 MB) I0402 10:55:39.809952 12248 search.cc:253] Solution #0 (objective value = 40, time = 12 ms, branches = 1262, failures = 627, depth = 635, memory used = 65.29 MB, limit = 0%) F0402 10:55:39.814927 12248 expressions.cc:1340] Check failed: min.Value() == max.Value() (0 vs. 13) variable Nexts0(0..13) is not bound. Check failure stack trace:

This line is wrong: index = routing.NextVar(index).Value() What I doing wrong?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1937#issuecomment-607716793, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3OXEE2C7E2Y632VK3DRKRH45ANCNFSM4LTW4F2Q .

Stepka commented 4 years ago

I'm sorry, but I frustrated. Am I right that or-tools now cannot solve routing model and constrain IntervalVars via Cumulative() function in one case? Will it be added in the future?

lperron commented 4 years ago

It can:

https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_resources.py

Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le jeu. 2 avr. 2020 à 11:34, Stepka notifications@github.com a écrit :

I'm sorry, but I frustrated. Am I right that or-tools now cannot solve routing model and constrain IntervalVars via Cumulative() function in one case? Will it be added in the future?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1937#issuecomment-607733632, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3J7EJNZYHCQUDTYMS3RKRL3ZANCNFSM4LTW4F2Q .

Stepka commented 4 years ago

I tryied VRP resources example, updated it with IntervalVar instead FixedDurationIntervalVar. And this code shown the same result as example. So, it can be a signal that problem is not with IntervalVar and Cumulative.

But I found two problems again.

First - from output when I run VRP example with fixed duration vars:

Route for vehicle 0:
0 Time(5,5) -> 8 Time(8,8) -> 14 Time(11,11) -> 16 Time(13,13) -> 0 Time(20,20)
Time of the route: 20min

Route for vehicle 1:
0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20)
Time of the route: 20min

Route for vehicle 2:
0 Time(5,5) -> 7 Time(7,7) -> 1 Time(11,11) -> 4 Time(13,13) -> 3 Time(14,14) -> 0 Time(25,25)
Time of the route: 25min

Route for vehicle 3:
0 Time(0,0) -> 9 Time(2,3) -> 5 Time(4,5) -> 6 Time(6,9) -> 2 Time(10,12) -> 10 Time(14,16) -> 0 Time(25,25)
Time of the route: 25min

As you see each vehicle transit to a first location from depot for a 2..4 time units, but there are not adds load_time (5 time units) in the arrival time. Looks like duration is omitted by solver. It is looks like a bug.

And the second problem, when I try to link my interval var duration to slackvars solver has no affect. Look like it linked with bug above.

Mizux commented 4 years ago

see https://github.com/google/or-tools/issues/1715#issuecomment-574156540

GuyBenhaim commented 4 years ago

Hello, This worked fine for me:
routing.solver().Add(routing.solver().Cumulative(vector< IntervalVar * >, vector< int > &demands, int capacity, string &name). I will try to re-examine, I hope no hidden issues ...