2
$\begingroup$

I am using python for CP solving. I would like to know if there is constraint that does the opposite of no_overlap. This will be like overlap(interval, arr, n)

interval - single interval variable

arr - array of interval variables

n - positive integer less than length of arr

this will mean that atleast n interval variables from arr overlap in the interval of interval

This is for a situation in job scheduling when a job is not possible to be scheduled on a machine because there are already n higher priority jobs.

$\endgroup$

1 Answer 1

4
$\begingroup$

You can use overlap_length

docplex.cp.modeler.overlap_length(interval, interval2, absentValue=None)

    Returns the length of the overlap of two interval variables.

and count true constraints

from docplex.mp.model import Model

# Data

Buses=[
    (40,500),
    (30,400),
    (35,450),
    (20,300)
    ]

nbKids=300

# Indexes

busSize=0;
busCost=1;

for b in Buses:
    print("buses with ",b[busSize]," seats cost ",b[busCost])

print()    

mdl = Model(name='buses')

#decision variables
mdl.nbBus=mdl.integer_var_dict(Buses,name="nbBus")

# Constraint
mdl.add_constraint(mdl.sum(mdl.nbBus[b]*b[busSize] for b in Buses) >= nbKids, 'kids')

# Objective
mdl.minimize(sum(mdl.nbBus[b]*b[busCost] for b in Buses))

mdl.solve()

# Display solution
for b in Buses:
    print(mdl.nbBus[b].solution_value," buses with ",b[busSize]," seats");

#Add a constraint
# Number of sizes where we have 1 or 2 buses should be at least 3

mdl.add(mdl.sum(mdl.logical_and(1<=mdl.nbBus[b],mdl.nbBus[b]<=2) for b in Buses) >=3)

mdl.solve()

print()
print("Number of sizes where we have 1 or 2 buses should be at least 3")
print()

# Display solution
for b in Buses:
    print(mdl.nbBus[b].solution_value," buses with ",b[busSize]," seats");

in OPL I would write

using CP;

int N=4;
int n=2;
dvar interval itvs;
dvar interval arr[1..N];

subject to
{
  (sum(i in 1..N) (1<=overlapLength(itvs,arr[i])))>=n;
}

and the same can be done with all APIs

$\endgroup$
3
  • $\begingroup$ The overlap constraint only overlaps 2 interval variables at a time. However I want that atleast n intervals overlap with it for its entire duration. NOTE here that the overlapping task can end in the interval of the first variable and new task can start. However all such interval variables would be in the input array. I am trying to model it using the idea in the second part. $\endgroup$ Mar 21, 2022 at 16:17
  • $\begingroup$ That is why you need count true constraints to check how many overlap $\endgroup$ Mar 21, 2022 at 16:19
  • $\begingroup$ But this is difficult with interval variables and not as staright forward. $\endgroup$ Mar 21, 2022 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.