Originally posted by: SystemAdmin

Hi all,

I have written a small code for scheduling the trucks on docks , but i am getting the following error..

!

---

! Satisfiability problem - 19 variables, 13 constraints
! Problem found infeasible at the root node
!

---

! Search terminated normally, model has no solution.
! Number of branches : 0
! Number of fails : 1
! Total memory usage : 991.2 kB (562.6 kB CP Optimizer + 428.7 kB Concert)
! Time spent in solve : 0.04s (0.04s engine + 0.00s extraction)
! Search speed (br. / s) : 0
!

---

If anyone can look at my OPL code and help me that would be gr8.
using CP;
// A tuple have all information about a route//mainly cost
tuple Route {
key int routeid;
int carrierid;
int loadtime;
int paperworktime;
};
{Route} RouteData = ...;

// A tuple have information about warehouse

int numberofdocks = ...;
int planstarttime= ...;
int planendtime= ...;

// tuple having information of each ARC
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { <r1.routeid, r2.routeid, r1.loadtime+r1.paperworktime> |
r1,r2 in RouteData: r1.routeid!=r2.routeid};
// ids of all the warehouse(start /end) and customers
{int} routeIds = { r.routeid | r in RouteData };

// calculate the interval time of visit reach and leave for every customers
dvar interval visit r in RouteData in planstarttime..planendtime size r.loadtime+r.paperworktime;

// an interval variable which will
dvar interval day_spanhttp://n in 1..numberofdocks in planstarttime..planendtime;

// interval of each route
dvar interval tvisithttp://n in 1..numberofdocksr in RouteData in planstarttime..planendtime;

// sequence variable for each day warehouse use
dvar sequence route http://t in 1..numberofdocks in all(r in RouteData) tvisit[t][r] types all(r in RouteData) r.routeid;
// an integer variable gives the output as routeid for every route in scheduling
dvar int nextroutehttp://t in 1..numberofdocksr in RouteData;

subject to
{
forall(n in 1..numberofdocks)
{
// fixing the total span of the sequence of all the route
span (day_span[n], all(r in RouteData) tvisit[n][r]);
noOverlap(route[n], Dist);
forall(r in RouteData)
{
nextroute[n][r] == typeOfNext(route[n],tvisit[n][r],r.routeid);
}
}
forall(r in RouteData) {
alternative(visit[r], all(n in 1..numberofdocks) tvisit[n][r]);
}

}
Data File----------------------

// A tuple have information about warehouse

numberofdocks = 2;
planstarttime = 0;
planendtime = 1440;

// A tuple have all information about a route
RouteData = {
<1, 0, 100, 30>,
<2, 0, 120, 40>,
<3, 0, 150, 90>,
};

Also I have few question to enhance my my model capabilities...

How can I use the interval variable to get the time when it reach at dock and when it leaves it to further constraint my model.

Thanks
Arun Lila
#ConstraintProgramming-General
#DecisionOptimization

Hi,

could you post your code within braces?

regards
#ConstraintProgramming-General
#DecisionOptimization

PS:

about

to get the time when it reach at dock and when it leaves it to further constraint my model.

Do you know startOf and endOf functions on an interval?

regards
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

(

using CP;
// A tuple have all information about a route//mainly cost
tuple Route {
key int routeid;
int carrierid;
int loadtime;
int paperworktime;
};
{Route} RouteData = ...;

// A tuple have information about warehouse

int numberofdocks = ...;
int planstarttime= ...;
int planendtime= ...;

// tuple having information of each ARC
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { <r1.routeid, r2.routeid, r1.loadtime+r1.paperworktime> |
r1,r2 in RouteData: r1.routeid!=r2.routeid};
// ids of all the warehouse(start /end) and customers
{int} routeIds = { r.routeid | r in RouteData };

// calculate the interval time of visit reach and leave for every customers
dvar interval visit r in RouteData in planstarttime..planendtime size r.loadtime+r.paperworktime;

// an interval variable which will
dvar interval day_spanhttp://n in 1..numberofdocks in planstarttime..planendtime;

// interval of each route
dvar interval tvisithttp://n in 1..numberofdocksr in RouteData in planstarttime..planendtime;

// sequence variable for each day warehouse use
dvar sequence route http://t in 1..numberofdocks in all(r in RouteData) tvisit[t][r] types all(r in RouteData) r.routeid;
// an integer variable gives the output as routeid for every route in scheduling
dvar int nextroutehttp://t in 1..numberofdocksr in RouteData;

subject to
{
forall(n in 1..numberofdocks)
{
// fixing the total span of the sequence of all the route
span (day_span[n], all(r in RouteData) tvisit[n][r]);
noOverlap(route[n], Dist);
forall(r in RouteData)
{
nextroute[n][r] == typeOfNext(route[n],tvisit[n][r],r.routeid);
}
}
forall(r in RouteData) {
alternative(visit[r], all(n in 1..numberofdocks) tvisit[n][r]);
}

}

)
I dont this is the right way to do it in CP or not, I have tried to model like TSP or SPP.

Basically the problem is to schedule every truck(route here) on available docks.

There are some constraints related to startof and endof time of interval , which i need to add.

I was checking in between , but was getting an error.

Thanks
Arun Lila
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

(

using CP;
// A tuple have all information about a route//mainly cost
tuple Route {
key int routeid;
int carrierid;
int loadtime;
int paperworktime;
};
{Route} RouteData = ...;

// A tuple have information about warehouse

int numberofdocks = ...;
int planstarttime= ...;
int planendtime= ...;

// tuple having information of each ARC
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { <r1.routeid, r2.routeid, r1.loadtime+r1.paperworktime> |
r1,r2 in RouteData: r1.routeid!=r2.routeid};
// ids of all the warehouse(start /end) and customers
{int} routeIds = { r.routeid | r in RouteData };

// calculate the interval time of visit reach and leave for every customers
{dvar interval visit r in RouteData in planstarttime..planendtime size r.loadtime+r.paperworktime;}

// an interval variable which will
{dvar interval day_spanhttp://n in 1..numberofdocks in planstarttime..planendtime;}

// interval of each route
{dvar interval tvisithttp://n in 1..numberofdocksr in RouteData in planstarttime..planendtime; }

// sequence variable for each day warehouse use
{dvar sequence route http://t in 1..numberofdocks in all(r in RouteData) tvisit[t][r] types all(r in RouteData) r.routeid;}
// an integer variable gives the output as routeid for every route in scheduling
{dvar int nextroutehttp://t in 1..numberofdocksr in RouteData;}

subject to
{
forall(n in 1..numberofdocks)
{
// fixing the total span of the sequence of all the route
span (day_span[n], all(r in RouteData) tvisit[n][r]);
noOverlap(route[n], Dist);
forall(r in RouteData)
{
nextroute[n][r] == typeOfNext(route[n],tvisit[n][r],r.routeid);
}
}
forall(r in RouteData) {
alternative(visit[r], all(n in 1..numberofdocks) tvisit[n][r]);
}

}

)
I dont this is the right way to do it in CP or not, I have tried to model like TSP or SPP.

Basically the problem is to schedule every truck(route here) on available docks.

There are some constraints related to startof and endof time of interval , which i need to add.

I was checking in between , but was getting an error.

Thanks
Arun Lila
#ConstraintProgramming-General
#DecisionOptimization

hi

sorry i meant, add {code} before and after your code

regards
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Sorry

here it is
{
using CP;
// A tuple have all information about a route//mainly cost
tuple Route {
key int routeid;
int carrierid;
int loadtime;
int paperworktime;
};
{Route} RouteData = ...;

// A tuple have information about warehouse

int numberofdocks = ...;
int planstarttime= ...;
int planendtime= ...;

// tuple having information of each ARC
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { <r1.routeid, r2.routeid, r1.loadtime+r1.paperworktime> |
r1,r2 in RouteData: r1.routeid!=r2.routeid};
// ids of all the warehouse(start /end) and customers
{int} routeIds = { r.routeid | r in RouteData };

// calculate the interval time of visit reach and leave for every customers
{dvar interval visit r in RouteData in planstarttime..planendtime size r.loadtime+r.paperworktime;}

// an interval variable which will
{dvar interval day_spanhttp://n in 1..numberofdocks in planstarttime..planendtime;}

// interval of each route
{dvar interval tvisithttp://n in 1..numberofdocksr in RouteData in planstarttime..planendtime; }

// sequence variable for each day warehouse use
{dvar sequence route http://t in 1..numberofdocks in all(r in RouteData) tvisit[t][r] types all(r in RouteData) r.routeid;}
// an integer variable gives the output as routeid for every route in scheduling
{dvar int nextroutehttp://t in 1..numberofdocksr in RouteData;}

subject to
{
forall(n in 1..numberofdocks)
{
// fixing the total span of the sequence of all the route
span (day_span[n], all(r in RouteData) tvisit[n][r]);
noOverlap(route[n], Dist);
forall(r in RouteData)
{
nextroute[n][r] == typeOfNext(route[n],tvisit[n][r],r.routeid);
}
}
forall(r in RouteData) {
alternative(visit[r], all(n in 1..numberofdocks) tvisit[n][r]);
}

}
}
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Can you please guide me , on the error
Also I want to know whether my approach for this problem is right or not ?
{
using CP;
// A tuple have all information about a route//mainly cost
tuple Route {
key int routeid;
int carrierid;
int loadtime;
int paperworktime;
};
{Route} RouteData = ...;

// A tuple have information about warehouse

int numberofdocks = ...;
int planstarttime= ...;
int planendtime= ...;

// tuple having information of each ARC
tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { <r1.routeid, r2.routeid, r1.loadtime+r1.paperworktime> |
r1,r2 in RouteData: r1.routeid!=r2.routeid};
// ids of all the warehouse(start /end) and customers
{int} routeIds = { r.routeid | r in RouteData };

// calculate the interval time of visit reach and leave for every customers
dvar interval visit r in RouteData in planstarttime..planendtime size r.loadtime+r.paperworktime;

// an interval variable which will
dvar interval day_spanhttp://n in 1..numberofdocks in planstarttime..planendtime;

// interval of each route
dvar interval tvisithttp://n in 1..numberofdocksr in RouteData in planstarttime..planendtime;

// sequence variable for each day warehouse use
dvar sequence route http://t in 1..numberofdocks in all(r in RouteData) tvisit[t][r] types all(r in RouteData) r.routeid;
// an integer variable gives the output as routeid for every route in scheduling
dvar int nextroutehttp://t in 1..numberofdocksr in RouteData;

subject to
{
forall(n in 1..numberofdocks)
{
// fixing the total span of the sequence of all the route
span (day_span[n], all(r in RouteData) tvisit[n][r]);
noOverlap(route[n], Dist);
forall(r in RouteData)
{
nextroute[n][r] == typeOfNext(route[n],tvisit[n][r],r.routeid);
}
}
forall(r in RouteData) {
alternative(visit[r], all(n in 1..numberofdocks) tvisit[n][r]);
}

}
}

The Error is

!

---

! Satisfiability problem - 19 variables, 13 constraints
! Problem found infeasible at the root node
!

---

! Search terminated normally, model has no solution.
! Number of branches : 0
! Number of fails : 1
! Total memory usage : 991.2 kB (562.6 kB CP Optimizer + 428.7 kB Concert)
! Time spent in solve : 0.00s (0.00s engine + 0.00s extraction)
! Search speed (br. / s) : 0
!

---

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

The model is infeasible because you state an alternative constraints over a set of intervals that are not optional. You need to declare the tvisit variables like this:

// interval of each route
dvar interval tvisithttp://n in 1..numberofdocksr in RouteData optional in planstarttime..planendtime;

Secondary intervals in an alternative should be optionals. It does not make sense otherwise.

You can find where an infeasibility is located by using Cplex Optimization Studio 12.5, that gives you a minimal set of conflicting constraints when you have no solution at the root node. In this case it points out one of the alternative constraints.

Regards

Philippe
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Philippe and Alex,

I am able to run my model ,

I have few question about CP models ,

1. How can we run it quick for large instance , for my problem if I don’t set any cp param it run for more than 10 minutes and continuously running….
Then I set up the CP param as shown in below model file

It does give result in 10 second,
How could I set CP Param for large instance of data.

My model is

{
using CP;
// A tuple have all information about a route
tuple Route {
key int routeid;
int carrierid;
int loadtime;
int paperworktime;
};
{Route} RouteData = ...;

// A tuple have information about warehouse

int numberofdocks = ...;
int planstarttime= ...;
int planendtime= ...;
{Route} routeVisits = { v | v in RouteData : v.routeid!=4 && v.routeid!=0};
// A tuple have information about carrier
tuple Carrier{
key int carrierid;
float waitingcost;
};
{Carrier} CarrierData = ...;

// A generated table has all time windows of customer for a route
tuple RouteCustTimeWindows{
key int routeid;
key int custid;
key int timewindowid;
int starttime;
int endtime;
};
{RouteCustTimeWindows} RouteCustTimeWindowsData = ...;

// A generate table has customer visiting sequence for a route
tuple RouteCust{
key int routeid;
key int custid;
int unloadtime;
int paperworktime;
int traveltime;
int starttime;
int endtime;
};
{RouteCust} RouteCustData = ...;
// tuple of only customers
{RouteCust} routecust = { v | v in RouteCustData : v.custid!=0 };
execute{
writeln("routecust = ", routecust);
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { <r1.routeid, r2.routeid, 0> |
r1,r2 in RouteData: r1.routeid!=r2.routeid && r1.routeid != 4 && r2.routeid != 0};

// calculate the interval time of visit reach and leave for every customers
dvar interval visit r in routeVisits in planstarttime..planendtime size r.loadtime+r.paperworktime;
// an interval variable which will
dvar interval day_spanhttp://n in 1..numberofdocks optional;

// interval of each route
dvar interval tvisithttp://n in 1..numberofdocksr in RouteData optional(r.routeid!=4 && r.routeid!=0);

// sequence variable for each day warehouse use
dvar sequence route http://t in 1..numberofdocks in all(r in RouteData)tvisit[t][r] types all(r in RouteData) r.routeid;

// reach and start time at each customer by a route
dvar interval cvixitrcd in RouteCustData in rcd.starttime..rcd.endtime size rcd.unloadtime+rcd.paperworktime;

dvar int+ truckwaitingtimeroutecust;

dvar boolean OnlyoneTimeRouteCustTimeWindowsData;

execute {
cp.param.NoOverlapInferenceLevel = "Medium";
cp.param.ElementInferenceLevel = "Low";
//cp.param.TemporalRelaxation = "Off";
cp.param.TimeMode = "ElapsedTime";
cp.param.TimeLimit = 10;
cp.param.Workers = 1;
var f = cp.factory;
cp.setSearchPhases(f.searchPhase(route));
writeln("Using",numberofdocks, " docks");
}

// objective function
dexpr float objective = sum(rc in routecust)truckwaitingtimerc;

// minimize objective function
minimize objective;

subject to
{
forall(n in 1..numberofdocks)
{
// fixing the total span of the sequence of all the route
span (day_span[n], all(r in routeVisits) tvisit[n][r]);
startOf(tvisit[n]<0>)==0;
last (route[n],tvisit[n]<4>);
noOverlap(route[n], Dist);
}
forall(r in routeVisits)
{
alternative(visit[r], all(n in 1..numberofdocks)tvisit[n][r]);

forall(rcd in RouteCustData)
{
if(r.routeid == rcd.routeid && rcd.custid ==0)
{
startOf(cvixitrcd) == endOf(visit[r]);
}
if(r.routeid == rcd.routeid && rcd.custid > 0)
{
startOf(cvixitrcd) == endOf(cvixitprev(RouteCustData, rcd)) + rcd.traveltime + truckwaitingtimercd ;
}
}
}
forall(rcd in routecust)
{
sum(rctw in RouteCustTimeWindowsData: rcd.routeid == rctw.routeid
&& rcd.custid == rctw.custid)OnlyoneTimerctw == 1;
}

forall(rcd in routecust)
{
sum(rctw in RouteCustTimeWindowsData: rcd.routeid == rctw.routeid
&& rcd.custid == rctw.custid)OnlyoneTimerctw*rctw.starttime <= startOf(cvixitrcd);
endOf(cvixitrcd) <= sum(rctw in RouteCustTimeWindowsData: rcd.routeid == rctw.routeid
&& rcd.custid == rctw.custid)OnlyoneTimerctw*rctw.endtime;

}
}
}

And Data are

numberofdocks = 2;
planstarttime = 0;
planendtime = 420;

// A tuple have all information about a route
RouteData = {
<0, 0, 0, 0>,
<1, 1, 100, 30>,
<2, 1, 120, 40>,
<3, 2, 150, 90>,
<4, 0, 0, 0>,
};

RouteCustData = {

<1, 0, 0, 0, 0, 0, 3000>,
<1, 1, 10, 3, 10, 10, 3000>,
<1, 2, 10, 3, 10, 20, 3000>,
<2, 0, 0, 0, 0, 0, 3000>,
<2, 3, 12, 4, 10, 10, 3000>,
<3, 0, 0, 0, 0, 0, 3000>,
<3, 1, 15, 9, 10, 10, 3000>,
<3, 2, 15, 9, 10, 20, 3000>,
<3, 3, 15, 9, 10, 30, 3000>,
};

RouteCustTimeWindowsData =
{
<1, 1, 1, 400, 1000>,
<1, 1, 2, 1500, 2500>,
<1, 2, 1, 300, 700>,
<1, 2, 2, 900, 1300>,
<2, 3, 1, 200, 400>,
<2, 3, 2, 500, 700>,
<2, 3, 3, 800, 1000>,
<2, 3, 4, 1100, 1300>,
<3, 1, 1, 300, 400>,
<3, 1, 2, 800, 1100>,
<3, 2, 1, 900, 1000>,
<3, 2, 2, 1100, 1400>,
<3, 2, 3, 1600, 2500>,
<3, 3, 1, 1000, 1020>,
<3, 3, 2, 1100, 1500>,
};

CarrierData = {
<1, 10>,
<2, 12>,
};

A very small instance where as numberofdocks could be 20 or 30
And RouteData could be 100.
Also I have one question about the constraint which I have created.

In my model the interval variable dvar interval cvixit should take values out of number of time windows

To do that I have done what we do in MIP, defined an integer variable and set it to choose 1 time window out of many ..like
{
forall(rcd in routecust)
{
sum(rctw in RouteCustTimeWindowsData: rcd.routeid == rctw.routeid
&& rcd.custid == rctw.custid)OnlyoneTimerctw == 1;
}

}

Than the upper and lower bound constraint for the interval time for the selected time window…like
{

forall(rcd in routecust)
{
sum(rctw in RouteCustTimeWindowsData: rcd.routeid == rctw.routeid
&& rcd.custid == rctw.custid)OnlyoneTimerctw*rctw.starttime <= startOf(cvixitrcd);
endOf(cvixitrcd) <= sum(rctw in RouteCustTimeWindowsData: rcd.routeid == rctw.routeid
&& rcd.custid == rctw.custid)OnlyoneTimerctw*rctw.endtime;

}
}

I want to know is there any direct way to do while initializing the interval variable dvar interval cvixit
Or using function like alternative

So that it can run little faster.

Hope I put well my problem.

Please help ,

Thanks
Arun Lila
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks , It am happy to have interaction with you all. It was helpful.
#ConstraintProgramming-General
#DecisionOptimization