HeurFarthestInsert.cpp File Reference

Detailed Description

farthest insert - combinatorial heuristic for TSP

Author

Timo Berthold

Definition in file HeurFarthestInsert.cpp.

#include <iostream>
#include <cassert>
#include "objscip/objscip.h"
#include "GomoryHuTree.h"
#include "HeurFarthestInsert.h"
#include "ProbDataTSP.h"

Include dependency graph for HeurFarthestInsert.cpp:

Go to the source code of this file.

Functions
GRAPHEDGE *	findEdge (GRAPHNODE *nodes, int index1, int index2)
void	updateDistances (GRAPHNODE *nodes, double *dist, int idx)
	SCIP_DECL_HEURFREE (HeurFarthestInsert::scip_free)
	SCIP_DECL_HEURINIT (HeurFarthestInsert::scip_init)
	SCIP_DECL_HEUREXIT (HeurFarthestInsert::scip_exit)
	SCIP_DECL_HEURINITSOL (HeurFarthestInsert::scip_initsol)
	SCIP_DECL_HEUREXITSOL (HeurFarthestInsert::scip_exitsol)
	SCIP_DECL_HEUREXEC (HeurFarthestInsert::scip_exec)
	SCIP_DECL_HEURCLONE (scip::ObjCloneable *HeurFarthestInsert::clone)

Function Documentation

GRAPHEDGE* findEdge	(	GRAPHNODE *	nodes,
		int	index1,
		int	index2
	)

method finding the edge going from the node with id index1 to the node with id index2

Parameters

nodes	all nodes of the graph
index1	id of the node where the searched edge starts
index2	id of the node where the searched edge ends

Definition at line 36 of file HeurFarthestInsert.cpp.

References GraphEdge::adjac, GraphNode::first_edge, GraphNode::id, and GraphEdge::next.

Referenced by SCIP_DECL_HEUREXEC().

SCIP_DECL_HEURCLONE

(

scip::ObjCloneable *HeurFarthestInsert::clone

)

clone method which will be used to copy a objective plugin

Definition at line 354 of file HeurFarthestInsert.cpp.

SCIP_DECL_HEUREXEC

(

HeurFarthestInsert::scip_exec

)

execution method of primal heuristic

Searches for feasible primal solutions. The method is called in the node processing loop.

possible return values for *result:

• SCIP_FOUNDSOL : at least one feasible primal solution was found
• SCIP_DIDNOTFIND : the heuristic searched, but did not find a feasible solution
• SCIP_DIDNOTRUN : the heuristic was skipped
• SCIP_DELAYED : the heuristic was skipped, but should be called again as soon as possible, disregarding its frequency

Definition at line 131 of file HeurFarthestInsert.cpp.

References GraphEdge::adjac, GraphEdge::back, findEdge(), GraphNode::first_edge, GraphNode::id, GraphEdge::length, GraphEdge::next, updateDistances(), and GraphEdge::var.

SCIP_DECL_HEUREXIT

(

HeurFarthestInsert::scip_exit

)

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 92 of file HeurFarthestInsert.cpp.

References release_graph().

SCIP_DECL_HEUREXITSOL

(

HeurFarthestInsert::scip_exitsol

)

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.

Definition at line 115 of file HeurFarthestInsert.cpp.

SCIP_DECL_HEURFREE

(

HeurFarthestInsert::scip_free

)

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 77 of file HeurFarthestInsert.cpp.

SCIP_DECL_HEURINIT

(

HeurFarthestInsert::scip_init

)

initialization method of primal heuristic (called after problem was transformed)

Definition at line 83 of file HeurFarthestInsert.cpp.

References capture_graph(), and tsp::ProbDataTSP::getGraph().

SCIP_DECL_HEURINITSOL

(

HeurFarthestInsert::scip_initsol

)

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.

Definition at line 105 of file HeurFarthestInsert.cpp.

void updateDistances	(	GRAPHNODE *	nodes,
		double *	dist,
		int	idx
	)

method updating the distances of the nodes to the tour after having inserted one node with id index

Parameters

nodes	all nodes of the graph
dist	array with current distances of all nodes to the subtour
idx	id of the inserted node

Definition at line 56 of file HeurFarthestInsert.cpp.

References GraphEdge::adjac, GraphNode::first_edge, GraphNode::id, GraphEdge::length, GraphEdge::next, and GraphEdge::var.

Referenced by SCIP_DECL_HEUREXEC().