operations_research::sat::BasicKnapsackSolver Class Reference

#include <util.h>

Classes
struct	Result

Public Member Functions
Result	Solve (const std::vector< Domain > &domains, const std::vector< int64_t > &coeffs, const std::vector< int64_t > &costs, const Domain &rhs)

Detailed Description

Use Dynamic programming to solve a single knapsack. This is used by the presolver to simplify variables appearing in a single linear constraint.

Complexity is the best of

• O(num_variables * num_relevant_values ^ 2) or
• O(num_variables * num_relevant_values * max_domain_size).

Definition at line 487 of file util.h.

Member Function Documentation

Solve()

BasicKnapsackSolver::Result operations_research::sat::BasicKnapsackSolver::Solve	(	const std::vector< Domain > &	domains,
		const std::vector< int64_t > &	coeffs,
		const std::vector< int64_t > &	costs,
		const Domain &	rhs )

The complexity of our DP will depends on the number of "activity" values that need to be considered.

Todo

(user): We can also solve efficiently if max_activity - rhs.Min() is small. Implement.

Problem is clearly infeasible, we can report the result right away.

Abort if complexity too large.

Canonicalize to positive coeffs and non-negative variables.

Transform solution back.

Definition at line 641 of file util.cc.

---

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

• ortools/sat/util.h
• ortools/sat/util.cc