branch_and_bound_test.cc File Reference

#include <memory>
#include <stdexcept>
#include <string>
#include <gtest/gtest.h>
#include <Knapsack.H>
#include <State_Search.H>

Include dependency graph for branch_and_bound_test.cc:

Go to the source code of this file.

Classes
struct	ThrowingPostApplyDomain
struct	ThrowingPostApplyVisitedDomain

Functions
	TEST (BranchAndBoundFramework, ObjectivePoliciesAndIncumbentConstruct)
	TEST (BranchAndBoundFramework, ArtificialMaximizationPrunesByBound)
	TEST (BranchAndBoundFramework, VisitedMapSearchKeepsRecordedBoundsOnSuccess)
	TEST (BranchAndBoundFramework, ArtificialMinimizationWorksWithBestFirst)
	TEST (BranchAndBoundFramework, BoundOrderedDepthFirstAndBestFirstBeatPlainBadOrder)
	TEST (BranchAndBoundFramework, ApplyExceptionDuringMoveOrderingDoesNotCallUndo)
	TEST (BranchAndBoundFramework, ApplyExceptionDuringDepthFirstExpansionDoesNotCallUndo)
	TEST (BranchAndBoundFramework, ApplyExceptionDuringVisitedDepthFirstDoesNotCallUndo)
	TEST (BranchAndBoundFramework, PostApplyExceptionCallsUndo)
	TEST (BranchAndBoundFramework, PostApplyExceptionDuringVisitedDepthFirstCallsUndo)
	TEST (BranchAndBoundFramework, StopAtFirstSolutionUsesCommonExplorationPolicy)
	TEST (BranchAndBoundFramework, KnapsackFractionalBoundFindsOptimal)
	TEST (BranchAndBoundFramework, KnapsackBestFirstMatchesDepthFirst)
	TEST (BranchAndBoundFramework, KnapsackFractionalBoundPrunesMoreThanWeakBound)
	TEST (BranchAndBoundFramework, AssignmentMinimizationFindsExpectedOptimum)
	TEST (BranchAndBoundFramework, AssignmentBestFirstMatchesDepthFirst)
	TEST (BranchAndBoundFramework, MaxDepthOnePreventsCompleteSolution)
	TEST (BranchAndBoundFramework, MaxExpansionsOnePreventsCompleteSolution)
	TEST (BranchAndBoundFramework, KnapsackCapacityZeroReturnsEmptySolution)
	TEST (BranchAndBoundFramework, IncrementalBoundProviderUsedForOrdering)

Function Documentation

TEST() [1/20]

TEST	(	BranchAndBoundFramework	,
		ApplyExceptionDuringDepthFirstExpansionDoesNotCallUndo
	)

Definition at line 819 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and engine.

TEST() [2/20]

TEST	(	BranchAndBoundFramework	,
		ApplyExceptionDuringMoveOrderingDoesNotCallUndo
	)

Definition at line 806 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), engine, and Aleph::ExplorationPolicy::move_ordering.

TEST() [3/20]

TEST	(	BranchAndBoundFramework	,
		ApplyExceptionDuringVisitedDepthFirstDoesNotCallUndo
	)

Definition at line 829 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and engine.

TEST() [4/20]

TEST	(	BranchAndBoundFramework	,
		ArtificialMaximizationPrunesByBound
	)

Definition at line 732 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::branch_and_bound_search().

TEST() [5/20]

TEST	(	BranchAndBoundFramework	,
		ArtificialMinimizationWorksWithBestFirst
	)

Definition at line 762 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), engine, and Aleph::ExplorationPolicy::strategy.

TEST() [6/20]

TEST	(	BranchAndBoundFramework	,
		AssignmentBestFirstMatchesDepthFirst
	)

Definition at line 994 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), and Aleph::ExplorationPolicy::strategy.

TEST() [7/20]

TEST	(	BranchAndBoundFramework	,
		AssignmentMinimizationFindsExpectedOptimum
	)

Definition at line 968 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), engine, and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

TEST() [8/20]

TEST	(	BranchAndBoundFramework	,
		BoundOrderedDepthFirstAndBestFirstBeatPlainBadOrder
	)

Definition at line 779 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::branch_and_bound_search(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy().

TEST() [9/20]

TEST	(	BranchAndBoundFramework	,
		IncrementalBoundProviderUsedForOrdering
	)

Definition at line 1084 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), engine, Aleph::ExplorationPolicy::move_ordering, and Aleph::ExplorationPolicy::stop_at_first_solution.

TEST() [10/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackBestFirstMatchesDepthFirst
	)

Definition at line 931 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::branch_and_bound_search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), Aleph::Array< T >::size(), and Aleph::ExplorationPolicy::strategy.

TEST() [11/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackCapacityZeroReturnsEmptySolution
	)

Definition at line 1066 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::branch_and_bound_search(), and Aleph::Array< T >::size().

TEST() [12/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackFractionalBoundFindsOptimal
	)

Definition at line 915 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::branch_and_bound_search(), and Aleph::Array< T >::size().

TEST() [13/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackFractionalBoundPrunesMoreThanWeakBound
	)

Definition at line 950 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::branch_and_bound_search(), and Aleph::Array< T >::size().

TEST() [14/20]

TEST	(	BranchAndBoundFramework	,
		MaxDepthOnePreventsCompleteSolution
	)

Definition at line 1029 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), engine, Aleph::SearchLimits::max_depth, and Aleph::ExplorationPolicy::stop_at_first_solution.

TEST() [15/20]

TEST	(	BranchAndBoundFramework	,
		MaxExpansionsOnePreventsCompleteSolution
	)

Definition at line 1047 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), engine, Aleph::SearchLimits::max_expansions, and Aleph::ExplorationPolicy::stop_at_first_solution.

TEST() [16/20]

TEST	(	BranchAndBoundFramework	,
		ObjectivePoliciesAndIncumbentConstruct
	)

Definition at line 715 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [17/20]

TEST	(	BranchAndBoundFramework	,
		PostApplyExceptionCallsUndo
	)

Definition at line 862 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and engine.

TEST() [18/20]

TEST	(	BranchAndBoundFramework	,
		PostApplyExceptionDuringVisitedDepthFirstCallsUndo
	)

Definition at line 881 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and engine.

TEST() [19/20]

TEST	(	BranchAndBoundFramework	,
		StopAtFirstSolutionUsesCommonExplorationPolicy
	)

Definition at line 900 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::branch_and_bound_search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), and Aleph::ExplorationPolicy::stop_at_first_solution.

TEST() [20/20]

TEST	(	BranchAndBoundFramework	,
		VisitedMapSearchKeepsRecordedBoundsOnSuccess
	)

Definition at line 749 of file branch_and_bound_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and engine.