Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

tests for Steiner tree TM (shortest path based) heuristics

Author: Daniel Rehfeldt

This file implements tests for Steiner problem TM (shortest path based) heuristics.

A list of all interface methods can be found in stptest.h.

Definition in file stptest_heurtm.c.

#include <stdio.h>
#include <assert.h>
#include "stptest.h"
#include "graph.h"
#include "solstp.h"
#include "heur_tm.h"
#include "portab.h"

Go to the source code of this file.

Functions
static SCIP_RETCODE	runTmPcFull (SCIP scip, GRAPH graph, int *steinertree_edges)

static SCIP_RETCODE	testTmGivesExpectedTreePcFull1 (SCIP *scip)

static SCIP_RETCODE	testTmGivesExpectedTreePcFull2 (SCIP *scip)

static SCIP_RETCODE	testTmGivesExpectedTreePcFull3 (SCIP *scip)

static SCIP_RETCODE	testPrunedSolIsImprovedPc1 (SCIP *scip)

static SCIP_RETCODE	testPrunedSolIsImprovedPc2 (SCIP *scip)

SCIP_RETCODE	stptest_testSolPrune (SCIP *scip)

SCIP_RETCODE	stptest_testHeurTm (SCIP *scip)

Function Documentation

◆ runTmPcFull()

static SCIP_RETCODE runTmPcFull	(	SCIP *	scip,
		GRAPH *	graph,
		int *	steinertree_edges
	)

static

runs TM heuristic

Parameters

scip	SCIP data structure
graph	graph data structure
steinertree_edges	the tree

Definition at line 39 of file stptest_heurtm.c.

References GRAPH::cost, NULL, pcmode_fulltree, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPStpHeurTMRun(), STPTEST_ASSERT, and GRAPH::terms.

Referenced by testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ testTmGivesExpectedTreePcFull1()

static SCIP_RETCODE testTmGivesExpectedTreePcFull1 ( SCIP * scip )

static

tests that PC solution is as expected

Parameters

scip	SCIP data structure

Definition at line 58 of file stptest_heurtm.c.

References EQ, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_getNonLeafTermOffset(), graph_pc_initPrizes(), nnodes, GRAPH::prize, runTmPcFull(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_getObjBounded(), GRAPH::source, STP_TERM, STPTEST_ASSERT_MSG_ARGS, stptest_graphSetUpPcExtended(), and stptest_graphTearDown().

Referenced by stptest_testHeurTm().

◆ testTmGivesExpectedTreePcFull2()

static SCIP_RETCODE testTmGivesExpectedTreePcFull2 ( SCIP * scip )

static

tests that PC solution is as expected

Parameters

scip	SCIP data structure

Definition at line 113 of file stptest_heurtm.c.

References EQ, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_getNonLeafTermOffset(), graph_pc_initPrizes(), nnodes, GRAPH::prize, runTmPcFull(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_getObjBounded(), GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG_ARGS, stptest_graphSetUpPcExtended(), and stptest_graphTearDown().

Referenced by stptest_testHeurTm().

◆ testTmGivesExpectedTreePcFull3()

static SCIP_RETCODE testTmGivesExpectedTreePcFull3 ( SCIP * scip )

static

tests that PC solution is as expected

Parameters

scip	SCIP data structure

Definition at line 173 of file stptest_heurtm.c.

References EQ, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_getNonLeafTermOffset(), graph_pc_initPrizes(), nnodes, GRAPH::prize, runTmPcFull(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_getObjBounded(), GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG_ARGS, stptest_graphSetUpPcExtended(), and stptest_graphTearDown().

Referenced by stptest_testHeurTm().

◆ testPrunedSolIsImprovedPc1()

static SCIP_RETCODE testPrunedSolIsImprovedPc1 ( SCIP * scip )

static

tests that PC solution is improved by pruning

Parameters

scip	SCIP data structure

Definition at line 237 of file stptest_heurtm.c.

References EQ, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_getNonLeafTermOffset(), graph_pc_initPrizes(), nnodes, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_getObjBounded(), solstp_prune(), GRAPH::source, STP_TERM, STPTEST_ASSERT_MSG_ARGS, stptest_graphSetUpPcExtended(), stptest_graphTearDown(), and TRUE.

Referenced by stptest_testSolPrune().

◆ testPrunedSolIsImprovedPc2()

static SCIP_RETCODE testPrunedSolIsImprovedPc2 ( SCIP * scip )

static

tests that PC solution is improved by pruning

Parameters

scip	SCIP data structure

Definition at line 299 of file stptest_heurtm.c.

References EQ, FALSE, FARAWAY, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_getNonLeafTermOffset(), graph_pc_initPrizes(), nnodes, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_getObjBounded(), solstp_prune(), GRAPH::source, STP_TERM, STPTEST_ASSERT_MSG_ARGS, stptest_graphSetUpPcExtended(), stptest_graphSetUpRmwExtended(), stptest_graphTearDown(), and TRUE.

Referenced by stptest_testSolPrune().

◆ stptest_testSolPrune()

SCIP_RETCODE stptest_testSolPrune ( SCIP * scip )

test pruning of solution

Parameters

scip	SCIP data structure

Definition at line 423 of file stptest_heurtm.c.

References SCIP_CALL, SCIP_OKAY, testPrunedSolIsImprovedPc1(), and testPrunedSolIsImprovedPc2().

Referenced by stptest_testAll().

◆ stptest_testHeurTm()

SCIP_RETCODE stptest_testHeurTm ( SCIP * scip )

tests TM heuristic

Parameters

scip	SCIP data structure

Definition at line 437 of file stptest_heurtm.c.

References SCIP_CALL, SCIP_OKAY, testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

Referenced by stptest_testAll().