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-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 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 {
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 } /*lint !e715*/
54 
55 
56 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
57 SCIP_DECL_HEURFREE(Heur2opt::scip_free)
58 {
59  return SCIP_OKAY;
60 } /*lint !e715*/
61 
62 
63 /** initialization method of primal heuristic (called after problem was transformed) */
64 SCIP_DECL_HEURINIT(Heur2opt::scip_init)
65 {
66  return SCIP_OKAY;
67 } /*lint !e715*/
68 
69 
70 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
71 SCIP_DECL_HEUREXIT(Heur2opt::scip_exit)
72 {
73  return SCIP_OKAY;
74 } /*lint !e715*/
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 {
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 } /*lint !e715*/
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 {
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 } /*lint !e715*/
112 
113 
114 /** execution method of primal heuristic 2-Opt */
115 SCIP_DECL_HEUREXEC(Heur2opt::scip_exec)
116 {
117  assert( heur != NULL );
118  SCIP_SOL* sol = SCIPgetBestSol( scip );
119  bool newsol;
120 
121  // check whether a new solution was found meanwhile
122  if( sol != sol_ )
123  {
124  sol_ = sol;
125  ncalls_ = 0;
126  newsol = true;
127  }
128  else
129  newsol = false;
130 
131  ncalls_++;
132 
133  int nnodes = graph_->nnodes; /*lint !e613*/
134 
135  // some cases need not to be handled
136  if( nnodes < 4 || sol == NULL || ncalls_ >= nnodes )
137  {
138  *result = SCIP_DIDNOTRUN;
139  return SCIP_OKAY;
140  }
141 
142  *result= SCIP_DIDNOTFIND;
143 
144  GRAPHNODE* nodes = graph_->nodes; /*lint !e613*/
145 
146  // get tour from sol and sort edges by length, if new solution was found
147  if( newsol )
148  {
149  GRAPHEDGE* edge;
150  GRAPHEDGE* lastedge = NULL;
151  GRAPHNODE* node = &nodes[0];
152  int i = 0;
153 
154  do
155  {
156  edge = node->first_edge;
157  while( edge != NULL )
158  {
159  // find the next edge of the tour
160  if( edge->back != lastedge && SCIPgetSolVal(scip, sol, edge->var) > 0.5 )
161  {
162  node = edge->adjac;
163  lastedge = edge;
164 
165  int j;
166  // shift edge through the (sorted) array
167  for(j = i; j > 0 && tour_[j-1]->length < edge->length; j-- ) /*lint !e613*/
168  tour_[j] = tour_[j-1]; /*lint !e613*/
169 
170  // and insert the edge at the right position
171  tour_[j] = edge; /*lint !e613*/
172 
173  i++;
174  break;
175  }
176  edge = edge->next;
177 
178  }
179  }while ( node != &nodes[0] );
180  assert( i == nnodes );
181 
182  }
183 
184  GRAPHEDGE** edges2test = NULL;
185  SCIP_CALL( SCIPallocBufferArray(scip, &edges2test, 4) );
186 
187  // test current edge with all 'longer' edges for improvement
188  // if swapping with crossing edges (though do 2Opt for one edge)
189  for( int i = 0; i < ncalls_ && *result != SCIP_FOUNDSOL; i++ )
190  {
191  edges2test[0] = tour_[ncalls_]; /*lint !e613*/
192  edges2test[1] = tour_[i]; /*lint !e613*/
193  edges2test[2] = findEdge( nodes, edges2test[0]->back->adjac, edges2test[1]->back->adjac );
194  edges2test[3] = findEdge( nodes, edges2test[0]->adjac, edges2test[1]->adjac );
195  assert( edges2test[2] != NULL );
196  assert( edges2test[3] != NULL );
197 
198  // if the new solution is better and variables are not fixed, update and end
199  if( edges2test[0]->length + edges2test[1]->length > edges2test[2]->length + edges2test[3]->length
200  && SCIPvarGetLbGlobal(edges2test[0]->var) == 0.0
201  && SCIPvarGetLbGlobal(edges2test[1]->var) == 0.0
202  && SCIPvarGetUbGlobal(edges2test[2]->var) == 1.0
203  && SCIPvarGetUbGlobal(edges2test[3]->var) == 1.0 )
204  {
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  }
230  SCIPfreeBufferArray(scip, &edges2test);
231 
232  return SCIP_OKAY;
233 } /*lint !e715*/
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:59
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
double length
Definition: GomoryHuTree.h:57
2-Optimum - combinatorial improvement heuristic for TSP
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
SCIP_DECL_HEUREXITSOL(Heur2opt::scip_exitsol)
Definition: Heur2opt.cpp:102
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip.c:40584
SCIP_DECL_HEURINIT(Heur2opt::scip_init)
Definition: Heur2opt.cpp:64
generator for global cuts in undirected graphs
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_DECL_HEURFREE(Heur2opt::scip_free)
Definition: Heur2opt.cpp:57
SCIP_VAR * var
Definition: GomoryHuTree.h:64
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_DECL_HEUREXEC(Heur2opt::scip_exec)
Definition: Heur2opt.cpp:115
GRAPHNODE * adjac
Definition: GomoryHuTree.h:62
struct GraphEdge * back
Definition: GomoryHuTree.h:60
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:43
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:350
GRAPH * getGraph()
Definition: ProbDataTSP.h:111
C++ problem data for TSP.
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38765
#define SCIP_Bool
Definition: def.h:61
SCIP_DECL_HEURINITSOL(Heur2opt::scip_initsol)
Definition: Heur2opt.cpp:83
SCIP_DECL_HEURCLONE(scip::ObjCloneable *Heur2opt::clone)
Definition: Heur2opt.cpp:236
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39876
Definition of base class for all clonable classes.
Definition: objcloneable.h:38
void capture_graph(GRAPH *gr)
void release_graph(GRAPH **gr)
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872