42 #define NINT(x) (floor(x+0.5)) 46 void ReaderTSP::getNodesFromFile(
58 while ( i < graph->
nnodes && !filedata.eof() )
60 filedata >> nodenumber >> x_coords[i] >> y_coords[i];
64 if( nodenumber-1 != i)
66 cout <<
"warning: nodenumber <" << nodenumber <<
"> does not match its index in node list <" << i+1
67 <<
">. Node will get number " << i+1 <<
" when naming variables and constraints!" << endl;
69 node->
x = x_coords[i];
70 node->
y = y_coords[i];
75 assert( i == graph->nnodes );
102 bool ReaderTSP::checkValid(
106 std::string edgeweighttype,
114 cout <<
"parse error in file <" << name <<
"> dimension should be greater than 0"<< endl ;
120 cout <<
"parse error in file <" << name <<
"> type should be TSP" << endl;
124 if ( !( edgeweighttype ==
"EUC_2D" || edgeweighttype ==
"MAX_2D" || edgeweighttype ==
"MAN_2D" 125 || edgeweighttype ==
"GEO" || edgeweighttype ==
"ATT") )
127 cout <<
"parse error in file <" << name <<
"> unknown weight type, should be EUC_2D, MAX_2D, MAN_2D, ATT, or GEO" << endl;
133 cout <<
"error while reading file <" << name <<
">, graph is uninitialized. ";
134 cout <<
"Probably NODE_COORD_SECTION is missing" << endl;
168 double* x_coords =
NULL;
169 double* y_coords =
NULL;
172 double** weights =
NULL;
183 string name =
"MY_OWN_LITTLE_TSP";
186 string edgeweighttype =
"EUC_2D";
199 while( ! filedata.eof() )
201 if( token ==
"NAME:" )
203 else if( token ==
"NAME" )
204 filedata >> token >> name;
205 else if( token ==
"TYPE:" )
207 else if( token ==
"TYPE" )
208 filedata >> token >> type;
209 else if( token ==
"DIMENSION:" )
212 nedges = nnodes * (nnodes-1);
214 else if( token ==
"DIMENSION" )
216 filedata >> token >>
nnodes;
217 nedges = nnodes * (nnodes-1);
219 else if( token ==
"EDGE_WEIGHT_TYPE:" )
220 filedata >> edgeweighttype;
221 else if( token ==
"EDGE_WEIGHT_TYPE" )
222 filedata >> token >> edgeweighttype;
223 else if( token ==
"NODE_COORD_SECTION" || token ==
"DISPLAY_DATA_SECTION" )
234 assert(x_coords ==
NULL);
235 assert(y_coords ==
NULL);
237 x_coords =
new double[
nnodes];
238 y_coords =
new double[
nnodes];
239 getNodesFromFile(filedata, x_coords, y_coords, graph);
247 else if( token ==
"COMMENT:" || token ==
"COMMENT" || token ==
"DISPLAY_DATA_TYPE" || token ==
"DISPLAY_DATA_TYPE:" )
248 (void) getline( filedata, token );
249 else if( token ==
"EOF" )
251 else if( token ==
"" )
255 cout <<
"parse error in file <" << name <<
"> unknown keyword <" << token <<
">" << endl;
262 if( ! checkValid(graph, name, type, edgeweighttype, nnodes) )
265 assert(graph !=
NULL);
269 edgeforw = &( graph->
edges[0] );
270 edgebackw= &( graph->
edges[nedges/2] );
273 weights =
new double* [
nnodes];
274 for( i = 0; i <
nnodes; ++i )
275 weights[i] =
new double[nnodes];
279 for( i = 0; i <
nnodes; i++ )
281 nodestart = &graph->nodes[i];
282 for( j = i+1; j <
nnodes; j++ )
284 nodeend = &graph->nodes[j];
287 edgeforw->
adjac = nodeend;
288 edgebackw->
adjac = nodestart;
289 edgeforw->
back = edgebackw;
290 edgebackw->
back = edgeforw;
293 x = x_coords[(*nodestart).id] - x_coords[(*nodeend).id];
294 y = y_coords[(*nodestart).id] - y_coords[(*nodeend).id];
295 if( edgeweighttype ==
"EUC_2D")
297 else if( edgeweighttype ==
"MAX_2D")
298 edgeforw->
length =
MAX( ABS(x), ABS(y) );
299 else if( edgeweighttype ==
"MAN_2D")
300 edgeforw->
length = ABS(x) + ABS(y);
301 else if( edgeweighttype ==
"ATT")
302 edgeforw->
length = ceil(
sqrt( (x*x+y*y)/10.0 ) );
303 else if( edgeweighttype ==
"GEO")
305 const double pi = 3.141592653589793;
313 coords[0] = x_coords[(*nodestart).id];
314 coords[1] = y_coords[(*nodestart).id];
315 coords[2] = x_coords[(*nodeend).id];
316 coords[3] = y_coords[(*nodeend).id];
318 for( k = 0; k < 4; k++ )
320 degs[k] = coords[k] >= 0 ? floor(coords[k]) : ceil(coords[k]);
321 mins[k] = coords[k] - degs[k];
322 rads[k] = pi*(degs[k]+5.0*mins[k]/3.0)/180.0;
325 euler[0] =
cos(rads[1]-rads[3]);
326 euler[1] =
cos(rads[0]-rads[2]);
327 euler[2] =
cos(rads[0]+rads[2]);
328 edgeforw->
length = floor(6378.388 * acos(0.5*((1.0+euler[0])*euler[1]-(1.0-euler[0])*euler[2]))+1.0);
337 weights[i][j] = edgeforw->
length;
338 weights[j][i] = edgebackw->
length;
377 if( weights !=
NULL )
379 for( i = 0; i <
nnodes; i++ )
391 for( i = 0; i <
nnodes; i++ )
393 for( j = 0; j <
nnodes; j++ )
394 printf(
" %4.0f ",weights[i][j]);
405 for( i = 0; i < nedges/2; i++ )
409 stringstream varname;
410 edge = &graph->
edges[i];
421 SCIP_CALL( addVarToEdges(scip, edge, var) );
433 for( i = 0, node = &(graph->nodes[0]); i < nnodes; i++, node++ )
437 stringstream consname;
438 consname <<
"deg_con_v" << node->
id+1;
446 while( edge != NULL )
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_DECL_READERFREE(ReaderTSP::scip_free)
SCIPInterval cos(const SCIPInterval &x)
enum SCIP_Retcode SCIP_RETCODE
SCIP_DECL_READERWRITE(ReaderTSP::scip_write)
generator for global cuts in undirected graphs
SCIP_RETCODE SCIPcreateConsSubtour(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
SCIPInterval sqrt(const SCIPInterval &x)
struct GraphEdge * first_edge
C++ wrapper classes for SCIP.
std::ifstream tspifstream
C++ problem data for TSP.
C++ constraint handler for TSP subtour elimination constraints.
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
C++ file reader for TSP data files.
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPcreateObjProb(SCIP *scip, const char *name, scip::ObjProbData *objprobdata, SCIP_Bool deleteobject)
SCIP_DECL_READERREAD(ReaderTSP::scip_read)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
void release_graph(GRAPH **gr)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)