144 int nnodes = graph_->nnodes;
145 int nedges = graph_->nedges;
148 for(
int e = 0; e < nedges; ++e)
153 hasFixedEdges =
TRUE;
159 if(
nnodes < 3 || hasFixedEdges )
192 for(
int u = 0; u <
nnodes - 2 && !foundThreeCircle; ++u)
194 for(
int v = u + 1; v <
nnodes - 1 && !foundThreeCircle; ++v)
201 for(
int w = v + 1; (
w <
nnodes) && !foundThreeCircle; ++
w)
212 foundThreeCircle =
TRUE;
231 if( !foundThreeCircle )
244 int subtourlength = 3;
245 for(; subtourlength <
nnodes; subtourlength++ )
252 if( (maxmin < dist[
i] && dist[
i] != DBL_MAX) || (maxmin == dist[
i] && !subtour[
i]) )
258 if(newnodeindex == -1)
260 couldNotInsert =
TRUE;
269 while( edge !=
NULL )
283 startnode = edge->
adjac;
289 edges[1] = successor[node->
id];
290 edges[2] =
findEdge(nodes, edges[1]->adjac->id, newnodeindex);
299 for(
i = 0;
i < 3;
i++ )
300 bestedges[
i] = edges[
i];
302 node = edges[1]->
adjac;
303 edges[0] = edges[2]->
back;
305 while( node != startnode);
307 if( minval == DBL_MAX )
309 couldNotInsert =
TRUE;
318 assert(subtour[bestedges[0]->adjac->id]);
319 assert(subtour[bestedges[1]->adjac->id]);
320 assert(bestedges[2]->adjac->id == newnodeindex);
321 assert(!subtour[newnodeindex]);
324 successor[bestedges[0]->
adjac->
id] = bestedges[0]->
back;
325 successor[bestedges[2]->adjac->id] = bestedges[2]->
back;
326 dist[newnodeindex] = 0.0;
327 subtour[newnodeindex] =
true;
void capture_graph(GRAPH *gr)
void release_graph(GRAPH **gr)
generator for global cuts in undirected graphs
struct GraphNode GRAPHNODE
struct GraphEdge GRAPHEDGE
static GRAPHEDGE * findEdge(GRAPHNODE *nodes, int index1, int index2)
static void updateDistances(GRAPHNODE *nodes, double *dist, int idx)
farthest insert - combinatorial heuristic for TSP
C++ problem data for TSP.
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemoryArray(ptr, num)
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
C++ wrapper classes for SCIP.
struct GraphEdge * first_edge
Definition of base class for all clonable classes.
#define SCIP_DECL_HEURINITSOL(x)
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
#define SCIP_DECL_HEURCLONE(x)