Detailed Description

Definition at line 268 of file routing_cuts.h.

#include <routing_cuts.h>

Classes
struct	ItemOrBin

Public Types
enum	ItemOrBinType { MUST_BE_ITEM = 0 , ITEM_OR_BIN = 1 , MUST_BE_BIN = 2 }
	See below. More...

Public Member Functions
	SpecialBinPackingHelper ()=default
	SpecialBinPackingHelper (double dp_effort)
int	ComputeMinNumberOfBins (absl::Span< ItemOrBin > objects, std::vector< int > &objects_that_cannot_be_bin_and_reach_minimum, std::string &info)
bool	GreedyPackingWorks (int num_bins, absl::Span< const ItemOrBin > objects)
bool	UseDpToTightenCapacities (absl::Span< ItemOrBin > objects)

Member Enumeration Documentation

◆ ItemOrBinType

enum operations_research::sat::SpecialBinPackingHelper::ItemOrBinType

See below.

Enumerator
MUST_BE_ITEM
ITEM_OR_BIN
MUST_BE_BIN

Definition at line 274 of file routing_cuts.h.

Constructor & Destructor Documentation

◆ SpecialBinPackingHelper() [1/2]

operations_research::sat::SpecialBinPackingHelper::SpecialBinPackingHelper ( )

default

◆ SpecialBinPackingHelper() [2/2]

operations_research::sat::SpecialBinPackingHelper::SpecialBinPackingHelper ( double dp_effort )

inlineexplicit

Definition at line 271 of file routing_cuts.h.

Member Function Documentation

◆ ComputeMinNumberOfBins()

int operations_research::sat::SpecialBinPackingHelper::ComputeMinNumberOfBins	(	absl::Span< ItemOrBin >	objects,
		std::vector< int > &	objects_that_cannot_be_bin_and_reach_minimum,
		std::string &	info )

Given a "special bin packing" problem as decribed above, return a lower bound on the number of bins that needs to be taken.

This simply sorts the object according to a greedy criteria and minimize the number of bins such that the "demands <= capacities" constraint is satisfied.

If the problem is infeasible, this will return object.size() + 1, which is a trivially infeasible bound.

Todo: (user): Use fancier DP to derive tighter bound. Also, when there are many dimensions, the choice of which item go to which bin is correlated, can we exploit this?

Todo: (user): we can probably handle a couple of extra case rather than just bailing out here and below.

If the gcd of all the demands term is positive, we can divide everything.

We only try DP if it can help.

Tricky: For the GreedyPackingWorks() to make sense, we use the fact that ComputeMinNumberOfBinsInternal() moves the best bins first. In any case the code will still be correct if it is not the case as we just use this as an heuristic to do less work.

Definition at line 385 of file routing_cuts.cc.

◆ GreedyPackingWorks()

bool operations_research::sat::SpecialBinPackingHelper::GreedyPackingWorks	(	int	num_bins,
		absl::Span< const ItemOrBin >	objects )

Visible for testing.

Returns true if we can greedily pack items with indices [num_bins, size) into the first num_bins bins (with indices [0, num_bins)). This function completely ignores the ItemOrBin types, and just uses the first num_bins objects as bins and the rest as items. It is up to the caller to make sure this is okay.

This is just used to quickly assess if a more precise lower bound on the number of bins could gain something. It works in O(num_bins * num_items).

We place the objects in order in the first bin that fits.

Definition at line 579 of file routing_cuts.cc.

◆ UseDpToTightenCapacities()

bool operations_research::sat::SpecialBinPackingHelper::UseDpToTightenCapacities ( absl::Span< ItemOrBin > objects )

Visible for testing.

If we look at all the possible sum of item demands, it is possible that some value can never be reached. We use dynamic programming to compute the set of reachable values and tighten the capacities accordingly.

Returns true iff we tightened something.

Todo: (user): We could be more tight here and also compute the max_reachable under smaller capacity than the max_capacity.

Definition at line 453 of file routing_cuts.cc.

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

ortools/sat/routing_cuts.h
ortools/sat/routing_cuts.cc