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