Scippy

SCIP

Solving Constraint Integer Programs

HeurFarthestInsert.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 2002-2022 Zuse Institute Berlin */
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 HeurFarthestInsert.cpp
26  * @brief farthest insert - combinatorial heuristic for TSP
27  * @author Timo Berthold
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 
33 #include <iostream>
34 #include <cassert>
35 
36 #include "objscip/objscip.h"
37 #include "GomoryHuTree.h"
38 #include "HeurFarthestInsert.h"
39 #include "ProbDataTSP.h"
40 
41 using namespace tsp;
42 using namespace std;
43 
44 /** method finding the edge going from the node with id index1 to the node with id index2 */
45 static
47  GRAPHNODE* nodes, /**< all nodes of the graph */
48  int index1, /**< id of the node where the searched edge starts */
49  int index2 /**< id of the node where the searched edge ends */
50  )
51 {
52  GRAPHEDGE* edge = nodes[index1].first_edge;
53 
54  // regard every outgoing edge of node index1 and stop if adjacent to node index2
55  while( edge != NULL )
56  {
57  if( edge->adjac->id == index2 )
58  break;
59  edge = edge->next;
60  }
61 
62  return edge;
63 }
64 
65 
66 /** method updating the distances of the nodes to the tour after having inserted one node with id index */
67 static
69  GRAPHNODE* nodes, /**< all nodes of the graph */
70  double* dist, /**< array with current distances of all nodes to the subtour */
71  int idx /**< id of the inserted node */
72  )
73 {
74  GRAPHEDGE* edge = nodes[idx].first_edge;
75 
76  /* Regard all outgoing edges of the node and update, if the length and therefore the distance of the adjacent is
77  * smaller and the edge is not fixed to 0. */
78  while( edge != NULL )
79  {
80  if( dist[edge->adjac->id] > edge->length && SCIPvarGetUbGlobal(edge->var) != 0.0 )
81  dist[edge->adjac->id] = edge->length;
82  edge = edge->next;
83  }
84 }
85 
86 
87 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
88 SCIP_DECL_HEURFREE(HeurFarthestInsert::scip_free)
89 { /*lint --e{715}*/
90  return SCIP_OKAY;
91 }
92 
93 /** initialization method of primal heuristic (called after problem was transformed) */
94 SCIP_DECL_HEURINIT(HeurFarthestInsert::scip_init)
95 { /*lint --e{715}*/
96  ProbDataTSP* probdata = dynamic_cast<ProbDataTSP*>(SCIPgetObjProbData(scip));
97  graph_ = probdata->getGraph(); /*lint !e613*/
98  capture_graph(graph_);
99  return SCIP_OKAY;
100 }
101 
102 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
103 SCIP_DECL_HEUREXIT(HeurFarthestInsert::scip_exit)
104 { /*lint --e{715}*/
105  release_graph(&graph_);
106 
107  return SCIP_OKAY;
108 }
109 
110 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
111  *
112  * This method is called when the presolving was finished and the branch and bound process is about to begin.
113  * The primal heuristic may use this call to initialize its branch and bound specific data.
114  *
115  */
116 SCIP_DECL_HEURINITSOL(HeurFarthestInsert::scip_initsol)
117 { /*lint --e{715}*/
118  return SCIP_OKAY;
119 }
120 
121 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
122  *
123  * This method is called before the branch and bound process is freed.
124  * The primal heuristic should use this call to clean up its branch and bound data.
125  */
126 SCIP_DECL_HEUREXITSOL(HeurFarthestInsert::scip_exitsol)
127 { /*lint --e{715}*/
128  return SCIP_OKAY;
129 }
130 
131 /** execution method of primal heuristic
132  *
133  * Searches for feasible primal solutions. The method is called in the node processing loop.
134  *
135  * possible return values for *result:
136  * - SCIP_FOUNDSOL : at least one feasible primal solution was found
137  * - SCIP_DIDNOTFIND : the heuristic searched, but did not find a feasible solution
138  * - SCIP_DIDNOTRUN : the heuristic was skipped
139  * - SCIP_DELAYED : the heuristic was skipped, but should be called again as soon as possible, disregarding
140  * its frequency
141  */
142 SCIP_DECL_HEUREXEC(HeurFarthestInsert::scip_exec)
143 { /*lint --e{715}*/
144  int nnodes = graph_->nnodes; /*lint !e613*/
145  int nedges = graph_->nedges; /*lint !e613*/
146 
147  SCIP_Bool hasFixedEdges = FALSE;
148  for(int e = 0; e < nedges; ++e)
149  {
150  GRAPHEDGE* edge = &(graph_->edges[e]); /*lint !e613*/
151  if( SCIPvarGetLbGlobal(edge->var) == 1.0 )
152  {
153  hasFixedEdges = TRUE;
154  break;
155  }
156  }
157 
158  // no longer need "SCIPgetNRuns(scip) > 1" since we now respect fixed variables after restart
159  if( nnodes < 3 || hasFixedEdges )
160  *result = SCIP_DIDNOTRUN;
161  else
162  {
163  bool* subtour;
164  int i;
165  double* dist;
166 
167  GRAPHNODE* startnode;
168  GRAPHNODE* node;
169  GRAPHEDGE* edge;
170 
171  GRAPHEDGE** bestedges; // will contain the best insertion of a given node into a subtour
172  GRAPHEDGE** edges; // will contain some insertion of a given node into a subtour
173  GRAPHEDGE** successor; // stores the successor of a node in the current subtour
174  GRAPHNODE* nodes = graph_->nodes; /*lint !e613*/
175 
176  for( i = 0; i < nnodes; i++ )
177  assert( i == nodes[i].id );
178 
179  // memory allocation
180  SCIP_CALL( SCIPallocBufferArray(scip, &subtour, nnodes) ); /*lint !e530*/
181  SCIP_CALL( SCIPallocBufferArray(scip, &dist, nnodes) ); /*lint !e530*/
182  SCIP_CALL( SCIPallocBufferArray(scip, &successor, nnodes) ); /*lint !e530*/
183  SCIP_CALL( SCIPallocBufferArray(scip, &edges, 3) ); /*lint !e530*/
184  SCIP_CALL( SCIPallocBufferArray(scip, &bestedges, 3) ); /*lint !e530*/
185 
186  BMSclearMemoryArray(subtour, nnodes);
187  for( i = 0; i < nnodes; i++ )
188  dist[i] = DBL_MAX;
189 
190  // building up a 3-circle, only using edges not fixed to 0
191  SCIP_Bool foundThreeCircle = FALSE;
192  for(int u = 0; u < nnodes - 2 && !foundThreeCircle; ++u)
193  {
194  for(int v = u + 1; v < nnodes - 1 && !foundThreeCircle; ++v)
195  {
196  GRAPHEDGE * uv = findEdge(nodes, u, v);
197  assert(uv != NULL);
198  if( SCIPvarGetUbGlobal(uv->var) == 0.0 )
199  continue;
200 
201  for(int w = v + 1; (w < nnodes) && !foundThreeCircle; ++w) /*lint !e845*/
202  {
203  GRAPHEDGE * vw = findEdge(nodes, v, w);
204  assert(vw != NULL);
205  GRAPHEDGE * wu = findEdge(nodes, w, u);
206  assert(wu != NULL);
207 
208  if( SCIPvarGetUbGlobal(vw->var) == 0.0 || SCIPvarGetUbGlobal(wu->var) == 0.0 )
209  continue;
210  else
211  {
212  foundThreeCircle = TRUE;
213 
214  subtour[u] = true;
215  dist[u] = 0.0;
216  updateDistances(nodes, dist, u);
217  subtour[v] = true;
218  dist[v] = 0.0;
219  updateDistances(nodes, dist, v);
220  subtour[w] = true;
221  dist[w] = 0.0;
222  updateDistances(nodes, dist, w);
223  successor[u] = uv;
224  successor[v] = vw;
225  successor[w] = wu;
226  } // foundThreeCircle with no fixed variables
227  } // for w
228  } // for v
229  } // for u
230 
231  if( !foundThreeCircle )
232  {
233  *result = SCIP_DIDNOTFIND;
234  }
235  else
236  {
237  double maxmin;
238  double minval;
239  int newnodeindex;
240 
241  SCIP_Bool couldNotInsert = FALSE;
242 
243  // widen the subtour by one node each step until you have a complete tour, actually the farthest insert heuritic
244  int subtourlength = 3;
245  for(; subtourlength < nnodes; subtourlength++ )
246  {
247  // find the node with the maximal distance to the tour
248  maxmin = 0.0;
249  newnodeindex = -1;
250  for( i = 0; i < nnodes; i++)
251  {
252  if( (maxmin < dist[i] && dist[i] != DBL_MAX) || (maxmin == dist[i] && !subtour[i]) ) /*lint !e777*/
253  {
254  maxmin = dist[i];
255  newnodeindex = i;
256  }
257  }
258  if(newnodeindex == -1)
259  {
260  couldNotInsert = TRUE;
261  break;
262  }
263 
264  // find connection to one node in the tour
265  BMSclearMemoryArray(bestedges, 3);
266  edge = nodes[newnodeindex].first_edge;
267  startnode = NULL;
268 
269  while( edge != NULL )
270  {
271  if( subtour[edge->adjac->id] && SCIPvarGetUbGlobal(edge->var) != 0.0 )
272  break;
273  edge = edge->next;
274  }
275 
276  assert(edge != NULL);
277  assert(subtour[edge->adjac->id]);
278 
279  /* find best insertion of the new node by trying to replace any edge connecting by the two edges connecting
280  * its end node with the new node */
281  minval = DBL_MAX;
282  edges[0] = edge;
283  startnode = edge->adjac;
284  node = startnode;
285 
286  // succeed to the next edge in the subtour
287  do
288  {
289  edges[1] = successor[node->id];
290  edges[2] = findEdge(nodes, edges[1]->adjac->id, newnodeindex);
291  assert( edges[2] != NULL );
292 
293  // check, whether you have found a better (feasible) insertion
294  if( edges[0]->back->length - edges[1]->length + edges[2]->back->length < minval
295  && SCIPvarGetUbGlobal(edges[0]->var) != 0.0
296  && SCIPvarGetUbGlobal(edges[2]->var) != 0.0 )
297  {
298  minval = edges[0]->back->length - edges[1]->length + edges[2]->back->length;
299  for( i = 0; i < 3; i++ )
300  bestedges[i] = edges[i];
301  }
302  node = edges[1]->adjac;
303  edges[0] = edges[2]->back;
304  }
305  while( node != startnode);
306 
307  if( minval == DBL_MAX ) /*lint !e777*/
308  {
309  couldNotInsert = TRUE;
310  break;
311  }
312  else
313  {
314  // bestedges should contain a 3-cycle (modulo orientation) connecting new node with two incident ones of the tour
315  assert(bestedges[0]->adjac->id == bestedges[1]->back->adjac->id);
316  assert(bestedges[1]->adjac->id == bestedges[2]->back->adjac->id);
317  assert(bestedges[2]->adjac->id == bestedges[0]->back->adjac->id);
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]);
322 
323  // now officially insert the new node into the tour
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;
328  updateDistances(nodes, dist, newnodeindex);
329  } // minval < DBL_MAX
330  } // for subtourlength
331 
332  if(couldNotInsert)
333  {
334  *result = SCIP_DIDNOTFIND;
335  }
336  else
337  {
338  SCIP_SOL* sol;
339  SCIP_Bool success;
340 
341  // now create a solution out of the edges stored in successor and try to add it to SCIP
342  SCIP_CALL( SCIPcreateSol (scip, &sol, heur) );
343  for( i = 0; i < nnodes; i++ )
344  {
345  SCIP_CALL( SCIPsetSolVal(scip, sol, successor[i]->var, 1.0) );
346  }
347 
348  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
349 
350  if( success )
351  *result = SCIP_FOUNDSOL;
352  else
353  *result = SCIP_DIDNOTFIND;
354 
355  SCIP_CALL( SCIPfreeSol(scip, &sol) );
356  } // couldNotInsert == FALSE
357  } // foundThreeCircle == TRUE
358 
359  // free all local memory
360  SCIPfreeBufferArray(scip, &bestedges);
361  SCIPfreeBufferArray(scip, &edges);
362  SCIPfreeBufferArray(scip, &successor);
363  SCIPfreeBufferArray(scip, &dist);
364  SCIPfreeBufferArray(scip, &subtour);
365  }
366 
367  return SCIP_OKAY;
368 }
369 
370 /** clone method which will be used to copy a objective plugin */
371 SCIP_DECL_HEURCLONE(scip::ObjCloneable* HeurFarthestInsert::clone) /*lint !e665*/
372 {
373  return new HeurFarthestInsert(scip);
374 }
struct GraphEdge * next
Definition: GomoryHuTree.h:69
double length
Definition: GomoryHuTree.h:67
SCIP_DECL_HEURFREE(HeurFarthestInsert::scip_free)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17919
#define FALSE
Definition: def.h:96
#define TRUE
Definition: def.h:95
SCIP_DECL_HEUREXITSOL(HeurFarthestInsert::scip_exitsol)
generator for global cuts in undirected graphs
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
farthest insert - combinatorial heuristic for TSP
SCIP_VAR * var
Definition: GomoryHuTree.h:74
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17929
SCIP_VAR * w
Definition: circlepacking.c:67
Definition: pqueue.h:37
GRAPHNODE * adjac
Definition: GomoryHuTree.h:72
struct GraphEdge * back
Definition: GomoryHuTree.h:70
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:53
#define NULL
Definition: lpi_spx1.cpp:164
C++ wrapper classes for SCIP.
#define SCIP_CALL(x)
Definition: def.h:393
GRAPH * getGraph()
Definition: ProbDataTSP.h:97
C++ problem data for TSP.
static void updateDistances(GRAPHNODE *nodes, double *dist, int idx)
#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_DECL_HEURCLONE(scip::ObjCloneable *HeurFarthestInsert::clone)
static GRAPHEDGE * findEdge(GRAPHNODE *nodes, int index1, int index2)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:985
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:3134
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
SCIP_DECL_HEURINIT(HeurFarthestInsert::scip_init)
SCIP_DECL_HEUREXEC(HeurFarthestInsert::scip_exec)
SCIP_DECL_HEURINITSOL(HeurFarthestInsert::scip_initsol)
Definition of base class for all clonable classes.
Definition: objcloneable.h:47
SCIP_DECL_HEUREXIT(HeurFarthestInsert::scip_exit)
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_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:328