Expand description
§Chapter 5.8.5 — Block partitions
New with task L1.7a (PLAN.md trilha L): the contract’s
BlockPartition.
§Purpose
The matrices of optimization are assembled from blocks, and the code
around them keeps asking where a block begins: the simplex method prices
the structural columns of [A | ±I] and treats the logical ones apart
(Chapter 5.1); the interior-point method stacks [−D Aᵀ; A δI] and
must know that row n + i is the dual of constraint i
(Chapter 5.14, KktForm::Augmented);
a decomposition (Dantzig–Wolfe, Benders) names coupling rows and
subproblem blocks. The matrix stays one CscMatrix; a
BlockPartition is the small companion object that records the
boundaries of its row and column blocks, so that assembly with
Triplets, extraction and bookkeeping agree on them
instead of each recomputing n + i.
§Notation
An m × n matrix is partitioned into p ≥ 0 row blocks and q ≥ 0
column blocks by the boundary lists
row_blocks = [r_0, r_1, …, r_p], 0 = r_0 < r_1 < … < r_p = m,
col_blocks = [c_0, c_1, …, c_q], 0 = c_0 < c_1 < … < c_q = n.Row block k is the half-open range r_k..r_{k+1}; column block l is
c_l..c_{l+1}; block (k, l) is their product. Strict increase means a
block is never empty; a dimension of size 0 has the single boundary
list [0] and no block. Two partitions of the same matrix are equal iff
their lists are.
The two examples of the contract:
- the computational form
[A | ±I]of the simplex,A ∈ R^{m×n}: one row block,row_blocks = [0, m], and two column blocks,col_blocks = [0, n, n + m]— columnjis structural iffcol_block_of(j) = 0; - the augmented system
K = [−D Aᵀ; A δI]of ordern + m:row_blocks = col_blocks = [0, n, n + m]— the primal block first, asKktForm::Augmentedrequires.
§Algorithm B (Block of an index)
Given a boundary list b = [b_0, …, b_p] and an index 0 ≤ i < b_p.
B1. Find, by binary search, the number k of boundaries ≤ i
(partition_point): k ≥ 1 since b_0 = 0 ≤ i, and k ≤ p since
i < b_p.
B2. Return k − 1: the block b_{k−1}..b_k contains i.
Cost O(log p).
§Invariants
(B1) row_blocks is non-empty, starts at 0 and is strictly
increasing; its last element is m.
(B2) The same for col_blocks and n.
(B3) m ≤ u32::MAX and n ≤ u32::MAX: the dimensions fit the index
space of the containers ((C4) of Chapter 5.8).
Checked by BlockPartition::check_invariants; both constructors
return the first violation as a SparseError. The fields are public,
as in the contract; a value edited by hand should be checked again.
§References
Maros, Computational Techniques of the Simplex Method (2003), §5.1
(the computational form); Wright, Primal-Dual Interior-Point Methods
(1997), ch. 11 (the augmented system); the contract of the crate
(BlockPartition).
Structs§
- Block
Partition - Block boundaries of a partitioned matrix:
row_blocksandcol_blocksare boundary lists starting at0and ending atm,n(invariants (B1)–(B3)).