#include <2d_orthogonal_packing.h>

Public Member Functions
	RoundingDualFeasibleFunction (IntegerValue max_x, IntegerValue k)
	`max_x` must fit in a uint16_t and `k` in [0, max_x/2].

IntegerValue	operator() (IntegerValue x) const
	`x` must be in [0, max_x].

IntegerValue	LowestInverse (IntegerValue y) const

Detailed Description

Dual Feasible Function based on rounding. Called f_2 on [1].

The f_2^k(x) function for an integer x in [0, C] and a parameter k taking values in [0, C/2] is defined as:

/ 2 * [ floor(C / k) - floor( (C - x) / k) ], if x > C / 2,

operations_research::sat::floor

floor(|P|/2)<

x

const Variable x

Definition qp_tests.cc:127

f_2^k(x) = | floor(C / k), if k = C / 2, \ floor(x / k), if x < C / 2.

This function is a Maximal Dual Feasible Function. Ie., it satisfies:

f_2 is nondecreasing,
f_2 is superadditive, i.e., f_2(x) + f_2(y) <= f_2(x + y),
f_2 is symmetric, i.e., f_2(x) + f_2(C - x) = f_2(C),
f_2(0) = 0.

[1] Carlier, Jacques, François Clautiaux, and Aziz Moukrim. "New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation." Computers & Operations Research 34.8 (2007): 2223-2250.

Definition at line 282 of file 2d_orthogonal_packing.h.

Constructor & Destructor Documentation

◆ RoundingDualFeasibleFunction()

operations_research::sat::RoundingDualFeasibleFunction::RoundingDualFeasibleFunction	(	IntegerValue	max_x,
		IntegerValue	k )

inline

max_x must fit in a uint16_t and k in [0, max_x/2].

Definition at line 285 of file 2d_orthogonal_packing.h.

Member Function Documentation

◆ LowestInverse()

IntegerValue operations_research::sat::RoundingDualFeasibleFunction::LowestInverse ( IntegerValue y ) const

Return the lowest integer y so that Dff(x) >= y. y must be in [0, Dff(max_x)].

Definition at line 150 of file 2d_orthogonal_packing.cc.

◆ operator()()

IntegerValue operations_research::sat::RoundingDualFeasibleFunction::operator() ( IntegerValue x ) const

inline

x must be in [0, max_x].

Definition at line 296 of file 2d_orthogonal_packing.h.

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