Bin-packing propagator. More...

#include <gecode/int/bin-packing.hh>

Public Member Functions
template<class SizeSet>
bool	nosum (const SizeSet &s, int a, int b, int &ap, int &bp)
	Detect non-existence of sums in a .. b.
template<class SizeSet>
bool	nosum (const SizeSet &s, int a, int b)
	Detect non-existence of sums in a .. b.
virtual ExecStatus	propagate (Space &home, const ModEventDelta &med)
	Perform propagation.
virtual PropCost	cost (const Space &home, const ModEventDelta &med) const
	Cost function.
virtual void	reschedule (Space &home)
	Schedule function.
virtual Actor *	copy (Space &home)
	Copy propagator during cloning.
virtual size_t	dispose (Space &home)
	Destructor.
ModEventDelta	modeventdelta (void) const
	Return the modification event delta.
virtual ExecStatus	advise (Space &home, Advisor &a, const Delta &d)
	Advise function.
virtual void	advise (Space &home, Advisor &a)
	Run advisor a to be run on failure in failed space.
double	afc (void) const
	Return the accumulated failure count.
unsigned int	id (void) const
	Return propagator id.
PropagatorGroup	group (void) const
	Return group propagator belongs to.
void	group (PropagatorGroup g)
	Add propagator to group g.
bool	disabled (void) const
	Whether propagator is currently disabled.
virtual	~Actor (void)
	To avoid warnings.

Static Public Member Functions
static ExecStatus	post (Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs, IntPropLevel ipl=IPL_DEF)
	Post propagator for loads l and items bs.
static void	calc_reductions (const ViewArray< Item > &bs, const ViewArray< OffsetView > &l, int weights_base_reduction, int &capacity_base_reduction, int delta_reductions)
static int	f_ccm1 (int w, int l, int c)
	Dual Feasible Functions.
static int	f_mt (int w, int l, int c)
static int	f_bj1 (int w, int l, int c)
static int	f_vb2_base (int w, int l, int c)
static int	f_vb2 (int w, int l, int c)
static int	f_fs1 (int w, int l, int c)
static int	f_rad2_base (int w, int l, int c)
static int	f_rad2 (int w, int l, int c)
static LambdaRange	l_ccm1 (int c)
static LambdaRange	l_mt (int c)
static LambdaRange	l_bj1 (int c)
static LambdaRange	l_vb2 (int c)
static LambdaRange	l_fs1 (int c)
static LambdaRange	l_rad2 (int c)
static LambdaRange	sanitize_lambda_range (LambdaRange lambda, int n_weights, int max_weight)
template<int f>
static int	calc_dff_lower_bound_single_lambda (const int *weights, int n_weights, int capacity, int lambda)
	Lower bound.
template<int f, LambdaRange l>
static int	calc_dff_lower_bound (const int *weights, int n_weights, int capacity, int n_not_zero_weights, int max_weight, bool sanitize=false)
static void *	operator new (size_t s, Space &home)
	Allocate memory from space.
static void	operator delete (void *p, Space &home)
	No-op for exceptions.
static void *	operator new (size_t s)
	Not used.
static void	operator delete (void *p)
	Not used.

Static Public Attributes
static int const	n_reductions = 3
	Reductions.
static int const	n_lambda_samples = 256

Protected Member Functions
	Pack (Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs, IntPropLevel ipl)
	Constructor for posting.
	Pack (Space &home, Pack &p)
	Constructor for cloning p.
Protected Member Functions inherited from Gecode::Propagator
	Propagator (Home home)
	Constructor for posting.
	Propagator (Space &home, Propagator &p)
	Constructor for cloning p.
Propagator *	fwd (void) const
	Return forwarding pointer during copying.
Kernel::GPI::Info &	gpi (void)
	Provide access to global propagator information.

Protected Attributes
ViewArray< OffsetView >	l
	Views for load of bins.
ViewArray< Item >	bs
	Items with bin and size.
IntPropLevel	ipl
	Propagation level.
int	t
	Total size of all items.

Detailed Description

Bin-packing propagator.

Basic and knapsack propagation are based on: Paul Shaw. A Constraint for Bin Packing. CP 2004.

The lower-bound phase uses dual-feasible functions described in: Tardivo et al. CP for Bin Packing with Multi-Core and GPUs. CP 2024.

Requires

#include <gecode/int/bin-packing.hh>

bin-packing.hh

Definition at line 151 of file bin-packing.hh.

Constructor & Destructor Documentation

◆ Pack() [1/2]

Gecode::Int::BinPacking::Pack::Pack	(	Home	home,
		ViewArray< OffsetView > &	l,
		ViewArray< Item > &	bs,
		IntPropLevel	ipl )

inlineprotected

Constructor for posting.

Definition at line 154 of file propagate.hpp.

◆ Pack() [2/2]

Gecode::Int::BinPacking::Pack::Pack	(	Space &	home,
		Pack &	p )

inlineprotected

Constructor for cloning p.

Definition at line 165 of file propagate.hpp.

Member Function Documentation

◆ post()

ExecStatus Gecode::Int::BinPacking::Pack::post	(	Home	home,
		ViewArray< OffsetView > &	l,
		ViewArray< Item > &	bs,
		IntPropLevel	ipl = IPL_DEF )

static

Post propagator for loads l and items bs.

Definition at line 381 of file propagate.cpp.

◆ nosum() [1/2]

template<class SizeSet>

bool Gecode::Int::BinPacking::Pack::nosum	(	const SizeSet &	s,
		int	a,
		int	b,
		int &	ap,
		int &	bp )

inline

Detect non-existence of sums in a .. b.

Definition at line 181 of file propagate.hpp.

◆ nosum() [2/2]

template<class SizeSet>

bool Gecode::Int::BinPacking::Pack::nosum	(	const SizeSet &	s,
		int	a,
		int	b )

inline

Detect non-existence of sums in a .. b.

Definition at line 212 of file propagate.hpp.

◆ propagate()

ExecStatus Gecode::Int::BinPacking::Pack::propagate	(	Space &	home,
		const ModEventDelta &	med )

virtual

Perform propagation.

Implements Gecode::Propagator.

Definition at line 117 of file propagate.cpp.

◆ cost()

PropCost Gecode::Int::BinPacking::Pack::cost	(	const Space &	home,
		const ModEventDelta &	med ) const

virtual

Cost function.

Implements Gecode::Propagator.

Definition at line 48 of file propagate.cpp.

◆ reschedule()

void Gecode::Int::BinPacking::Pack::reschedule ( Space & home )

virtual

Schedule function.

Implements Gecode::Propagator.

Definition at line 53 of file propagate.cpp.

◆ copy()

Actor * Gecode::Int::BinPacking::Pack::copy ( Space & home )

virtual

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 59 of file propagate.cpp.

◆ dispose()

size_t Gecode::Int::BinPacking::Pack::dispose ( Space & home )

inlinevirtual

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 172 of file propagate.hpp.

◆ calc_reductions()

void Gecode::Int::BinPacking::Pack::calc_reductions	(	const ViewArray< Item > &	bs,
		const ViewArray< OffsetView > &	l,
		int *	weights_base_reduction,
		int &	capacity_base_reduction,
		int *	delta_reductions )

static

Definition at line 420 of file propagate.cpp.

◆ f_ccm1()

int Gecode::Int::BinPacking::Pack::f_ccm1	(	int	w,
		int	l,
		int	c )

inlinestatic

Dual Feasible Functions.

Definition at line 218 of file propagate.hpp.

◆ f_mt()

int Gecode::Int::BinPacking::Pack::f_mt	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 233 of file propagate.hpp.

◆ f_bj1()

int Gecode::Int::BinPacking::Pack::f_bj1	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 248 of file propagate.hpp.

◆ f_vb2_base()

int Gecode::Int::BinPacking::Pack::f_vb2_base	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 264 of file propagate.hpp.

◆ f_vb2()

int Gecode::Int::BinPacking::Pack::f_vb2	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 270 of file propagate.hpp.

◆ f_fs1()

int Gecode::Int::BinPacking::Pack::f_fs1	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 287 of file propagate.hpp.

◆ f_rad2_base()

int Gecode::Int::BinPacking::Pack::f_rad2_base	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 300 of file propagate.hpp.

◆ f_rad2()

int Gecode::Int::BinPacking::Pack::f_rad2	(	int	w,
		int	l,
		int	c )

inlinestatic

Definition at line 315 of file propagate.hpp.

◆ l_ccm1()

LambdaRange Gecode::Int::BinPacking::Pack::l_ccm1 ( int c )

inlinestatic

Definition at line 328 of file propagate.hpp.

◆ l_mt()

LambdaRange Gecode::Int::BinPacking::Pack::l_mt ( int c )

inlinestatic

Definition at line 333 of file propagate.hpp.

◆ l_bj1()

LambdaRange Gecode::Int::BinPacking::Pack::l_bj1 ( int c )

inlinestatic

Definition at line 338 of file propagate.hpp.

◆ l_vb2()

LambdaRange Gecode::Int::BinPacking::Pack::l_vb2 ( int c )

inlinestatic

Definition at line 343 of file propagate.hpp.

◆ l_fs1()

LambdaRange Gecode::Int::BinPacking::Pack::l_fs1 ( int c )

inlinestatic

Definition at line 348 of file propagate.hpp.

◆ l_rad2()

LambdaRange Gecode::Int::BinPacking::Pack::l_rad2 ( int c )

inlinestatic

Definition at line 353 of file propagate.hpp.

◆ sanitize_lambda_range()

LambdaRange Gecode::Int::BinPacking::Pack::sanitize_lambda_range	(	LambdaRange	lambda,
		int	n_weights,
		int	max_weight )

inlinestatic

Definition at line 358 of file propagate.hpp.

◆ calc_dff_lower_bound_single_lambda()

template<int f>

int Gecode::Int::BinPacking::Pack::calc_dff_lower_bound_single_lambda	(	const int *	weights,
		int	n_weights,
		int	capacity,
		int	lambda )

inlinestatic

Lower bound.

Definition at line 374 of file propagate.hpp.

◆ calc_dff_lower_bound()

template<int f, LambdaRange l>

int Gecode::Int::BinPacking::Pack::calc_dff_lower_bound	(	const int *	weights,
		int	n_weights,
		int	capacity,
		int	n_not_zero_weights,
		int	max_weight,
		bool	sanitize = false )

inlinestatic

Definition at line 392 of file propagate.hpp.

Member Data Documentation

◆ l

ViewArray<OffsetView> Gecode::Int::BinPacking::Pack::l

protected

Views for load of bins.

Definition at line 154 of file bin-packing.hh.

◆ bs

ViewArray<Item> Gecode::Int::BinPacking::Pack::bs

protected

Items with bin and size.

Definition at line 156 of file bin-packing.hh.

◆ ipl

IntPropLevel Gecode::Int::BinPacking::Pack::ipl

protected

Propagation level.

Definition at line 158 of file bin-packing.hh.

◆ t

int Gecode::Int::BinPacking::Pack::t

protected

Total size of all items.

Definition at line 160 of file bin-packing.hh.

◆ n_reductions

int const Gecode::Int::BinPacking::Pack::n_reductions = 3

static

Reductions.

Definition at line 193 of file bin-packing.hh.

◆ n_lambda_samples

int const Gecode::Int::BinPacking::Pack::n_lambda_samples = 256

static

Definition at line 208 of file bin-packing.hh.

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

gecode/int/bin-packing.hh
gecode/int/bin-packing/propagate.cpp
gecode/int/bin-packing/propagate.hpp

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Pack() [1/2]

◆ Pack() [2/2]

Member Function Documentation

◆ post()

◆ nosum() [1/2]

◆ nosum() [2/2]

◆ propagate()

◆ cost()

◆ reschedule()

◆ copy()

◆ dispose()

◆ calc_reductions()

◆ f_ccm1()

◆ f_mt()

◆ f_bj1()

◆ f_vb2_base()

◆ f_vb2()

◆ f_fs1()

◆ f_rad2_base()

◆ f_rad2()

◆ l_ccm1()

◆ l_mt()

◆ l_bj1()

◆ l_vb2()

◆ l_fs1()

◆ l_rad2()

◆ sanitize_lambda_range()

◆ calc_dff_lower_bound_single_lambda()

◆ calc_dff_lower_bound()

Member Data Documentation

◆ l

◆ bs

◆ ipl

◆ t

◆ n_reductions

◆ n_lambda_samples