Scippy

SCIP

Solving Constraint Integer Programs

Heur2opt.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 Heur2opt.cpp
17  * @brief 2-Optimum - combinatorial improvement 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 <cassert>
24 #include <iostream>
25 
26 #include "objscip/objscip.h"
27 #include "GomoryHuTree.h"
28 #include "Heur2opt.h"
29 #include "ProbDataTSP.h"
30 
31 using namespace tsp;
32 using namespace std;
33 
34 
35 /** method finding the edge going from the node with id index1 to the node with id index2 */
36 static
38  GRAPHNODE* nodes, /**< all nodes of the graph */
39  GRAPHNODE* node1, /**< id of the node where the searched edge starts */
40  GRAPHNODE* node2 /**< id of the node where the searched edge ends */
41  )
42 { /*lint --e{715}*/
43  GRAPHEDGE* edge = node1->first_edge;
44 
45  // regard every outgoing edge of node index1 and stop if adjacent to node index2
46  while( edge != NULL )
47  {
48  if( edge->adjac == node2 )
49  break;
50  edge = edge->next;
51  }
52  return edge;
53 }
54 
55 
56 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
57 SCIP_DECL_HEURFREE(Heur2opt::scip_free)
58 { /*lint --e{715}*/
59  return SCIP_OKAY;
60 }
61 
62 
63 /** initialization method of primal heuristic (called after problem was transformed) */
64 SCIP_DECL_HEURINIT(Heur2opt::scip_init)
65 { /*lint --e{715}*/
66  return SCIP_OKAY;
67 }
68 
69 
70 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
71 SCIP_DECL_HEUREXIT(Heur2opt::scip_exit)
72 { /*lint --e{715}*/
73  return SCIP_OKAY;
74 }
75 
76 
77 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
78  *
79  * This method is called when the presolving was finished and the branch and bound process is about to begin.
80  * The primal heuristic may use this call to initialize its branch and bound specific data.
81  *
82  */
83 SCIP_DECL_HEURINITSOL(Heur2opt::scip_initsol)
84 { /*lint --e{715}*/
85  ProbDataTSP* probdata = dynamic_cast<ProbDataTSP*>(SCIPgetObjProbData(scip));
86  graph_ = probdata->getGraph(); /*lint !e613*/
87  capture_graph(graph_);
88 
89  ncalls_ = 0;
90  sol_ = NULL;
91  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &tour_, graph_->nnodes) );
92 
93  return SCIP_OKAY;
94 }
95 
96 
97 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
98  *
99  * This method is called before the branch and bound process is freed.
100  * The primal heuristic should use this call to clean up its branch and bound data.
101  */
102 SCIP_DECL_HEUREXITSOL(Heur2opt::scip_exitsol)
103 { /*lint --e{715}*/
104  assert( graph_ != 0 );
105  assert( tour_ != 0 );
106 
107  SCIPfreeBlockMemoryArray(scip, &tour_, graph_->nnodes);
108  release_graph(&graph_);
109 
110  return SCIP_OKAY;
111 }
112 
113 
114 /** execution method of primal heuristic 2-Opt */
115 SCIP_DECL_HEUREXEC(Heur2opt::scip_exec)
116 { /*lint --e{715}*/
117  assert( scip != NULL );
118  assert( result != NULL );
119  assert( heur != NULL );
120 
121  SCIP_SOL* sol = SCIPgetBestSol(scip);
122  bool newsol;
123 
124  // check whether a new solution was found meanwhile
125  if( sol != sol_ )
126  {
127  sol_ = sol;
128  ncalls_ = 0;
129  newsol = true;
130  }
131  else
132  newsol = false;
133 
134  ++ncalls_;
135 
136  int nnodes = graph_->nnodes; /*lint !e613*/
137 
138  // some cases need not to be handled
139  if( nnodes < 4 || sol == NULL || ncalls_ >= nnodes )
140  {
141  *result = SCIP_DIDNOTRUN;
142  return SCIP_OKAY;
143  }
144 
145  *result= SCIP_DIDNOTFIND;
146 
147  GRAPHNODE* nodes = graph_->nodes; /*lint !e613*/
148 
149  // get tour from sol and sort edges by length, if new solution was found
150  if( newsol )
151  {
152  GRAPHEDGE* edge;
153  GRAPHEDGE* lastedge = NULL;
154  GRAPHNODE* node = &nodes[0];
155  int i = 0;
156 
157  do
158  {
159  edge = node->first_edge;
160  while( edge != NULL )
161  {
162  // find the next edge of the tour
163  if( edge->back != lastedge && SCIPgetSolVal(scip, sol, edge->var) > 0.5 )
164  {
165  node = edge->adjac;
166  lastedge = edge;
167 
168  int j;
169  // shift edge through the (sorted) array
170  for(j = i; j > 0 && tour_[j-1]->length < edge->length; j-- ) /*lint !e613*/
171  tour_[j] = tour_[j-1]; /*lint !e613*/
172 
173  // and insert the edge at the right position
174  tour_[j] = edge; /*lint !e613*/
175 
176  i++;
177  break;
178  }
179  edge = edge->next;
180  }
181  }
182  while ( node != &nodes[0] );
183  assert( i == nnodes );
184  }
185 
186  GRAPHEDGE** edges2test = NULL;
187  SCIP_CALL( SCIPallocBufferArray(scip, &edges2test, 4) );
188 
189  /* test current edge with all 'longer' edges for improvement if swapping with crossing edges (though do 2Opt for one edge) */
190  for( int i = 0; i < ncalls_ && *result != SCIP_FOUNDSOL; i++ )
191  {
192  edges2test[0] = tour_[ncalls_]; /*lint !e613*/
193  edges2test[1] = tour_[i]; /*lint !e613*/
194  edges2test[2] = findEdge( nodes, edges2test[0]->back->adjac, edges2test[1]->back->adjac );
195  edges2test[3] = findEdge( nodes, edges2test[0]->adjac, edges2test[1]->adjac );
196  assert( edges2test[2] != NULL );
197  assert( edges2test[3] != NULL );
198 
199  // if the new solution is better and variables are not fixed, update and end
200  if( edges2test[0]->length + edges2test[1]->length > edges2test[2]->length + edges2test[3]->length
201  && SCIPvarGetLbGlobal(edges2test[0]->var) < 0.5
202  && SCIPvarGetLbGlobal(edges2test[1]->var) < 0.5
203  && SCIPvarGetUbGlobal(edges2test[2]->var) > 0.5
204  && SCIPvarGetUbGlobal(edges2test[3]->var) > 0.5 )
205  {
206  SCIP_Bool success;
207  SCIP_SOL* swapsol; // copy of sol with 4 edges swapped
208 
209  SCIP_CALL( SCIPcreateSol(scip, &swapsol, heur) );
210 
211  // copy the old solution
212  for( int j = 0; j < nnodes; j++)
213  {
214  SCIP_CALL( SCIPsetSolVal(scip, swapsol, tour_[j]->var, 1.0) ); /*lint !e613*/
215  }
216 
217  // and replace two edges
218  SCIP_CALL( SCIPsetSolVal(scip, swapsol, edges2test[0]->var, 0.0) );
219  SCIP_CALL( SCIPsetSolVal(scip, swapsol, edges2test[1]->var, 0.0) );
220  SCIP_CALL( SCIPsetSolVal(scip, swapsol, edges2test[2]->var, 1.0) );
221  SCIP_CALL( SCIPsetSolVal(scip, swapsol, edges2test[3]->var, 1.0) );
222  SCIP_CALL( SCIPaddSolFree(scip, &swapsol, &success) );
223 
224  assert(success);
225  *result = SCIP_FOUNDSOL;
226  ncalls_ = 0;
227  }
228  }
229  SCIPfreeBufferArray(scip, &edges2test);
230 
231  return SCIP_OKAY;
232 }
233 
234 
235 /** clone method which will be used to copy a objective plugin */
236 SCIP_DECL_HEURCLONE(scip::ObjCloneable* Heur2opt::clone) /*lint !e665*/
237 {
238  return new Heur2opt(scip);
239 }
struct GraphEdge * next
Definition: GomoryHuTree.h:60
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
double length
Definition: GomoryHuTree.h:58
2-Optimum - combinatorial improvement heuristic for TSP
SCIP_DECL_HEUREXITSOL(Heur2opt::scip_exitsol)
Definition: Heur2opt.cpp:102
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIP_DECL_HEURINIT(Heur2opt::scip_init)
Definition: Heur2opt.cpp:64
generator for global cuts in undirected graphs
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_DECL_HEURFREE(Heur2opt::scip_free)
Definition: Heur2opt.cpp:57
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
SCIP_VAR * var
Definition: GomoryHuTree.h:65
SCIP_DECL_HEUREXEC(Heur2opt::scip_exec)
Definition: Heur2opt.cpp:115
Definition: pqueue.h:28
GRAPHNODE * adjac
Definition: GomoryHuTree.h:63
struct GraphEdge * back
Definition: GomoryHuTree.h:61
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:44
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_DECL_HEUREXIT(Heur2opt::scip_exit)
Definition: Heur2opt.cpp:71
C++ wrapper classes for SCIP.
static GRAPHEDGE * findEdge(GRAPHNODE *nodes, GRAPHNODE *node1, GRAPHNODE *node2)
Definition: Heur2opt.cpp:37
#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_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:3015
SCIP_DECL_HEURINITSOL(Heur2opt::scip_initsol)
Definition: Heur2opt.cpp:83
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
SCIP_DECL_HEURCLONE(scip::ObjCloneable *Heur2opt::clone)
Definition: Heur2opt.cpp:236
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
Definition of base class for all clonable classes.
Definition: objcloneable.h:38
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
void capture_graph(GRAPH *gr)
void release_graph(GRAPH **gr)
#define nnodes
Definition: gastrans.c:65
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305