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