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 790 of file branch_and_bound_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and engine.

TEST() [2/20]

TEST	(	BranchAndBoundFramework	,
		ApplyExceptionDuringMoveOrderingDoesNotCallUndo
	)

Definition at line 777 of file branch_and_bound_test.cc.

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

TEST() [3/20]

TEST	(	BranchAndBoundFramework	,
		ApplyExceptionDuringVisitedDepthFirstDoesNotCallUndo
	)

Definition at line 800 of file branch_and_bound_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and engine.

TEST() [4/20]

TEST	(	BranchAndBoundFramework	,
		ArtificialMaximizationPrunesByBound
	)

Definition at line 703 of file branch_and_bound_test.cc.

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

TEST() [5/20]

TEST	(	BranchAndBoundFramework	,
		ArtificialMinimizationWorksWithBestFirst
	)

Definition at line 733 of file branch_and_bound_test.cc.

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

TEST() [6/20]

TEST	(	BranchAndBoundFramework	,
		AssignmentBestFirstMatchesDepthFirst
	)

Definition at line 965 of file branch_and_bound_test.cc.

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

TEST() [7/20]

TEST	(	BranchAndBoundFramework	,
		AssignmentMinimizationFindsExpectedOptimum
	)

Definition at line 939 of file branch_and_bound_test.cc.

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

TEST() [8/20]

TEST	(	BranchAndBoundFramework	,
		BoundOrderedDepthFirstAndBestFirstBeatPlainBadOrder
	)

Definition at line 750 of file branch_and_bound_test.cc.

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

TEST() [9/20]

TEST	(	BranchAndBoundFramework	,
		IncrementalBoundProviderUsedForOrdering
	)

Definition at line 1055 of file branch_and_bound_test.cc.

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

TEST() [10/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackBestFirstMatchesDepthFirst
	)

Definition at line 902 of file branch_and_bound_test.cc.

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

TEST() [11/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackCapacityZeroReturnsEmptySolution
	)

Definition at line 1037 of file branch_and_bound_test.cc.

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

TEST() [12/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackFractionalBoundFindsOptimal
	)

Definition at line 886 of file branch_and_bound_test.cc.

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

TEST() [13/20]

TEST	(	BranchAndBoundFramework	,
		KnapsackFractionalBoundPrunesMoreThanWeakBound
	)

Definition at line 921 of file branch_and_bound_test.cc.

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

TEST() [14/20]

TEST	(	BranchAndBoundFramework	,
		MaxDepthOnePreventsCompleteSolution
	)

Definition at line 1000 of file branch_and_bound_test.cc.

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

TEST() [15/20]

TEST	(	BranchAndBoundFramework	,
		MaxExpansionsOnePreventsCompleteSolution
	)

Definition at line 1018 of file branch_and_bound_test.cc.

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

TEST() [16/20]

TEST	(	BranchAndBoundFramework	,
		ObjectivePoliciesAndIncumbentConstruct
	)

Definition at line 686 of file branch_and_bound_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [17/20]

TEST	(	BranchAndBoundFramework	,
		PostApplyExceptionCallsUndo
	)

Definition at line 833 of file branch_and_bound_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and engine.

TEST() [18/20]

TEST	(	BranchAndBoundFramework	,
		PostApplyExceptionDuringVisitedDepthFirstCallsUndo
	)

Definition at line 852 of file branch_and_bound_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and engine.

TEST() [19/20]

TEST	(	BranchAndBoundFramework	,
		StopAtFirstSolutionUsesCommonExplorationPolicy
	)

Definition at line 871 of file branch_and_bound_test.cc.

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

TEST() [20/20]

TEST	(	BranchAndBoundFramework	,
		VisitedMapSearchKeepsRecordedBoundsOnSuccess
	)

Definition at line 720 of file branch_and_bound_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and engine.