ommx.testing.placement

ommx.testing.placement#

Plant Placement Problem — equivalent OMMX formulations.

This module provides a small, solver-agnostic benchmark problem used to exercise an adapter’s SOS1 handling. The builders in this module produce ommx.v1.Instance objects describing the same feasible region and optimum; they differ only in how “at most one plant per region” is communicated to the solver.

Problem#

A set of plants and clients are drawn uniformly from \([0, 100]^2\). A vertical line at \(x = 50\) partitions the plants into a west region \(W = \{i : x_i^{\text{plant}} < 50\}\) and an east region \(E = \{i : x_i^{\text{plant}} \ge 50\}\). At most one plant may be opened in each region; the opened plant covers all of its region’s share of client demand via a continuous transport variable.

Sets and parameters#

\(N\) plants, \(M\) clients.
\(C_i \ge 0\) — maximum capacity of plant \(i\).
\(d_j \ge 0\) — demand of client \(j\).
\(\operatorname{dist}(i, j)\) — Euclidean distance between plant \(i\) and client \(j\).

Decision variables (shared by both formulations)#

\[\begin{aligned} s_{i,j} &\in [0, d_j] \qquad i \in 1..N,\ j \in 1..M \\ c_i &\in [0, C_i] \qquad i \in 1..N \end{aligned}\]

where \(s_{i,j}\) is the amount delivered from plant \(i\) to client \(j\) and \(c_i\) is the total capacity drawn from plant \(i\).

Shared constraints#

\[\begin{aligned} \sum_{j=1}^M s_{i,j} &= c_i \quad \text{(capacity balance, per plant)} \\ \sum_{i=1}^N s_{i,j} &= d_j \quad \text{(demand, per client)} \end{aligned}\]

Objective (minimize)#

\[\min \; \sum_{i,j} \operatorname{dist}(i, j) \cdot s_{i,j} \;+\; \sum_i c_i\]

“At most one plant per region” — eight formulations#

All eight builders share the decision variables and constraints above and encode the same feasible region on \((s, c)\). They differ along three orthogonal axes:

whether the auxiliary opening indicator \(\delta_i \in \{0, 1\}\) and the big-M link \(c_i \le C_i \, \delta_i\) are introduced;
whether the per-region cardinality \(\sum_{i \in W} \delta_i \le 1\) (and the analogous east bound) is added as a plain linear constraint;
where SOS1 is declared: on the continuous capacities \(\{c_i\}_{i \in W/E}\), on the binary indicators \(\{\delta_i\}_{i \in W/E}\), on both (redundant), or nowhere.

The eight builders enumerate every well-defined combination:

#	Builder	δ + big-M	\(\sum δ ≤ 1\)	SOS1 on c	SOS1 on δ
1	`build_sos1()`	–	–	✓	–
2	`build_sos1_on_c_with_delta()`	✓	–	✓	–
3	`build_sos1_on_c_with_delta_with_card()` \| ✓		✓	✓	–
4	`build_sos1_on_delta()`	✓	–	–	✓
5	`build_sos1_on_delta_with_card()`	✓	✓	–	✓
6	`build_sos1_on_both_with_delta()`	✓	–	✓	✓
7	`build_sos1_on_both_with_delta_with_card()` \| ✓		✓	✓	✓
8	`build_bigm()`	✓	✓	–	–

The δ-bearing rows always include the big-M link \(c_i \le C_i \, \delta_i\). Each region with at least two plants contributes one SOS1 set per “✓” in the SOS1 columns; regions with fewer than two plants are skipped (the constraint is trivially satisfied).

Intended use#

These eight builders are useful for benchmarking how a solver — and the adapter forwarding to it — reacts to different ways of expressing the same SOS1 structure. Callers should construct Input.random() with a fixed random.seed for reproducibility and pass the resulting Input to each builder to obtain comparable instances.

Classes#

`Client`
`Input`
`Plant`

Functions#

`build_bigm`(→ ommx.v1.Instance)	Pure linear: big-M link plus per-region cardinality bounds, no SOS1.
`build_sos1`(→ ommx.v1.Instance)	Build the instance with one SOS1 constraint per region on \(c_i\).
`build_sos1_on_both_with_delta`(→ ommx.v1.Instance)	δ + big-M; SOS1 declared on both c and δ (no explicit cardinality).
`build_sos1_on_both_with_delta_with_card`(→ ommx.v1.Instance)	δ + big-M + cardinality; SOS1 declared on both c and δ (maximum-information).
`build_sos1_on_c_with_delta`(→ ommx.v1.Instance)	δ + big-M; per-region cardinality enforced by SOS1 on the continuous c_i.
`build_sos1_on_c_with_delta_with_card`(→ ommx.v1.Instance)	δ + big-M + cardinality AND a SOS1 on the continuous c_i (cardinality kept).
`build_sos1_on_delta`(→ ommx.v1.Instance)	δ + big-M; per-region cardinality replaced by SOS1 on the binaries.
`build_sos1_on_delta_with_card`(→ ommx.v1.Instance)	δ + big-M + cardinality bounds AND a redundant SOS1 on the binaries.

Module Contents#

class Client#

demand: float#

position: Tuple[float, float]#

class Input#

classmethod random(num_plants: int, num_clients: int) → Input#

Sample a random instance that is feasible under the one-plant-per-region rule.

Plant and client positions are drawn uniformly from \([0, 100]^2\). Client demands are uniform on \([200, 400]\). Plant capacities are drawn from a range sized relative to total demand.

To keep the sampled instance feasible under “at most one plant per region”, two repairs are applied:

Plant positions are resampled until both west and east regions contain at least one plant.
If the best plant in each region together cannot cover total demand, the deficit is split evenly between those two best plants. Only the two best plants are touched — all other capacities are left at their sampled values, so the benchmark difficulty is not inflated across the board.

Requires num_plants >= 2. Callers are expected to seed random before calling this.

clients: List[Client]#

plants: List[Plant]#

class Plant#

max_capacity: float#

position: Tuple[float, float]#

build_bigm(input: Input) → Instance#: Pure linear: big-M link plus per-region cardinality bounds, no SOS1.

build_sos1(input: Input) → Instance#

Build the instance with one SOS1 constraint per region on \(c_i\).

A region with fewer than two plants is trivially satisfied and is skipped.

build_sos1_on_both_with_delta(input: Input) → Instance#: δ + big-M; SOS1 declared on both c and δ (no explicit cardinality).

build_sos1_on_both_with_delta_with_card(input: Input) → Instance#: δ + big-M + cardinality; SOS1 declared on both c and δ (maximum-information).

build_sos1_on_c_with_delta(input: Input) → Instance#: δ + big-M; per-region cardinality enforced by SOS1 on the continuous c_i.

build_sos1_on_c_with_delta_with_card(input: Input) → Instance#: δ + big-M + cardinality AND a SOS1 on the continuous c_i (cardinality kept).

build_sos1_on_delta(input: Input) → Instance#: δ + big-M; per-region cardinality replaced by SOS1 on the binaries.

build_sos1_on_delta_with_card(input: Input) → Instance#: δ + big-M + cardinality bounds AND a redundant SOS1 on the binaries.