Scippy

SCIP

Solving Constraint Integer Programs

HeurFrats.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file HeurFrats.cpp
17  * @brief fractional travelling salesman heuristic - Rounding heuristic for TSP
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "HeurFrats.h"
24 #include "ProbDataTSP.h"
25 
26 using namespace tsp;
27 using namespace std;
28 
29 
30 /*
31  * Local methods
32  */
33 
34 
35 /*
36  * Callback methods of primal heuristic
37  */
38 
39 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
40 SCIP_DECL_HEURFREE(HeurFrats::scip_free)
41 { /*lint --e{715}*/
42  return SCIP_OKAY;
43 }
44 
45 /** initialization method of primal heuristic (called after problem was transformed) */
46 SCIP_DECL_HEURINIT(HeurFrats::scip_init)
47 {
48  ProbDataTSP* probdata;
49 
50  /* create heuristic data */
51  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
52 
53  /* load the problem specific data */
54  probdata = dynamic_cast<ProbDataTSP*>(SCIPgetObjProbData(scip));
55  assert(probdata != NULL);
56 
57  graph = probdata->getGraph();
58  assert(graph != NULL);
59 
60  capture_graph(graph);
61 
62  return SCIP_OKAY;
63 }
64 
65 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
66 SCIP_DECL_HEUREXIT(HeurFrats::scip_exit)
67 { /*lint --e{715}*/
68  /* free everything which was created in scip_init */
69  SCIP_CALL( SCIPfreeSol(scip, &sol) );
70  release_graph(&graph);
71 
72  return SCIP_OKAY;
73 }
74 
75 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
76  *
77  * This method is called when the presolving was finished and the branch and bound process is about to begin.
78  * The primal heuristic may use this call to initialize its branch and bound specific data.
79  *
80  */
81 SCIP_DECL_HEURINITSOL(HeurFrats::scip_initsol)
82 { /*lint --e{715}*/
83  return SCIP_OKAY;
84 }
85 
86 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
87  *
88  * This method is called before the branch and bound process is freed.
89  * The primal heuristic should use this call to clean up its branch and bound data.
90  */
91 SCIP_DECL_HEUREXITSOL(HeurFrats::scip_exitsol)
92 { /*lint --e{715}*/
93  return SCIP_OKAY;
94 }
95 
96 /** execution method of primal heuristic */
97 SCIP_DECL_HEUREXEC(HeurFrats::scip_exec)
98 { /*lint --e{715}*/
99  SCIP_SOL* newsol;
100  GRAPHNODE* currnode;
101  SCIP_Bool* visited;
102  SCIP_Bool success;
103  int nnodes;
104  int i;
105 
106  assert(result != NULL);
107  /* since the timing is SCIP_HEURTIMING_AFTERLPNODE, the current node should have an LP */
108  assert(SCIPhasCurrentNodeLP(scip));
109 
110  *result = SCIP_DIDNOTRUN;
111 
112  /* only call heuristic, if an optimal LP solution is at hand */
114  return SCIP_OKAY;
115 
116  /* get the working solution from heuristic's local data */
117  assert(sol != NULL);
118 
119  /* copy the current LP solution to the working solution */
120  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
121 
122  *result = SCIP_DIDNOTFIND;
123 
124  /* choose the first node as starting point*/
125  currnode = &graph->nodes[0]; /*lint !e613*/
126  nnodes = graph->nnodes; /*lint !e613*/
127  success = TRUE;
128 
129  /* allocate local memory */
130  SCIP_CALL( SCIPcreateSol (scip, &newsol, heur) );
131  SCIP_CALL( SCIPallocBufferArray(scip, &visited, nnodes) ); /*lint !e530*/
132  BMSclearMemoryArray(visited, nnodes);
133 
134  assert(currnode->id == 0);
135  visited[0] = TRUE;
136 
137  /*exactly nnodes edges have to be inserted into the tour */
138  for( i = 0; i < nnodes; i++ )
139  {
140  GRAPHEDGE* edge;
141  SCIP_Real bestval;
142  GRAPHEDGE* bestedge;
143 
144  /* initialization */
145  bestedge = NULL;
146  bestval = -1;
147 
148  /* the graph works with adjacency lists */
149  edge = currnode->first_edge;
150 
151  /* the last edge is treated separately */
152  if( i != nnodes-1 )
153  {
154  while( edge != NULL )
155  {
156  /* update, if an edge has a better LP value AND was not visited yet AND was not globally fixed to zero */
157  if( SCIPgetSolVal(scip, sol, edge->var) > bestval && !visited[edge->adjac->id]
158  && SCIPvarGetUbGlobal(edge->var) == 1.0 )
159  {
160  bestval = SCIPgetSolVal(scip, sol, edge->var);
161  bestedge = edge;
162  }
163  edge = edge->next;
164  }
165  }
166  else
167  {
168  GRAPHNODE* finalnode;
169  finalnode = &graph->nodes[0]; /*lint !e613*/
170 
171  /* find the last edge which closes the tour */
172  while( edge != NULL )
173  {
174  if( edge->adjac == finalnode )
175  {
176  if( SCIPvarGetUbGlobal(edge->var) == 1.0 )
177  {
178  bestval = SCIPgetSolVal(scip, sol, edge->var);
179  bestedge = edge;
180  }
181  break;
182  }
183  edge = edge->next;
184  }
185  }
186 
187  /* it may happen that we were not able to build a complete tour */
188  if( bestval == -1 )
189  {
190  success = FALSE;
191  break;
192  }
193 
194  /* assert that the data is not corrupted */
195  assert(bestedge != NULL);
196  assert(SCIPisFeasLE(scip, 0.0, bestval) && SCIPisFeasLE(scip, bestval, 1.0));
197  assert(bestval == SCIPgetSolVal(scip, sol, bestedge->var)); /*lint !e777*/
198 
199  /* fix the variable which represents the best edge to one in the new solution and proceed to next node */
200  SCIP_CALL( SCIPsetSolVal(scip, newsol, bestedge->var, 1.0) );
201  currnode = bestedge->adjac;
202  assert(currnode != NULL);
203  assert(0 <= currnode->id && currnode->id <= nnodes-1);
204  if( i != nnodes-1 )
205  assert(!visited[currnode->id]);
206  visited[currnode->id] = TRUE;
207  }
208 
209  /* if we were able to construct a complete tour, try to add the solution to SCIP */
210  if( success )
211  {
212  for( i = 0; i < nnodes; i++ )
213  assert(visited[graph->nodes[i].id]); /*lint !e613*/
214 
215  success = FALSE;
216 
217  /* due to construction we already know, that the solution will be feasible */
218  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
219  if( success )
220  *result = SCIP_FOUNDSOL;
221  }
222  /* free all local memory */
223  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
224  SCIPfreeBufferArray(scip, &visited);
225 
226  return SCIP_OKAY;
227 }
228 
229 /** clone method which will be used to copy a objective plugin */
230 SCIP_DECL_HEURCLONE(scip::ObjCloneable* HeurFrats::clone) /*lint !e665*/
231 {
232  return new HeurFrats(scip);
233 }
struct GraphEdge * next
Definition: GomoryHuTree.h:60
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
SCIP_DECL_HEURINITSOL(HeurFrats::scip_initsol)
Definition: HeurFrats.cpp:81
SCIP_DECL_HEUREXEC(HeurFrats::scip_exec)
Definition: HeurFrats.cpp:97
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1018
SCIP_DECL_HEURINIT(HeurFrats::scip_init)
Definition: HeurFrats.cpp:46
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_DECL_HEURCLONE(scip::ObjCloneable *HeurFrats::clone)
Definition: HeurFrats.cpp:230
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
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)
Definition: scip_sol.c:3125
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
SCIP_VAR * var
Definition: GomoryHuTree.h:65
Definition: pqueue.h:28
GRAPHNODE * adjac
Definition: GomoryHuTree.h:63
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:44
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
GRAPH * getGraph()
Definition: ProbDataTSP.h:88
C++ problem data for TSP.
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIP_Bool
Definition: def.h:70
SCIP_DECL_HEUREXITSOL(HeurFrats::scip_exitsol)
Definition: HeurFrats.cpp:91
SCIP_DECL_HEURFREE(HeurFrats::scip_free)
Definition: HeurFrats.cpp:40
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
fractional travelling salesman heuristic - Rounding heuristic for TSP
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
SCIP_DECL_HEUREXIT(HeurFrats::scip_exit)
Definition: HeurFrats.cpp:66
Definition of base class for all clonable classes.
Definition: objcloneable.h:38
#define SCIP_Real
Definition: def.h:163
void capture_graph(GRAPH *gr)
void release_graph(GRAPH **gr)
#define nnodes
Definition: gastrans.c:65
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122