42 #define NINT(x) (floor(x+0.5)) 45 void ReaderTSP::getNodesFromFile(
46 std::ifstream& filedata,
57 while ( i < graph->
nnodes && !filedata.eof() )
59 filedata >> nodenumber >> x_coords[i] >> y_coords[i];
63 if( nodenumber-1 != i)
64 cout<<
"warning: nodenumber <" <<nodenumber<<
"> does not match its index in node list <"<<i+1
65 <<
">. Node will get number "<<i+1<<
" when naming variables and constraints!"<<endl;
66 node->
x = x_coords[i];
67 node->
y = y_coords[i];
72 assert( i == graph->nnodes );
99 bool ReaderTSP::checkValid(
103 std::string edgeweighttype,
111 cout <<
"parse error in file <" << name <<
"> dimension should be greater than 0"<< endl ;
116 cout <<
"parse error in file <" << name <<
"> type should be TSP" << endl;
119 if ( !( edgeweighttype ==
"EUC_2D" || edgeweighttype ==
"MAX_2D" || edgeweighttype ==
"MAN_2D" 120 || edgeweighttype ==
"GEO" || edgeweighttype ==
"ATT") )
122 cout <<
"parse error in file <" << name
123 <<
"> unknown weight type, should be EUC_2D, MAX_2D, MAN_2D, ATT, or GEO" << endl;
128 cout <<
"error while reading file <" << name <<
">, graph is uninitialized. ";
129 cout <<
"Probably NODE_COORD_SECTION is missing" << endl;
162 double* x_coords =
NULL;
163 double* y_coords =
NULL;
166 double** weights =
NULL;
177 string name =
"MY_OWN_LITTLE_TSP";
180 string edgeweighttype =
"EUC_2D";
186 ifstream filedata(filename);
193 while( !filedata.eof() )
195 if( token ==
"NAME:" )
197 else if( token ==
"NAME" )
198 filedata >> token >> name;
199 else if( token ==
"TYPE:" )
201 else if( token ==
"TYPE" )
202 filedata >> token >> type;
203 else if( token ==
"DIMENSION:" )
206 nedges = nnodes * (nnodes-1);
208 else if( token ==
"DIMENSION" )
210 filedata >> token >>
nnodes;
211 nedges = nnodes * (nnodes-1);
213 else if( token ==
"EDGE_WEIGHT_TYPE:" )
214 filedata >> edgeweighttype;
215 else if( token ==
"EDGE_WEIGHT_TYPE" )
216 filedata >> token >> edgeweighttype;
217 else if( token ==
"NODE_COORD_SECTION" || token ==
"DISPLAY_DATA_SECTION" )
228 assert(x_coords ==
NULL);
229 assert(y_coords ==
NULL);
231 x_coords =
new double[
nnodes];
232 y_coords =
new double[
nnodes];
233 getNodesFromFile(filedata, x_coords, y_coords, graph);
241 else if( token ==
"COMMENT:" || token ==
"COMMENT" ||
242 token ==
"DISPLAY_DATA_TYPE" || token ==
"DISPLAY_DATA_TYPE:" )
243 (void) getline( filedata, token );
244 else if( token ==
"EOF" )
246 else if( token ==
"" )
250 cout <<
"parse error in file <" << name <<
"> unknown keyword <" << token <<
">" << endl;
257 if( !checkValid(graph, name, type, edgeweighttype, nnodes) )
260 assert(graph !=
NULL);
264 edgeforw = &( graph->
edges[0] );
265 edgebackw= &( graph->
edges[nedges/2] );
268 weights =
new double* [
nnodes];
269 for( i = 0; i <
nnodes; ++i )
270 weights[i] =
new double[nnodes];
274 for( i = 0; i <
nnodes; i++ )
276 nodestart = &graph->nodes[i];
277 for( j = i+1; j <
nnodes; j++ )
279 nodeend = &graph->nodes[j];
282 edgeforw->
adjac = nodeend;
283 edgebackw->
adjac = nodestart;
284 edgeforw->
back = edgebackw;
285 edgebackw->
back = edgeforw;
288 x = x_coords[(*nodestart).id] - x_coords[(*nodeend).id];
289 y = y_coords[(*nodestart).id] - y_coords[(*nodeend).id];
290 if( edgeweighttype ==
"EUC_2D")
292 else if( edgeweighttype ==
"MAX_2D")
294 else if( edgeweighttype ==
"MAN_2D")
296 else if( edgeweighttype ==
"ATT")
297 edgeforw->
length = ceil(
sqrt( (x*x+y*y)/10.0 ) );
298 else if( edgeweighttype ==
"GEO")
300 const double pi = 3.141592653589793;
308 coords[0] = x_coords[(*nodestart).id];
309 coords[1] = y_coords[(*nodestart).id];
310 coords[2] = x_coords[(*nodeend).id];
311 coords[3] = y_coords[(*nodeend).id];
313 for( k = 0; k < 4; k++ )
315 degs[k] = coords[k] >= 0 ? floor(coords[k]) : ceil(coords[k]);
316 mins[k] = coords[k] - degs[k];
317 rads[k] = pi*(degs[k]+5.0*mins[k]/3.0)/180.0;
320 euler[0] =
cos(rads[1]-rads[3]);
321 euler[1] =
cos(rads[0]-rads[2]);
322 euler[2] =
cos(rads[0]+rads[2]);
323 edgeforw->
length = floor(6378.388 * acos(0.5*((1.0+euler[0])*euler[1]-(1.0-euler[0])*euler[2]))+1.0);
332 weights[i][j] = edgeforw->
length;
333 weights[j][i] = edgebackw->
length;
372 if( weights !=
NULL )
374 for( i = 0; i <
nnodes; i++ )
386 for( i = 0; i <
nnodes; i++ )
388 for( j = 0; j <
nnodes; j++ )
389 printf(
" %4.0f ",weights[i][j]);
400 for( i = 0; i < nedges/2; i++ )
404 stringstream varname;
405 edge = &graph->
edges[i];
416 SCIP_CALL( addVarToEdges(scip, edge, var) );
429 for( i = 0, node = &(graph->nodes[0]); i < nnodes; i++, node++ )
433 stringstream consname;
434 consname <<
"deg_con_v" << node->
id+1;
442 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.
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)