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
40using namespace tsp;
41using namespace std;
42
43
44/** method finding the edge going from the node with id index1 to the node with id index2 */
45static
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) */
66SCIP_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) */
73SCIP_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) */
80SCIP_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 */
92SCIP_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 */
111SCIP_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 */
124SCIP_DECL_HEUREXEC(Heur2opt::scip_exec)
125{ /*lint --e{715}*/
126 assert( scip != NULL );
127 assert( result != NULL );
128 assert( heur != NULL );
129
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 */
245SCIP_DECL_HEURCLONE(scip::ObjCloneable* Heur2opt::clone) /*lint !e665*/
246{
247 return new Heur2opt(scip);
248}
void capture_graph(GRAPH *gr)
void release_graph(GRAPH **gr)
generator for global cuts in undirected graphs
SCIP_DECL_HEURCLONE(scip::ObjCloneable *Heur2opt::clone)
Definition: Heur2opt.cpp:245
SCIP_DECL_HEUREXIT(Heur2opt::scip_exit)
Definition: Heur2opt.cpp:80
SCIP_DECL_HEUREXITSOL(Heur2opt::scip_exitsol)
Definition: Heur2opt.cpp:111
SCIP_DECL_HEURINIT(Heur2opt::scip_init)
Definition: Heur2opt.cpp:73
static GRAPHEDGE * findEdge(GRAPHNODE *nodes, GRAPHNODE *node1, GRAPHNODE *node2)
Definition: Heur2opt.cpp:46
SCIP_DECL_HEURINITSOL(Heur2opt::scip_initsol)
Definition: Heur2opt.cpp:92
SCIP_DECL_HEURFREE(Heur2opt::scip_free)
Definition: Heur2opt.cpp:66
SCIP_DECL_HEUREXEC(Heur2opt::scip_exec)
Definition: Heur2opt.cpp:124
2-Optimum - combinatorial improvement heuristic for TSP
C++ problem data for TSP.
GRAPH * getGraph()
Definition: ProbDataTSP.h:97
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:2855
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
Definition: pqueue.h:38
scip::ObjProbData * SCIPgetObjProbData(SCIP *scip)
C++ wrapper classes for SCIP.
struct GraphEdge * back
Definition: GomoryHuTree.h:70
GRAPHNODE * adjac
Definition: GomoryHuTree.h:72
SCIP_VAR * var
Definition: GomoryHuTree.h:74
double length
Definition: GomoryHuTree.h:67
struct GraphEdge * next
Definition: GomoryHuTree.h:69
struct GraphEdge * first_edge
Definition: GomoryHuTree.h:53
Definition of base class for all clonable classes.
Definition: objcloneable.h:48
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_OKAY
Definition: type_retcode.h:42