Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
thomas-bee
@thomas-bee
Please excuse an absolute newbie question. I would like to schedule non-overlapping time intervals (telescope observations). Google's CP SAT solver provides an IntervalVar, consisting of two IntVars from/to and a duration. Would you have any pointer to an example or a hint how to express such intervals in Choco and the fact that they must not overlap?
Charles Prud'homme
@cprudhom
In Choco, we defined Tasks, a tasks is composed of a start, a duration and a end. Then you should have a look at the cumulative constraint
thomas-bee
@thomas-bee
Aah yes. Thanks a lot @cprudhom I will dig around with that
thomas-bee
@thomas-bee
Hmm. Not really getting what to do with the cumulative constraint. I have this (in Groovy), but I need to express that no task overlaps and exclude certain daytime intervals from the available slots.
        List<IntVar> intervalStarts = []
        observations.size().times { i ->
            IntVar start = model.intVar("OB $i from", 0, TOTAL_SLOTS - 1)
            IntVar end = model.intVar("OB $i to", 0,  TOTAL_SLOTS - 1)
            model.taskVar(start, observations[i].requestedNoOfSlots, end)
            intervalStarts.add(start)
        }
        model.allDifferent((IntVar[]) intervalStarts).post()
Charles Prud'homme
@cprudhom
The cumulative constraint is what you need (see, its formal definition here: https://sofdem.github.io/gccat/gccat/Ccumulative.html). If all tasks have a height equal to one and the capacity is set to one too, then you have a dijunctive constraint which ensures no overlapping. If you want to exclude some daytime intervals, simply create fixed task (ie, start time and duration are fixed).
thomas-bee
@thomas-bee
@cprudhom thanks a lot this is working great for me so far.
João Pedro Schmitt
@schmittjoaopedro

Hello,

Is there some kind of operation on choco that changes the behavior of double values? I'm having some troubles when running tests using a docker container (maven:3.6.3-openjdk-11-slim).

System.out.println(10.0, 6); // Prints: 1000000.0
model.getSolver().propagate(); 
System.out.println(10.0, 6); // Prints: 1000000.0000000001
Charles Prud'homme
@cprudhom
I suppose you added some constraints that may have a side effect, didn’t you?
João Pedro Schmitt
@schmittjoaopedro
maybe, I'm debugging to find the cause.
João Pedro Schmitt
@schmittjoaopedro
The cause is Ibex, I've made some tests, and after calling the build method from ibex it mess with java double definition.
Charles Prud'homme
@cprudhom
I suppose it refines the domain wrt to constraints...
João Pedro Schmitt
@schmittjoaopedro
What do you get for the following sysouts on your Linux environment?
Ibex ibex = new Ibex(new double[]{0.000001, 0.000001});
ibex.add_ctr("{0}=acos({1})");
System.out.println(Math.pow(10, 6)); // Prints: 1000000.0
ibex.build();
System.out.println(Math.pow(10, 6)); // Prints: 1000000.0000000001
Charles Prud'homme
@cprudhom
On Mac OSX:
1000000.0
1000000.0000000001
([-10000.0,10000.0] ; [-0.6,0.6])
After contract:
([0.9272952180016122,2.2142974355881813] ; [-0.6,0.6])
João Pedro Schmitt
@schmittjoaopedro
I see that it's a problem
I've no idea how to handle it in ibex integration
I will open a issue in GIT for this
thomas-bee
@thomas-bee
Hi. I am scheduling observations of variable duration into hourly slots, each night has 10 slots or so. This works beautifully using only IntVar and the cumulative constraint. Now some of those observations belong to groups that should be scheduled strictly together filling up one or several consecutive nights. Is there an obvious way to express this?
Charles Prud'homme
@cprudhom
you can try to link them together with some constraints (like conditional constraints)?
thomas-bee
@thomas-bee
Hmm. I was thinking that maybe, if, I have N observations that have to be consecutive and they require a total of M slots, and starts[index] represents the respective start of observation IntVars, would it then not work to require that the max(starts) - min(starts) === (M - 1). I just have no clue how to extract such max of IntVars as an intermediate, "fresh" variable? Maybe the distance constraint, but since it only takes 2 variables would I have to add a constraint for each combination?
Charles Prud'homme
@cprudhom
If you already know which observations have to be consecutive, you can consider creating a meta-observation, whose start=min(start) and end=start+sum(durations)
thomas-bee
@thomas-bee
Got it. Will try, thanks a lot.
thomas-bee
@thomas-bee
I am experiencing a weird issue, surely I am doing something really wrong. I am holding two not one references to the same IntVar, initialized before invoking the solver. After invoking the solver and finding a solution (returns true) the values of the two references are not the same anymore. Is the solver doing some magic to those variables?
Charles Prud'homme
@cprudhom
it shouldn’t
if you can define a MWE, that would be helpful
thomas-bee
@thomas-bee
will try
thomas-bee
@thomas-bee
never mind, my bad
bigangswan
@bigangswan

Dear All, I am currently try to solve a new problem using Choco solver which needs to use the core idea from classic example Traveling Salesman Problem in tutorials. The example will be modified to given a start city and find a path traverse all cities to the end given city. For example, define a start city0 and the end the path travel all cities to city1.
Based on the current example code, I introduced the code like
model.arithm(succ[0], "=", 0).post();
model.arithm(succ[C - 1], "=", 1).post();
but solver.solve() didn't find any solution. I even replaced the code
model.subCircuit(succ, 0, model.intVar(C)).post();

to:

model.subPath(succ, model.intVar(0), model.intVar(1), 0, model.intVar(C)).post();

but again solver.solve() didn't find any solution.

does any one can give idea how to modify the code to solve this problem change?
Charles Prud'homme
@cprudhom
I believe model.arithm(succ[0], "=", 0).post(); is not what you want since it defines 0 as the successor of node 0 (a loop over itself).
bigangswan
@bigangswan
but use SubPath() still not work, I cann't find any example for this function use, look its description seem can find a path with start and end node
Charles Prud'homme
@cprudhom
can you share your code?
bigangswan
@bigangswan

I used same code from choco TSP example, but replace subCircuit() as subPath(). Based on choco document, subPath() is described as subPath​(IntVar[] vars, IntVar start, IntVar end, int offset, IntVar SIZE)

Creates a subPath constraint which ensures that

the elements of vars define a path of SIZE vertices, leading from start to end. Therefore I think this can replace subCircuit() to find a path, but in fact no solution found.

Charles Prud'homme
@cprudhom
In that case, this achieves your goal:
IntVar[] succ = new IntVar[C];
        for(int i = 0; i < C-1; i++){
            succ[i] = model.intVar("succ_"+i, 1, C-1); // forbid to reach cityO
        }
        succ[C - 1] = model.intVar("succ_" + (C-1), 0); // expect for the last city
that’s the only modification required
bigangswan
@bigangswan

that looks work, thanks :) One question I don't quite understand is the following code:

succ[C - 1] = model.intVar("succ_" + (C-1), 0); // expect for the last city

if set the last city range to 0 and why this lead to succ[C-2] always = 16 ?

João Pedro Schmitt
@schmittjoaopedro

Hello,

I'm looking for a way to improve the performance of my model that is reused by many HTTP requests (for performance reasons). Sometimes I want to ignore constraints from being executed (I have some use cases-that I need that), but after the propagation/search ends I want to re-add them to the model. I know that it's possible to unpost constraints from choco-solver. Therefore my questions are:

  • Should I be concerned with reification vars and views not being cleared after unpost a constraint?
  • Is there a better approach to ignore constraints from propagation/search without unposting/posting them between executions (something like a soft-constraints)?

Following I share my experiments so far:

public static void main(String[] args) throws Exception {

    Model model = new Model();
    IntVar x = model.intVar("x", new int[]{1, 2, 3});

    Constraint cstr = applyWith(model, model.arithm(x, "=", 1));
    System.out.println(x); // x = 1
    applyWithout(model, cstr);
    System.out.println(x); // x = {1..3}

    cstr = applyWith(model, model.arithm(x, "=", 1));
    System.out.println(x); // x = 1
    applyWithout(model, cstr);
    System.out.println(x); // x = {1..3}

}

public static Constraint applyWith(Model model, Constraint cstr) throws Exception {
    model.getSolver().hardReset();
    cstr.post();
    model.getSolver().getEnvironment().worldPush();
    model.getSolver().propagate();
    return cstr;
}

public static void applyWithout(Model model, Constraint cstr) throws Exception {
    model.getSolver().hardReset();
    model.unpost(cstr);
    model.getSolver().getEnvironment().worldPush();
    model.getSolver().propagate();
}

Thanks in advance

Charles Prud'homme
@cprudhom
@schmittjoaopedro I suppose you can play around with Propagator’s status and fake reification calling setReifiedSilent. Alternatively I would try to set it passive callingsetPassiveinstead ofunpost` but I think it may fail on solution

@bigangswan

that looks work, thanks :) One question I don't quite understand is the following code:

succ[C - 1] = model.intVar("succ_" + (C-1), 0); // expect for the last city

if set the last city range to 0 and why this lead to succ[C-2] always = 16 ?

The first line force the last city to be connected to the first one (with index 0). But you can change which city is the last (or first) one by playing with indices. The fact that such[C_2] = 16 is probably related to the distance matrix

thomas-bee
@thomas-bee
Sorry for a stupid beginner's question. Very happy with Choco so far, but I would like to improve performance using ParallePortfoliowith mutliple identical model instances. After solving, I understand there is portfolio.getBestModel()but what is the best way to access the values of the solution. In a single threaded approach I store references to those IntVars outside of the model.
Charles Prud'homme
@cprudhom
You can try streamSolutions() which returns a stream of solutions, or call new Solution(getBestModel()).record()
thomas-bee
@thomas-bee
Sorry I am not getting this. Assuming I build 4 identical models, each with an IntVar[] starts array of variables. When the parallel portfolio finds a solution, I don't know which model worked. So how do I retrieve the values? It seems I cannot query the solution for IntVars by name? So I need to keep references to the 4 arrays and then map the bestModel to one of the 4 arrays?
        ParallelPortfolio portfolio = new ParallelPortfolio()
        NO_OF_MODELS.times { index ->
            Model model = buildModel(observations)
            model.solver.limitTime(SOLVER_LIMIT)
            portfolio.addModel(model)
        }
        if (portfolio.solve()) {
            Solution solution = new Solution(portfolio.getBestModel()).record()
            // how do I retrieve the bound IntVar values by index        
      }
Charles Prud'homme
@cprudhom
portfolio gives you the model that found the solution through portfolio.getBestModel(). So you can map starts with model. Then when you are given a getBestModel() you can get its starts and record the solution
Or you can plug a solution monitor to achieve your goal
thomas-bee
@thomas-bee
Aah. I can derive my own model from choco Model, store the IntVars on it and pass that to the portfolio. Working fine. Thanks !
thomas-bee
@thomas-bee
Sorry to continue asking beginner's questions. I have a list of observations ob[1 .. 1000] each of which is one or several timeslots long, to be scheduled to timeslots, represented by their start slot IntVar starts[]. I have a constraint that a particular property of an OB has to have the same value in a particular subrange, say in timeslot [1 .. 15] all scheduled ob[] must have the same property value. Is there an off-the-shelf constraint that could help here?
Charles Prud'homme
@cprudhom
You can have a look at the element constraint I suppose it can help
thomas-bee
@thomas-bee
Hi again, may I ask some more please. Still prototyping with Choco, liking it a lot. Just like before, I have a list of observations ob[1 .. 1000] each of which is one or several timeslots long, to be scheduled to timeslots, represented by their start slot IntVar starts[]. Each observation has a duration in units of timeslots. What constraint would be good to express that in any given night, a subset of observations must be contiguous (but in no particular order) i.e. without gaps
Charles Prud'homme
@cprudhom
I would sum the durations and make sure that the results is equal to the night duration...
thomas-bee
@thomas-bee
Thank you. It is more subtle: they don't have to fill up the whole night, just a random sub-interval of the night (larger than 2h), to allocate a continuous interval to a particular observer
thomas-bee
@thomas-bee
Hmm. Is there an obvious way to extract the values of a SetVar chunk as an IntVar[] chunkIds array, then use those values as indices into anotherIntVar[] starts array and find the indexed entries?