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-2017 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 email to scip@zib.de. */
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 
40 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
41 SCIP_DECL_HEURFREE(HeurFrats::scip_free)
42 {
43  return SCIP_OKAY;
44 } /*lint !e715*/
45 
46 /** initialization method of primal heuristic (called after problem was transformed) */
47 SCIP_DECL_HEURINIT(HeurFrats::scip_init)
48 {
49  ProbDataTSP* probdata;
50 
51  /* create heuristic data */
52  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
53 
54  /* load the problem specific data */
55  probdata = dynamic_cast<ProbDataTSP*>(SCIPgetObjProbData(scip));
56  assert(probdata != NULL);
57 
58  graph = probdata->getGraph();
59  assert(graph != NULL);
60 
61  capture_graph(graph);
62 
63  return SCIP_OKAY;
64 }
65 
66 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
67 SCIP_DECL_HEUREXIT(HeurFrats::scip_exit)
68 {
69  /* free everything which was created in scip_init */
70  SCIP_CALL( SCIPfreeSol(scip, &sol) );
71  release_graph(&graph);
72 
73  return SCIP_OKAY;
74 } /*lint !e715*/
75 
76 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
77  *
78  * This method is called when the presolving was finished and the branch and bound process is about to begin.
79  * The primal heuristic may use this call to initialize its branch and bound specific data.
80  *
81  */
82 SCIP_DECL_HEURINITSOL(HeurFrats::scip_initsol)
83 {
84  return SCIP_OKAY;
85 } /*lint !e715*/
86 
87 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
88  *
89  * This method is called before the branch and bound process is freed.
90  * The primal heuristic should use this call to clean up its branch and bound data.
91  */
92 SCIP_DECL_HEUREXITSOL(HeurFrats::scip_exitsol)
93 {
94  return SCIP_OKAY;
95 } /*lint !e715*/
96 
97 /** execution method of primal heuristic */
98 SCIP_DECL_HEUREXEC(HeurFrats::scip_exec)
99 { /*lint --e{715}*/
100 
101  SCIP_SOL* newsol;
102  GRAPHNODE* currnode;
103  SCIP_Bool* visited;
104  int nnodes;
105  int i;
106  SCIP_Bool success;
107 
108  assert(result != NULL);
109  /* since the timing is SCIP_HEURTIMING_AFTERLPNODE, the current node should have an LP */
110  assert(SCIPhasCurrentNodeLP(scip));
111 
112  *result = SCIP_DIDNOTRUN;
113 
114  /* only call heuristic, if an optimal LP solution is at hand */
116  return SCIP_OKAY;
117 
118  /* get the working solution from heuristic's local data */
119  assert(sol != NULL);
120 
121  /* copy the current LP solution to the working solution */
122  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
123 
124  *result = SCIP_DIDNOTFIND;
125 
126  /* choose the first node as starting point*/
127  currnode = &graph->nodes[0]; /*lint !e613*/
128  nnodes = graph->nnodes; /*lint !e613*/
129  success = TRUE;
130 
131  /* allocate local memory */
132  SCIP_CALL( SCIPcreateSol (scip, &newsol, heur) );
133  SCIP_CALL( SCIPallocBufferArray(scip, &visited, nnodes) ); /*lint !e530*/
134  BMSclearMemoryArray(visited, nnodes);
135 
136  assert(currnode->id == 0);
137  visited[0] = TRUE;
138 
139  /*exactly nnodes edges have to be inserted into the tour */
140  for( i = 0; i < nnodes; i++ )
141  {
142  GRAPHEDGE* edge;
143  SCIP_Real bestval;
144  GRAPHEDGE* bestedge;
145 
146  /* initialization */
147  bestedge = NULL;
148  bestval = -1;
149 
150  /* the graph works with adjacency lists */
151  edge = currnode->first_edge;
152 
153  /* the last edge is treated separately */
154  if( i != nnodes-1 )
155  {
156  while( edge != NULL )
157  {
158  /* update, if an edge has a better LP value AND was not visited yet AND was not globally fixed to zero */
159  if( SCIPgetSolVal(scip, sol, edge->var) > bestval && !visited[edge->adjac->id]
160  && SCIPvarGetUbGlobal(edge->var) == 1.0 )
161  {
162  bestval = SCIPgetSolVal(scip, sol, edge->var);
163  bestedge = edge;
164  }
165  edge = edge->next;
166  }
167  }
168  else
169  {
170  GRAPHNODE* finalnode;
171  finalnode = &graph->nodes[0]; /*lint !e613*/
172 
173  /* find the last edge which closes the tour */
174  while( edge != NULL )
175  {
176  if( edge->adjac == finalnode )
177  {
178  if( SCIPvarGetUbGlobal(edge->var) == 1.0 )
179  {
180  bestval = SCIPgetSolVal(scip, sol, edge->var);
181  bestedge = edge;
182  }
183  break;
184  }
185  edge = edge->next;
186  }
187  }
188 
189  /* it may happen that we were not able to build a complete tour */
190  if( bestval == -1 )
191  {
192  success = FALSE;
193  break;
194  }
195  /* assert that the data is not corrupted */
196  assert(bestedge != NULL);
197  assert(SCIPisFeasLE(scip, 0.0, bestval) && SCIPisFeasLE(scip, bestval, 1.0));
198  assert(bestval == SCIPgetSolVal(scip, sol, bestedge->var)); /*lint !e777*/
199 
200  /* fix the variable which represents the best edge to one in the new solution and proceed to next node */
201  SCIP_CALL( SCIPsetSolVal(scip, newsol, bestedge->var, 1.0) );
202  currnode = bestedge->adjac;
203  assert(currnode != NULL);
204  assert(0 <= currnode->id && currnode->id <= nnodes-1);
205  if( i != nnodes-1 )
206  assert(!visited[currnode->id]);
207  visited[currnode->id] = TRUE;
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  /* due to construction we already know, that the solution will be feasible */
217  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
218  if( success )
219  *result = SCIP_FOUNDSOL;
220  }
221  /* free all local memory */
222  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
223  SCIPfreeBufferArray(scip, &visited);
224 
225  return SCIP_OKAY;
226 }
227 
228 /** clone method which will be used to copy a objective plugin */
229 SCIP_DECL_HEURCLONE(scip::ObjCloneable* HeurFrats::clone) /*lint !e665*/
230 {
231  return new HeurFrats(scip);
232 }
struct GraphEdge * next
Definition: GomoryHuTree.h:59
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
SCIP_DECL_HEURINITSOL(HeurFrats::scip_initsol)
Definition: HeurFrats.cpp:82
SCIP_DECL_HEUREXEC(HeurFrats::scip_exec)
Definition: HeurFrats.cpp:98
#define FALSE
Definition: def.h:64
#define TRUE
Definition: def.h:63
SCIP_DECL_HEURINIT(HeurFrats::scip_init)
Definition: HeurFrats.cpp:47
SCIP_DECL_HEURCLONE(scip::ObjCloneable *HeurFrats::clone)
Definition: HeurFrats.cpp:229
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_VAR * var
Definition: GomoryHuTree.h:64
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
GRAPHNODE * adjac
Definition: GomoryHuTree.h:62
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:43
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
GRAPH * getGraph()
Definition: ProbDataTSP.h:111
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
C++ problem data for TSP.
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:37867
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
SCIP_DECL_HEUREXITSOL(HeurFrats::scip_exitsol)
Definition: HeurFrats.cpp:92
SCIP_DECL_HEURFREE(HeurFrats::scip_free)
Definition: HeurFrats.cpp:41
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
fractional travelling salesman heuristic - Rounding heuristic for TSP
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.c:39749
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
SCIP_DECL_HEUREXIT(HeurFrats::scip_exit)
Definition: HeurFrats.cpp:67
Definition of base class for all clonable classes.
Definition: objcloneable.h:38
#define SCIP_Real
Definition: def.h:135
void capture_graph(GRAPH *gr)
void release_graph(GRAPH **gr)
#define nnodes
Definition: gastrans.c:65
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005