operations_research::sat::Disjoint2dPackingResult Struct Reference

#include <2d_rectangle_presolve.h>

Classes
struct	Bin

Public Attributes
std::vector< Bin >	bins

Detailed Description

Detect whether the fixed boxes of a no_overlap_2d constraint are splitting the space into separate components and thus can be replaced by one no_overlap_2d constraint per component. If this is not possible, return an empty result. Otherwise, return a struct containing what boxes (fixed and non-fixed) are needed in each new constraint.

Note

for this to be correct, we need to introduce new boxes to "fill" the space occupied by the other components. For example, if we have a no_overlap_2d constraint with the fixed boxes and the bounding box of the non-fixed boxes as follows: +------------------—+

++++++++++++++++++
++++++++++++++++++
++++++++++++++++++
*****
*****
*****

+------------------—+ and we are building the new no_overlap_2d constraint for the space below, we would need to add two new fixed boxes (the '.' and the 'o' one): +------------------—+ ooooooooooooooooooooo ooooooooooooooooooooo ooooooooooooooooooooo ooooooooooooooooooooo ooooooooooooooooooooo |...++++++++++++++++++| |...++++++++++++++++++| |...++++++++++++++++++| |***** | |***** |

*****

+------------------—+ This ensures that the new no_overlap_2d constraint will impose the box to be in that component as it should. Note that in the example above, the number of boxes won't really increase after a presolve pass, since the presolve for fixed boxes will simplify it to two fixed boxes again.

Definition at line 89 of file 2d_rectangle_presolve.h.

Member Data Documentation

bins

std::vector<Bin> operations_research::sat::Disjoint2dPackingResult::bins

Definition at line 99 of file 2d_rectangle_presolve.h.

---

The documentation for this struct was generated from the following file:

• ortools/sat/2d_rectangle_presolve.h