CVRP model

[Iván Riera]

I have problems trying to modeler this CVRP:


###Sets and parameters###


param n :=13;
param k :=4;

set dem_nodes := {2..n};
set nodes ordered := {1..n};
set veh;
set links := {i in nodes, j in nodes: i<>j};

param Q{veh}>0;

param q{nodes}>=0;

param travel_cost{links};



###Variables###
var x{links, veh}, binary;
var y{links}, binary;
#var z{nodes}, integer;



###The objective function###
minimize Total_cost:
sum {(i,j) in links} travel_cost[i,j] * x[i,j,k];


###Constraints###


#Starting from depot (node 1), a vehicle must visit a customer i.
subject to Start{j in dem_nodes}:
sum{i in nodes: i<>j} y[i,j]=1;

#After visiting a customer i,the vehicle must leave for another
customer j.
subject to Continue{i in dem_nodes}:
sum{(i,j) in links: i<>j} y[i,j]=1;

#The nº of vehicles going from node 1 to all nodes j must be equal to
K.
subject to Going:
sum{j in dem_nodes, i in nodes: i<>j} y[1,j]=k;

#The nº of vehicles returning to node 1 from all nodes i must be equal
to K.
subject to Backing:
sum{i in dem_nodes, j in nodes: i<>j} y[i,1]=k;

#Each vehicle must carry less than or equal to its capacity.
subject to Capacity:
sum {i in dem_nodes, j in nodes: i<>j} x[i,j,k]*q[j]<=Q[k];

#There must be a link between xkij and yij variables. Each node,
except
#the depot, can only be served once by only one vehicle.
subject to Served:
sum{i in nodes, j in nodes: i<>j} x[i,j,1] + sum{i in nodes, j in
nodes: i<>j} x[i,j,2] + sum{i in nodes, j in nodes: i<>j} x[i,j,3] +
sum{i in nodes, j in nodes: i<>j} x[i,j,4] =sum{i in nodes, j in
nodes: i<>j} y[i,j];

#The solution must not contain any cycle using the nodes 2,3,..,n. Not
#contain any subtours of these nodes.



Each time I try to use {k in veh}, I get syntex error, and I need a
hand for doing the last constraint...should I define a subtour set or
something similar? how?

Thank you!

[Robert Fourer]

There is nothing wrong with "{k in veh}" so the error must have something to
do with the context in which you are using it. However it is hard to say
more, without seeing the statement that gave the error, and the complete
error message.

It seems that for your last constraint you must have been trying to write
something like this:

subject to Served:
sum {k in veh} sum{i in nodes, j in nodes: i<>j} x[i,j,k]
= sum{i in nodes, j in nodes: i<>j} y[i,j];

For an example of how subtour constraints can be handled, see question 4.4
at www.ampl.com/FAQ and the traveling salesman example referenced there.

Bob Fourer
4...@ampl.com

-----Original Message-----
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of Iván Riera
Sent: Monday, April 30, 2012 5:25 PM
To: AMPL Modeling Language
Subject: [AMPL 5732] CVRP model

I have problems trying to modeler this CVRP:

###Sets and parameters###

param n :=13;
param k :=4;

set dem_nodes := {2..n};
set nodes ordered := {1..n};
set veh;
set links := {i in nodes, j in nodes: i<>j};

param Q{veh}>0;

param q{nodes}>=0;

param travel_cost{links};

###Variables###

var x{links, veh}, binary;
var y{links}, binary;

...

[Iván Riera]

Thanks a lot for your answer and help.

I tried your code, and I get the same error as always, when I try to
use "k in veh":

cvrp.mod, line 65 (offset 1890):
syntax error
context: sum {k >>> in <<< veh} sum{i in Nodes, j in Nodes: i<>j}
x[i,j,k]

I am really lost with that, any help with it would be great!!

[Robert Fourer]

This kind of syntax error is often seen when k has already been defined in
the model (as a param, for example) and then is defined again in an indexing
expression like {k in veh}.

Bob Fourer
4...@ampl.com


-----Original Message-----
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of Iván Riera
Sent: Sunday, May 06, 2012 8:04 PM
To: AMPL Modeling Language

[Iván Riera]

Thanks a lot again.

Now, I have no problems with the k, I think I had solve it, but I
recieved this problem when I try to solve:

CPLEX 11.2.0: integer infeasible.
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.

I read that this can appear when you have variable * variable, but my
TSP model have almost the same min function and it works OK.

Any hint for this?? :)

[Robert Fourer]

The "integer infeasible" message indicates CPLEX has determined that there
is no way to satisfy all of the constraints and also integrality of all the
integer variables. Most likely there is an error in your constraints that
makes them impossible to satisfy. If your problem is not too large, then
you might get some help finding the cause of the infeasibility by using the
"iisfind" feature in CPLEX, as described in other postings and in the
documentation at

http://www.ampl.com/BOOKLETS/amplcplex122userguide.pdf

This basically tries to find a small subset of constraints that are
infeasible by themselves.

[Iván Riera]

I'll try that, thank you again, Bob!!