/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program and library */ /* SCIP --- Solving Constraint Integer Programs */ /* */ /* Copyright (C) 2002-2008 Konrad-Zuse-Zentrum */ /* fuer Informationstechnik Berlin */ /* */ /* SCIP is distributed under the terms of the ZIB Academic License. */ /* */ /* You should have received a copy of the ZIB Academic License */ /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #pragma ident "@(#) $Id: HeurLpgreedy.cpp,v 1.6 2009/09/11 16:34:48 bzfberth Exp $" /**@file HeurLpgreedy.cpp * @brief fractional travelling salesman heuristic - Rounding heuristic for TSP * @author Timo Berthold */ /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ #include "HeurLpgreedy.h" #include "ProbDataTSP.h" using namespace tsp; using namespace std; /* * Local methods */ /* * Callback methods of primal heuristic */ /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ SCIP_RETCODE HeurLpgreedy::scip_free( SCIP* scip, /**< SCIP data structure */ SCIP_HEUR* heur /**< the primal heuristic itself */ ) { return SCIP_OKAY; } /** initialization method of primal heuristic (called after problem was transformed) */ SCIP_RETCODE HeurLpgreedy::scip_init( SCIP* scip, /**< SCIP data structure */ SCIP_HEUR* heur /**< the primal heuristic itself */ ) { /* load the problem specific data */ ProbDataTSP* probdata = dynamic_cast(SCIPgetObjProbData(scip)); assert(probdata != NULL); /* get and capture the graph */ graph = probdata->getGraph(); assert(graph != NULL); capture_graph(graph); /* create heuristic data */ SCIP_CALL( SCIPcreateSol(scip, &lpsol, heur) ); return SCIP_OKAY; } /** deinitialization method of primal heuristic (called before transformed problem is freed) */ SCIP_RETCODE HeurLpgreedy::scip_exit( SCIP* scip, /**< SCIP data structure */ SCIP_HEUR* heur /**< the primal heuristic itself */ ) { /* free everything which was created in scip_init */ SCIP_CALL( SCIPfreeSol(scip, &lpsol) ); release_graph(&graph); return SCIP_OKAY; } /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) * * This method is called when the presolving was finished and the branch and bound process is about to begin. * The primal heuristic may use this call to initialize its branch and bound specific data. * */ SCIP_RETCODE HeurLpgreedy::scip_initsol( SCIP* scip, /**< SCIP data structure */ SCIP_HEUR* heur /**< the primal heuristic itself */ ) { return SCIP_OKAY; } /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) * * This method is called before the branch and bound process is freed. * The primal heuristic should use this call to clean up its branch and bound data. */ SCIP_RETCODE HeurLpgreedy::scip_exitsol( SCIP* scip, /**< SCIP data structure */ SCIP_HEUR* heur /**< the primal heuristic itself */ ) { return SCIP_OKAY; } /** execution method of primal heuristic */ SCIP_RETCODE HeurLpgreedy::scip_exec( SCIP* scip, /**< SCIP data structure */ SCIP_HEUR* heur, /**< the primal heuristic itself */ SCIP_HEURTIMING heurtiming, /**< current point in the node solving loop */ SCIP_RESULT* result /**< pointer to store the result of the heuristic call */ ) { /*lint --e{715}*/ SCIP_SOL* newsol; GRAPHNODE* currnode; SCIP_Bool* visited; int nnodes; int i; SCIP_Bool success; assert(result != NULL); /* since the timing is SCIP_HEURTIMING_AFTERLPNODE, the current node should have an LP */ assert(SCIPhasCurrentNodeLP(scip)); *result = SCIP_DIDNOTRUN; /* only call heuristic, if an optimal LP solution is at hand */ if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) return SCIP_OKAY; /* get the working solution from heuristic's local data */ assert(lpsol != NULL); /* copy the current LP solution to the working solution */ SCIP_CALL( SCIPlinkLPSol(scip, lpsol) ); *result = SCIP_DIDNOTFIND; /* choose the first node as starting point*/ currnode = &graph->nodes[0]; nnodes = graph->nnodes; success = TRUE; /* allocate local memory */ SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) ); SCIP_CALL( SCIPallocBufferArray(scip, &visited, nnodes) ); BMSclearMemoryArray(visited, nnodes); assert(currnode->id == 0); visited[0] = TRUE; /*exactly nnodes edges have to be inserted into the tour */ for( i = 0; i < nnodes; i++ ) { GRAPHEDGE* edge; SCIP_Real bestval; GRAPHEDGE* bestedge; /* initialization */ bestedge = NULL; bestval = -1; /* the graph works with adjacency lists */ edge = currnode->first_edge; /* the last edge is treated separately */ if( i != nnodes-1 ) { while( edge != NULL ) { /* update, if an edge has a better LP value AND was not visited yet AND was not globally dixed to zero */ if( SCIPgetSolVal(scip, lpsol, edge->var) > bestval && !visited[edge->adjac->id] && SCIPvarGetUbGlobal(edge->var) > 0.5 ) { bestval = SCIPgetSolVal(scip, lpsol, edge->var); bestedge = edge; } edge = edge->next; } } else { GRAPHNODE* finalnode; finalnode = &graph->nodes[0]; /* find the last edge which closes the tour */ while( edge != NULL && edge->adjac != finalnode) edge = edge->next; assert(edge != NULL); /* only close tour, if the neccessary edge is not fixed to zero yet */ if( SCIPvarGetUbGlobal(edge->var) > 0.5 ) { bestval = SCIPgetSolVal(scip, lpsol, edge->var); bestedge = edge; } } /* it may happen that we were not able to build a complete tour */ if( bestval == -1 ) { success = FALSE; break; } /* assert that the data is not corrupted */ assert(bestedge != NULL); assert(SCIPisFeasLE(scip, 0.0, bestval) && SCIPisFeasLE(scip, bestval, 1.0)); assert(bestval == SCIPgetSolVal(scip, lpsol, bestedge->var)); /* fix the variable which represents the best edge to one in the new solution and proceed to next node */ SCIP_CALL( SCIPsetSolVal(scip, newsol, bestedge->var, 1.0) ); currnode = bestedge->adjac; assert(currnode != NULL); assert(0 <= currnode->id && currnode->id <= nnodes-1); if( i != nnodes-1 ) assert(!visited[currnode->id]); visited[currnode->id] = TRUE; } /* if we were able to construct a complete tour, try to add the solution to SCIP */ if( success ) { for( i = 0; i < nnodes; i++ ) assert(visited[graph->nodes[i].id]); success = FALSE; /* due to construction we already know, that the solution will be feasible */ SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, FALSE, &success) ); if( success ) *result = SCIP_FOUNDSOL; } /* free all local memory */ SCIP_CALL( SCIPfreeSol(scip, &newsol) ); SCIPfreeBufferArray(scip, &visited); return SCIP_OKAY; }