Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::KnapsackSolver Class Reference

Detailed Description

Definition at line 103 of file knapsack_solver.h.

#include <knapsack_solver.h>

Public Types

enum  SolverType {
  KNAPSACK_BRUTE_FORCE_SOLVER = 0 , KNAPSACK_64ITEMS_SOLVER = 1 , KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER = 2 , KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER = 3 ,
  KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER = 5 , KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER = 6 , KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER = 7 , KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER = 8 ,
  KNAPSACK_DIVIDE_AND_CONQUER_SOLVER = 9 , KNAPSACK_MULTIDIMENSION_CP_SAT_SOLVER = 10
}
 Enum controlling which underlying algorithm is used. More...

Public Member Functions

 KnapsackSolver (const std::string &solver_name)
 KnapsackSolver (SolverType solver_type, const std::string &solver_name)
 KnapsackSolver (const KnapsackSolver &)=delete
KnapsackSolver & operator= (const KnapsackSolver &)=delete
virtual ~KnapsackSolver ()
void Init (const std::vector< int64_t > &profits, const std::vector< std::vector< int64_t > > &weights, const std::vector< int64_t > &capacities)
 Initializes the solver and enters the problem to be solved.
int64_t Solve ()
 Solves the problem and returns the profit of the optimal solution.
bool BestSolutionContains (int item_id) const
 Returns true if the item 'item_id' is packed in the optimal knapsack.
bool IsSolutionOptimal () const
 Returns true if the solution was proven optimal.
std::string GetName () const
bool use_reduction () const
void set_use_reduction (bool use_reduction)
void set_time_limit (double time_limit_seconds)
 Time limit in seconds.

Member Enumeration Documentation

◆ SolverType

enum operations_research::KnapsackSolver::SolverType

Enum controlling which underlying algorithm is used.

This enum is passed to the constructor of the KnapsackSolver object. It selects which solving method will be used.

Enumerator
KNAPSACK_BRUTE_FORCE_SOLVER 

Brute force method.

Limited to 30 items and one dimension, this solver uses a brute force algorithm, ie. explores all possible states. Experiments show competitive performance for instances with less than 15 items.

KNAPSACK_64ITEMS_SOLVER 

Optimized method for single dimension small problems

Limited to 64 items and one dimension, this solver uses a branch & bound algorithm. This solver is about 4 times faster than KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER.

KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER 

Dynamic Programming approach for single dimension problems

Limited to one dimension, this solver is based on a dynamic programming algorithm. The time and space complexity is O(capacity * number_of_items).

KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER 

CBC Based Solver

This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver CBC.

KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER 

Generic Solver.

This solver can deal with both large number of items and several dimensions. This solver is based on branch and bound.

KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER 

SCIP based solver

This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver SCIP.

KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER 

XPRESS based solver

This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver XPRESS.

KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER 

CPLEX based solver

This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver CPLEX.

KNAPSACK_DIVIDE_AND_CONQUER_SOLVER 

Divide and Conquer approach for single dimension problems

Limited to one dimension, this solver is based on a divide and conquer technique and is suitable for larger problems than Dynamic Programming Solver. The time complexity is O(capacity * number_of_items) and the space complexity is O(capacity + number_of_items).

KNAPSACK_MULTIDIMENSION_CP_SAT_SOLVER 

CP-SAT based solver

This solver can deal with both large number of items and several dimensions. This solver is based on the CP-SAT solver

Definition at line 108 of file knapsack_solver.h.

Constructor & Destructor Documentation

◆ KnapsackSolver() [1/3]

operations_research::KnapsackSolver::KnapsackSolver ( const std::string & solver_name)
explicit

Definition at line 1385 of file knapsack_solver.cc.

◆ KnapsackSolver() [2/3]

operations_research::KnapsackSolver::KnapsackSolver ( SolverType solver_type,
const std::string & solver_name )

Definition at line 1389 of file knapsack_solver.cc.

◆ KnapsackSolver() [3/3]

operations_research::KnapsackSolver::KnapsackSolver ( const KnapsackSolver & )
delete

◆ ~KnapsackSolver()

operations_research::KnapsackSolver::~KnapsackSolver ( )
virtualdefault

Member Function Documentation

◆ BestSolutionContains()

bool operations_research::KnapsackSolver::BestSolutionContains ( int item_id) const

Returns true if the item 'item_id' is packed in the optimal knapsack.

Definition at line 1633 of file knapsack_solver.cc.

◆ GetName()

std::string operations_research::KnapsackSolver::GetName ( ) const

Definition at line 1641 of file knapsack_solver.cc.

◆ Init()

void operations_research::KnapsackSolver::Init ( const std::vector< int64_t > & profits,
const std::vector< std::vector< int64_t > > & weights,
const std::vector< int64_t > & capacities )

Initializes the solver and enters the problem to be solved.

Definition at line 1441 of file knapsack_solver.cc.

◆ IsSolutionOptimal()

bool operations_research::KnapsackSolver::IsSolutionOptimal ( ) const
inline

Returns true if the solution was proven optimal.

Definition at line 207 of file knapsack_solver.h.

◆ operator=()

KnapsackSolver & operations_research::KnapsackSolver::operator= ( const KnapsackSolver & )
delete

◆ set_time_limit()

void operations_research::KnapsackSolver::set_time_limit ( double time_limit_seconds)
inline

Time limit in seconds.

When a finite time limit is set the solution obtained might not be optimal if the limit is reached.

Definition at line 216 of file knapsack_solver.h.

◆ set_use_reduction()

void operations_research::KnapsackSolver::set_use_reduction ( bool use_reduction)
inline

Definition at line 211 of file knapsack_solver.h.

◆ Solve()

int64_t operations_research::KnapsackSolver::Solve ( )

Solves the problem and returns the profit of the optimal solution.

Definition at line 1625 of file knapsack_solver.cc.

◆ use_reduction()

bool operations_research::KnapsackSolver::use_reduction ( ) const
inline

Definition at line 210 of file knapsack_solver.h.

The documentation for this class was generated from the following files: