Question about AddCumulative in CP-SAT

[谭惟予]

Sorry to bother, but I do have a question when I built an Interval model with Global Cumulative to resolve a Bin Packing problem. Here is my idea and example code.

from ortools.sat.python import cp_model

binCapacity = [10,20,30,40,50]

taskDemand = [10,10,10,10,10,10,10,10,10,10]

numBins = len(binCapacity)
numTasks = len(taskDemand)

taskToBin = [int] * numTasks
taskToBinEnd = [int] * numTasks
taskIntervals = [int] * numTasks

model = cp_model.CpModel()

for i in range(numTasks):
    taskToBin[i] = model.NewIntVar(0, numBins - 1, "taskToBin")
    taskToBinEnd[i] = model.NewIntVar(1, numBins, "taskToBinEnd")
    taskIntervals[i] = model.NewIntervalVar(taskToBin[i], 1, taskToBinEnd[i], "taskIntervals")

for j in range(numBins):
    model.AddCumulative(taskIntervals, taskDemand, binCapacity[j])

# Solve model.
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.Solve(model)

for i in range(numTasks):
    print(solver.Value(taskToBin[i]))

The example code above should run successfully  as expected because we can simply get many solutions, such as [1,2,3,4,0] (number of tasks in each bin), [0,2,2,2,4] and so on. However, it failed and indicated "Infeasible".

So I want to know whether it is my misunderstanding about AddCumulative() or Intervals and lead to this fault? Thanks a lot for answers and discussions. 

[Frederic Didier]

Your first cumulative (j == 0) asks for all of your 10 tasks to fit in the time interval [0, numBins] with a max capacity of 10. This is infeasible since you can never schedule two tasks at the same time with this constraint.

To model what you want, you might use ONE cumulative constraint with a variable capacity for each time step. This can be achieved by using a max capacity and fixed intervals to reduce it when you need. 

But this is quite convoluted and probably not efficient at all, you better just use Boolean variables for simple bin packing models.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1d4aacbd-1a87-4ce2-bdbc-6923e69fb88cn%40googlegroups.com.

[Mizux Seiha]

Did you take a look at: 
https://github.com/google/or-tools/blob/stable/ortools/sat/samples/binpacking_problem_sat.py ?

[Weiyu Tan]

Thank you very much for your suggestion!

It's my misunderstanding of Cumulative. 

Actually my real question has a huge scale for Bins and Tasks, so I want to use Cumulative model instead of traditional Binpack model, which requires double FOR circle. 

The modified demo code is shown below, it seems worked. Does this meet your suggestion?

from ortools.sat.python import cp_model

binCapacity = [100,100,100,100,100]
binUsed = [90,80,70,60,50]     #binRest = [10,20,30,40,50]

taskDemand = [10,10,10,10,10,10,10,10,10,10]

numBins = len(binCapacity)
numTasks = len(taskDemand)

taskToBin = [int] * numTasks
taskToBinEnd = [int] * numTasks

taskInterval = [int] * numTasks

binInterval = [int] * numNodes
Intervals = []

model = cp_model.CpModel()

for i in range(numTasks):

    taskToBin[i] = model.NewIntVar(0, numNodes - 1, "taskToBin")
    taskToBinEnd[i] = model.NewIntVar(1, numNodes, "taskToBinEnd")
    taskInterval[i] = model.NewIntervalVar(taskToBin[i], 1, taskToBinEnd[i], "taskIntervals")
    Intervals.append(taskInterval[i])

for j in range(numBins):
    binInterval[j] = model.NewIntervalVar(taskToBin[j], 1, taskToBinEnd[j], "nodeIntervals")
    Intervals.append(binInterval[j])

model.AddCumulative(Intervals, taskDemand + binUsed, 100)

# Solve model.
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.Solve(model)

for i in range(numTasks):
    print(solver.Value(taskToBin[i]))

Thanks again.