operations_research::sat::BasicKnapsackSolver Class Reference

#include <util.h>

Classes
struct	Result

Public Member Functions
Result	Solve (absl::Span< const Domain > domains, absl::Span< const int64_t > coeffs, absl::Span< const 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 559 of file util.h.

Member Function Documentation

Solve()

BasicKnapsackSolver::Result operations_research::sat::BasicKnapsackSolver::Solve	(	absl::Span< const Domain >	domains,
		absl::Span< const int64_t >	coeffs,
		absl::Span< const 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 648 of file util.cc.

---

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

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