51 #define NINT(x) (floor(x+0.5)) 55 void ReaderTSP::getNodesFromFile(
67 while ( i < graph->
nnodes && !filedata.eof() )
69 filedata >> nodenumber >> x_coords[i] >> y_coords[i];
73 if( nodenumber-1 != i)
75 cout <<
"warning: nodenumber <" << nodenumber <<
"> does not match its index in node list <" << i+1
76 <<
">. Node will get number " << i+1 <<
" when naming variables and constraints!" << endl;
78 node->
x = x_coords[i];
79 node->
y = y_coords[i];
84 assert( i == graph->
nnodes );
111 bool ReaderTSP::checkValid(
113 const std::string& name,
114 const std::string& type,
115 const std::string& edgeweighttype,
123 cout <<
"parse error in file <" << name <<
"> dimension should be greater than 0"<< endl ;
129 cout <<
"parse error in file <" << name <<
"> type should be TSP" << endl;
133 if ( !( edgeweighttype ==
"EUC_2D" || edgeweighttype ==
"MAX_2D" || edgeweighttype ==
"MAN_2D" 134 || edgeweighttype ==
"GEO" || edgeweighttype ==
"ATT") )
136 cout <<
"parse error in file <" << name <<
"> unknown weight type, should be EUC_2D, MAX_2D, MAN_2D, ATT, or GEO" << endl;
142 cout <<
"error while reading file <" << name <<
">, graph is uninitialized. ";
143 cout <<
"Probably NODE_COORD_SECTION is missing" << endl;
177 double* x_coords =
NULL;
178 double* y_coords =
NULL;
181 double** weights =
NULL;
192 string name =
"MY_OWN_LITTLE_TSP";
195 string edgeweighttype =
"EUC_2D";
208 while( ! filedata.eof() )
210 if( token ==
"NAME:" )
212 else if( token ==
"NAME" )
213 filedata >> token >> name;
214 else if( token ==
"TYPE:" )
216 else if( token ==
"TYPE" )
217 filedata >> token >> type;
218 else if( token ==
"DIMENSION:" )
221 nedges = nnodes * (nnodes-1);
223 else if( token ==
"DIMENSION" )
225 filedata >> token >>
nnodes;
226 nedges = nnodes * (nnodes-1);
228 else if( token ==
"EDGE_WEIGHT_TYPE:" )
229 filedata >> edgeweighttype;
230 else if( token ==
"EDGE_WEIGHT_TYPE" )
231 filedata >> token >> edgeweighttype;
232 else if( token ==
"NODE_COORD_SECTION" || token ==
"DISPLAY_DATA_SECTION" )
243 assert(x_coords ==
NULL);
244 assert(y_coords ==
NULL);
246 x_coords =
new double[
nnodes];
247 y_coords =
new double[
nnodes];
248 getNodesFromFile(filedata, x_coords, y_coords, graph);
256 else if( token ==
"COMMENT:" || token ==
"COMMENT" || token ==
"DISPLAY_DATA_TYPE" || token ==
"DISPLAY_DATA_TYPE:" )
257 (void) getline( filedata, token );
258 else if( token ==
"EOF" )
260 else if( token ==
"" )
264 cout <<
"parse error in file <" << name <<
"> unknown keyword <" << token <<
">" << endl;
271 if( ! checkValid(graph, name, type, edgeweighttype, nnodes) )
274 assert(graph !=
NULL);
278 edgeforw = &( graph->
edges[0] );
279 edgebackw= &( graph->
edges[nedges/2] );
282 weights =
new double* [
nnodes];
283 for( i = 0; i <
nnodes; ++i )
284 weights[i] =
new double[nnodes];
288 for( i = 0; i <
nnodes; i++ )
290 nodestart = &graph->
nodes[i];
291 for( j = i+1; j <
nnodes; j++ )
293 nodeend = &graph->
nodes[j];
296 edgeforw->
adjac = nodeend;
297 edgebackw->
adjac = nodestart;
298 edgeforw->
back = edgebackw;
299 edgebackw->
back = edgeforw;
302 x = x_coords[(*nodestart).id] - x_coords[(*nodeend).id];
303 y = y_coords[(*nodestart).id] - y_coords[(*nodeend).id];
304 if( edgeweighttype ==
"EUC_2D")
305 edgeforw->
length = sqrt( x*x + y*y );
306 else if( edgeweighttype ==
"MAX_2D")
307 edgeforw->
length =
MAX( ABS(x), ABS(y) );
308 else if( edgeweighttype ==
"MAN_2D")
309 edgeforw->
length = ABS(x) + ABS(y);
310 else if( edgeweighttype ==
"ATT")
311 edgeforw->
length = ceil( sqrt( (x*x+y*y)/10.0 ) );
312 else if( edgeweighttype ==
"GEO")
314 const double pi = 3.141592653589793;
322 coords[0] = x_coords[(*nodestart).id];
323 coords[1] = y_coords[(*nodestart).id];
324 coords[2] = x_coords[(*nodeend).id];
325 coords[3] = y_coords[(*nodeend).id];
327 for( k = 0; k < 4; k++ )
329 degs[k] = coords[k] >= 0 ? floor(coords[k]) : ceil(coords[k]);
330 mins[k] = coords[k] - degs[k];
331 rads[k] = pi*(degs[k]+5.0*mins[k]/3.0)/180.0;
334 euler[0] = cos(rads[1]-rads[3]);
335 euler[1] = cos(rads[0]-rads[2]);
336 euler[2] = cos(rads[0]+rads[2]);
337 edgeforw->
length = floor(6378.388 * acos(0.5*((1.0+euler[0])*euler[1]-(1.0-euler[0])*euler[2]))+1.0);
346 weights[i][j] = edgeforw->
length;
347 weights[j][i] = edgebackw->
length;
386 if( weights !=
NULL )
388 for( i = 0; i <
nnodes; i++ )
400 for( i = 0; i <
nnodes; i++ )
402 for( j = 0; j <
nnodes; j++ )
403 printf(
" %4.0f ",weights[i][j]);
414 for( i = 0; i < nedges/2; i++ )
418 stringstream varname;
419 edge = &graph->
edges[i];
430 SCIP_CALL( addVarToEdges(scip, edge, var) );
442 for( i = 0, node = &(graph->
nodes[0]); i < nnodes; i++, node++ )
446 stringstream consname;
447 consname <<
"deg_con_v" << node->
id+1;
455 while( edge != NULL )
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
SCIP_DECL_READERFREE(ReaderTSP::scip_free)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
enum SCIP_Retcode SCIP_RETCODE
SCIP_DECL_READERWRITE(ReaderTSP::scip_write)
generator for global cuts in undirected graphs
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
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)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
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 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)
C++ file reader for TSP data files.
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPcaptureVar(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)
void release_graph(GRAPH **gr)