Scippy

    SCIP

    Solving Constraint Integer Programs

    Functions
    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"

    Go to the source code of this file.

    Functions

    static GRAPHEDGE * findEdge (GRAPHNODE *nodes, int index1, int index2)
     
    static 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

    ◆ findEdge()

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

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

    Parameters
    nodesall nodes of the graph
    index1id of the node where the searched edge starts
    index2id of the node where the searched edge ends

    Definition at line 46 of file HeurFarthestInsert.cpp.

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

    Referenced by SCIP_DECL_HEUREXEC().

    ◆ updateDistances()

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

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

    Parameters
    nodesall nodes of the graph
    distarray with current distances of all nodes to the subtour
    idxid of the inserted node

    Definition at line 68 of file HeurFarthestInsert.cpp.

    References GraphEdge::adjac, GraphNode::first_edge, GraphNode::id, GraphEdge::length, GraphEdge::next, NULL, SCIPvarGetUbGlobal(), and GraphEdge::var.

    Referenced by SCIP_DECL_HEUREXEC().

    ◆ SCIP_DECL_HEURFREE()

    SCIP_DECL_HEURFREE ( HeurFarthestInsert::scip_free  )

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

    Definition at line 88 of file HeurFarthestInsert.cpp.

    References SCIP_OKAY.

    ◆ SCIP_DECL_HEURINIT()

    SCIP_DECL_HEURINIT ( HeurFarthestInsert::scip_init  )

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

    Definition at line 94 of file HeurFarthestInsert.cpp.

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

    ◆ SCIP_DECL_HEUREXIT()

    SCIP_DECL_HEUREXIT ( HeurFarthestInsert::scip_exit  )

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

    Definition at line 103 of file HeurFarthestInsert.cpp.

    References release_graph(), and SCIP_OKAY.

    ◆ SCIP_DECL_HEURINITSOL()

    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 116 of file HeurFarthestInsert.cpp.

    References SCIP_OKAY.

    ◆ SCIP_DECL_HEUREXITSOL()

    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 126 of file HeurFarthestInsert.cpp.

    References SCIP_OKAY.

    ◆ SCIP_DECL_HEUREXEC()

    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 142 of file HeurFarthestInsert.cpp.

    References GraphEdge::adjac, GraphEdge::back, BMSclearMemoryArray, FALSE, findEdge(), GraphNode::first_edge, GraphNode::id, GraphEdge::length, GraphEdge::next, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPsetSolVal(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, updateDistances(), GraphEdge::var, and w.

    ◆ SCIP_DECL_HEURCLONE()

    SCIP_DECL_HEURCLONE ( scip::ObjCloneable *HeurFarthestInsert::clone  )

    clone method which will be used to copy a objective plugin

    Definition at line 371 of file HeurFarthestInsert.cpp.