|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
Public Member Functions | |
| CoveringProblem (MPSolver *const solver, const Instance &instance) | |
| Grid is a row-major string of length width*height with '@' for an occupied cell (strawberry) and '. | |
| bool | Init () |
| Constructs initial variables and constraints. | |
| int | width () const |
| int | height () const |
| int | area () const |
| int | max_boxes () const |
| bool | IsCellOccupied (int x, int y) const |
| double | GetOptimalBox (Box *const target) |
| Calculates reduced costs for each possible Box and if any is negative (improves cost), returns reduced cost and set target to the most-negative (steepest descent) one - otherwise returns 0. | |
| MPVariable * | AddBox (const Box &box) |
| Add continuous [0,1] box variable with box.Cost() as objective coefficient. | |
| string | PrintGrid () const |
| string | PrintCovering () const |
| Prints covering - total cost, those variables with non-zero value, and graphical depiction of covering using upper case letters for integral coverage and lower case for coverage using combination of fractional boxes. | |
Protected Types | |
| typedef std::map< Box, MPVariable *, BoxLessThan > | BoxTable |
Protected Member Functions | |
| int | index (int x, int y) const |
| MPConstraint * | cell (int x, int y) |
| const MPConstraint * | cell (int x, int y) const |
| void | AddCellConstraints () |
| Adds constraints that every cell is covered at most once, exactly once if occupied. | |
| void | AddMaxBoxesConstraint () |
| Adds constraint on maximum number of boxes used to cover. | |
| double | zero_access (const std::vector< double > &array, int x, int y) const |
| Gets 2d array element, returning 0 if out-of-bounds. | |
| void | ComputeUpperLeftSums (std::vector< double > *upper_left_sums) const |
| Precomputes the sum of reduced costs for every upper-left rectangle. | |
Protected Attributes | |
| MPSolver *const | solver_ |
| not owned | |
| const int | max_boxes_ |
| const int | width_ |
| const int | height_ |
| const char *const | grid_ |
| std::vector< MPConstraint * > | cells_ |
| BoxTable | boxes_ |
| MPConstraint * | max_boxes_constraint_ |
Definition at line 311 of file strawberry_fields_with_column_generation.cc.
typedef std::map<Box, MPVariable*, BoxLessThan> operations_research::CoveringProblem::BoxTable [protected] |
Definition at line 552 of file strawberry_fields_with_column_generation.cc.
| operations_research::CoveringProblem::CoveringProblem | ( | MPSolver *const | solver, | |
| const Instance & | instance | |||
| ) | [inline] |
Grid is a row-major string of length width*height with '@' for an occupied cell (strawberry) and '.
' for an empty cell. Solver is not owned.
Definition at line 316 of file strawberry_fields_with_column_generation.cc.
| bool operations_research::CoveringProblem::Init | ( | ) | [inline] |
Constructs initial variables and constraints.
Initial column (box) covers entire grid, ensuring feasibility.
Definition at line 325 of file strawberry_fields_with_column_generation.cc.
| int operations_research::CoveringProblem::width | ( | ) | const [inline] |
Definition at line 356 of file strawberry_fields_with_column_generation.cc.
| int operations_research::CoveringProblem::height | ( | ) | const [inline] |
Definition at line 357 of file strawberry_fields_with_column_generation.cc.
| int operations_research::CoveringProblem::area | ( | ) | const [inline] |
Definition at line 358 of file strawberry_fields_with_column_generation.cc.
| int operations_research::CoveringProblem::max_boxes | ( | ) | const [inline] |
Definition at line 359 of file strawberry_fields_with_column_generation.cc.
| bool operations_research::CoveringProblem::IsCellOccupied | ( | int | x, | |
| int | y | |||
| ) | const [inline] |
Definition at line 361 of file strawberry_fields_with_column_generation.cc.
| double operations_research::CoveringProblem::GetOptimalBox | ( | Box *const | target | ) | [inline] |
Calculates reduced costs for each possible Box and if any is negative (improves cost), returns reduced cost and set target to the most-negative (steepest descent) one - otherwise returns 0.
For a problem in standard form 'minimize c*x s.t. Ax<=b, x>=0' the reduced cost vector is c - transp(y) * A where y is the dual cost column vector.
For this covering problem, in which all coefficients in A are 0 or 1, this reduces to:
reduced_cost(box) =
box.Cost() - sum_{enclosed cell} cell_constraint->dual_value()
Since there are O(d^4) boxes, we don't also want O(d^2) sum for each, so pre-calculate sums of cell duals for all rectangles with upper-left at 0, 0, and use these to calculate the sum in constant time using the standard inclusion-exclusion trick.
Definition at line 383 of file strawberry_fields_with_column_generation.cc.
| MPVariable* operations_research::CoveringProblem::AddBox | ( | const Box & | box | ) | [inline] |
Add continuous [0,1] box variable with box.Cost() as objective coefficient.
Add to cell constraint of all enclosed cells.
Definition at line 443 of file strawberry_fields_with_column_generation.cc.
| string operations_research::CoveringProblem::PrintGrid | ( | ) | const [inline] |
Definition at line 457 of file strawberry_fields_with_column_generation.cc.
| string operations_research::CoveringProblem::PrintCovering | ( | ) | const [inline] |
Prints covering - total cost, those variables with non-zero value, and graphical depiction of covering using upper case letters for integral coverage and lower case for coverage using combination of fractional boxes.
Definition at line 474 of file strawberry_fields_with_column_generation.cc.
| int operations_research::CoveringProblem::index | ( | int | x, | |
| int | y | |||
| ) | const [inline, protected] |
Definition at line 509 of file strawberry_fields_with_column_generation.cc.
| MPConstraint* operations_research::CoveringProblem::cell | ( | int | x, | |
| int | y | |||
| ) | [inline, protected] |
Definition at line 510 of file strawberry_fields_with_column_generation.cc.
| const MPConstraint* operations_research::CoveringProblem::cell | ( | int | x, | |
| int | y | |||
| ) | const [inline, protected] |
Definition at line 511 of file strawberry_fields_with_column_generation.cc.
| void operations_research::CoveringProblem::AddCellConstraints | ( | ) | [inline, protected] |
Adds constraints that every cell is covered at most once, exactly once if occupied.
Definition at line 515 of file strawberry_fields_with_column_generation.cc.
| void operations_research::CoveringProblem::AddMaxBoxesConstraint | ( | ) | [inline, protected] |
Adds constraint on maximum number of boxes used to cover.
Definition at line 526 of file strawberry_fields_with_column_generation.cc.
| double operations_research::CoveringProblem::zero_access | ( | const std::vector< double > & | array, | |
| int | x, | |||
| int | y | |||
| ) | const [inline, protected] |
Gets 2d array element, returning 0 if out-of-bounds.
Definition at line 531 of file strawberry_fields_with_column_generation.cc.
| void operations_research::CoveringProblem::ComputeUpperLeftSums | ( | std::vector< double > * | upper_left_sums | ) | const [inline, protected] |
Precomputes the sum of reduced costs for every upper-left rectangle.
Definition at line 540 of file strawberry_fields_with_column_generation.cc.
MPSolver* const operations_research::CoveringProblem::solver_ [protected] |
const int operations_research::CoveringProblem::max_boxes_ [protected] |
Definition at line 554 of file strawberry_fields_with_column_generation.cc.
const int operations_research::CoveringProblem::width_ [protected] |
Definition at line 555 of file strawberry_fields_with_column_generation.cc.
const int operations_research::CoveringProblem::height_ [protected] |
Definition at line 556 of file strawberry_fields_with_column_generation.cc.
const char* const operations_research::CoveringProblem::grid_ [protected] |
Definition at line 557 of file strawberry_fields_with_column_generation.cc.
std::vector<MPConstraint*> operations_research::CoveringProblem::cells_ [protected] |
Definition at line 558 of file strawberry_fields_with_column_generation.cc.
BoxTable operations_research::CoveringProblem::boxes_ [protected] |
Definition at line 559 of file strawberry_fields_with_column_generation.cc.
MPConstraint* operations_research::CoveringProblem::max_boxes_constraint_ [protected] |
Definition at line 560 of file strawberry_fields_with_column_generation.cc.