51#define NINT(x) (floor(x+0.5))
59 while( *str !=
'\0' && ( isspace(*str) || *str ==
':') )
63 while( *str !=
'\0' && *str !=
':' && ! isspace(*str) )
70 while( *str !=
'\0' && ( isspace(*str) || *str ==
':') )
116 if( nodenumber-1 !=
i)
118 cout <<
"warning: nodenumber <" << nodenumber <<
"> does not match its index in node list <" <<
i+1
119 <<
">. Node will get number " <<
i+1 <<
" when naming variables and constraints!" << endl;
122 node->
x = x_coords[
i];
123 node->
y = y_coords[
i];
157bool ReaderTSP::checkValid(
159 const std::string& name,
160 const std::string& type,
161 const std::string& edgeweighttype,
169 cout <<
"parse error in file <" << name <<
"> dimension should be greater than 0"<< endl ;
175 cout <<
"parse error in file <" << name <<
"> type should be TSP" << endl;
179 if ( !( edgeweighttype ==
"EUC_2D" || edgeweighttype ==
"MAX_2D" || edgeweighttype ==
"MAN_2D"
180 || edgeweighttype ==
"GEO" || edgeweighttype ==
"ATT") )
182 cout <<
"parse error in file <" << name <<
"> unknown weight type, should be EUC_2D, MAX_2D, MAN_2D, ATT, or GEO" << endl;
188 cout <<
"error while reading file <" << name <<
">, graph is uninitialized. ";
189 cout <<
"Probably NODE_COORD_SECTION is missing" << endl;
223 double* x_coords =
NULL;
224 double* y_coords =
NULL;
227 double** weights =
NULL;
238 string name =
"MY_OWN_LITTLE_TSP";
241 string edgeweighttype =
"EUC_2D";
261 if( token ==
"NAME" )
263 else if( token ==
"TYPE" )
265 else if( token ==
"DIMENSION" )
274 else if( token ==
"EDGE_WEIGHT_TYPE" )
276 else if( token ==
"NODE_COORD_SECTION" || token ==
"DISPLAY_DATA_SECTION" )
290 x_coords =
new double[
nnodes];
291 y_coords =
new double[
nnodes];
292 SCIP_CALL( getNodesFromFile(file, x_coords, y_coords, graph) );
300 else if( token ==
"COMMENT:" || token ==
"COMMENT" || token ==
"DISPLAY_DATA_TYPE" || token ==
"DISPLAY_DATA_TYPE:" )
304 else if( token ==
"EOF" )
306 else if( token ==
"" )
310 cout <<
"parse error in file <" << name <<
"> unknown keyword <" << token <<
">" << endl;
321 if( ! checkValid(graph, name, type, edgeweighttype,
nnodes) )
328 edgeforw = &( graph->
edges[0] );
329 edgebackw= &( graph->
edges[nedges/2] );
332 weights =
new double* [
nnodes];
334 weights[
i] =
new double[
nnodes];
340 nodestart = &graph->
nodes[
i];
341 for( j =
i+1; j <
nnodes; j++ )
343 nodeend = &graph->
nodes[j];
346 edgeforw->
adjac = nodeend;
347 edgebackw->
adjac = nodestart;
348 edgeforw->
back = edgebackw;
349 edgebackw->
back = edgeforw;
352 x = x_coords[(*nodestart).id] - x_coords[(*nodeend).id];
353 y = y_coords[(*nodestart).id] - y_coords[(*nodeend).id];
354 if( edgeweighttype ==
"EUC_2D")
356 else if( edgeweighttype ==
"MAX_2D")
358 else if( edgeweighttype ==
"MAN_2D")
360 else if( edgeweighttype ==
"ATT")
361 edgeforw->
length = ceil( sqrt( (
x*
x+
y*
y)/10.0 ) );
362 else if( edgeweighttype ==
"GEO")
364 const double pi = 3.141592653589793;
372 coords[0] = x_coords[(*nodestart).id];
373 coords[1] = y_coords[(*nodestart).id];
374 coords[2] = x_coords[(*nodeend).id];
375 coords[3] = y_coords[(*nodeend).id];
377 for( k = 0; k < 4; k++ )
379 degs[k] = coords[k] >= 0 ? floor(coords[k]) : ceil(coords[k]);
380 mins[k] = coords[k] - degs[k];
381 rads[k] = pi*(degs[k]+5.0*mins[k]/3.0)/180.0;
384 euler[0] = cos(rads[1]-rads[3]);
385 euler[1] = cos(rads[0]-rads[2]);
386 euler[2] = cos(rads[0]+rads[2]);
387 edgeforw->
length = floor(6378.388 * acos(0.5*((1.0+euler[0])*euler[1]-(1.0-euler[0])*euler[2]))+1.0);
396 weights[
i][j] = edgeforw->
length;
397 weights[j][
i] = edgebackw->
length;
436 if( weights !=
NULL )
452 for( j = 0; j <
nnodes; j++ )
453 printf(
" %4.0f ",weights[
i][j]);
464 for(
i = 0;
i < nedges/2;
i++ )
468 stringstream varname;
496 stringstream consname;
497 consname <<
"deg_con_v" << node->
id+1;
505 while( edge !=
NULL )
C++ constraint handler for TSP subtour elimination constraints.
SCIP_Bool create_graph(int n, int m, GRAPH **gr)
void release_graph(GRAPH **gr)
generator for global cuts in undirected graphs
struct GraphNode GRAPHNODE
struct GraphEdge GRAPHEDGE
C++ problem data for TSP.
string getToken(char *&str)
C++ file reader for TSP data files.
Constraint handler for linear constraints in their most general form, .
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
int SCIPfeof(SCIP_FILE *stream)
int SCIPfclose(SCIP_FILE *fp)
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
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_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
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)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
assert(minobj< SCIPgetCutoffbound(scip))
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 SCIPcreateObjProb(SCIP *scip, const char *name, scip::ObjProbData *objprobdata, SCIP_Bool deleteobject)
C++ wrapper classes for SCIP.
wrapper functions to map file i/o to standard or zlib file i/o
struct SCIP_File SCIP_FILE
struct GraphEdge * first_edge
struct SCIP_Cons SCIP_CONS
#define SCIP_DECL_READERWRITE(x)
#define SCIP_DECL_READERREAD(x)
#define SCIP_DECL_READERFREE(x)
enum SCIP_Retcode SCIP_RETCODE