Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Milk Pooling and Blending

Adapted, with thanks, from work by the late Jeffrey Kantor.

This notebook is adapted from notebook 5.1, Milk pooling and blending, in the companion notebook collection for M. Postek, A. Zocca, J. Gromicho and J. Kantor, Hands-On Mathematical Optimization with Python (Cambridge University Press, 2025). Jeff Kantor was a colleague in this department; the example, the data and the framing of the three options are his.

The underlying problem is the canonical pooling benchmark of C. A. Haverly, “Studies of the behavior of recursion for the pooling problem,” ACM SIGMAP Bulletin 25 (1978), 19--28.

MIT License

Copyright (c) 2022 Jeffrey Kantor

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

What is different here. The models are rewritten with named pyo.Set and pyo.Param components so that the Pyomo code reads as the set-notation model in the lecture notes, the solver is ipopt throughout rather than appsi_highs, all three options are built by a single function rather than two, and the convex (McCormick) relaxation is left to the global optimization lecture. The notebook is organized on the course’s five-step procedure, with the three options carried through every step in parallel. Two typographical errors in the source notebook’s mathematics are corrected: its blending constraints are printed with the summation running over the cross product L×CL \times C inside a constraint that is already quantified for all c∈Cc \in C, and the sum must run over l∈Ll \in L alone. Its Pyomo code is correct as written.

# This code cell installs packages on Colab

import sys

if "google.colab" in sys.modules:
    !wget "https://raw.githubusercontent.com/ndcbe/optimization/main/notebooks/helper.py"
    import helper

    helper.easy_install()
else:
    sys.path.insert(0, "../")
    import helper
helper.set_plotting_style()

# `helper` also provides the extract / archive / figure plumbing used below.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pyomo.environ as pyo
from pyomo.environ import units as u
from pyomo.util.check_units import assert_units_consistent

# The source data is scale-free: milk is measured in "units" and priced per unit.
# Pyomo's unit library has neither, so declare both. Fat content stays
# dimensionless -- it is a mass fraction, kg of fat per kg of milk.
u.load_definitions_from_strings(["USD = [currency]", "milk = [milk]"])

Step 0: Problem statement

A bulk distributor supplies custom milk blends to several customers. Each customer specifies a minimum fat content, pays a fixed price per unit, and will buy no more than a stated maximum. The distributor sources raw milk from local farms, each producing milk of known fat content at a known cost.

The distributor has found cheaper raw milk at some remote farms. But it owns only one truck with a single tank for the remote route, so milk from the remote farms must be mixed in that tank before transport. That creates a pool of uniform composition, which is then blended with local milk to meet each customer’s requirement.

Three options:

  1. Business as usual --- local farms only.

  2. Buy a second truck --- keep each remote farm’s milk separate, so everything blends freely.

  3. Pool the remote farms --- one truck, one tank, one composition.

Options 1 and 2 are linear programs. Option 3 is not, and that is the point of the example.

The rest of the notebook follows the course’s five-step procedure --- mathematical model, model-size analysis, Pyomo implementation, analysis of the results --- and works all three options through each step side by side.

The objective measures operating profit. No truck purchase price, transport cost, tank capacity, or supplier limit is included. Comparing equipment investments requires those additional data and a common time horizon.

customers = pd.DataFrame(
    {
        "Customer 1": {"min_fat": 0.045, "price": 52.0, "demand": 6000.0},
        "Customer 2": {"min_fat": 0.030, "price": 48.0, "demand": 2500.0},
        "Customer 3": {"min_fat": 0.040, "price": 50.0, "demand": 4000.0},
    }
).T

suppliers = pd.DataFrame(
    {
        "Farm A": {"fat": 0.045, "cost": 45.0, "location": "local"},
        "Farm B": {"fat": 0.030, "cost": 42.0, "location": "local"},
        "Farm C": {"fat": 0.033, "cost": 37.0, "location": "remote"},
        "Farm D": {"fat": 0.050, "cost": 45.0, "location": "remote"},
    },
).T

# Farm and customer names
local_farms = suppliers.index[suppliers["location"] == "local"].tolist()
remote_farms = suppliers.index[suppliers["location"] == "remote"].tolist()
all_farms = local_farms + remote_farms
customer_names = customers.index.tolist()

# Problem data as plain dictionaries, keyed by farm or customer name

# Fat fraction of the milk from farm s, phi_s [dimensionless]
fat = suppliers["fat"].astype(float).to_dict()

# Purchase cost per unit from farm s, kappa_s [USD/milk]
cost = suppliers["cost"].astype(float).to_dict()

# Price paid per unit by customer k, pi_k [USD/milk]
price = customers["price"].astype(float).to_dict()

# Maximum demand of customer k, d_k [milk]
demand = customers["demand"].astype(float).to_dict()

# Minimum fat fraction customer k accepts, phi_min_k [dimensionless]
min_fat = customers["min_fat"].astype(float).to_dict()

print("Customers")
display(customers)

print("Suppliers")
display(suppliers)
Customers
Loading...
Suppliers
Loading...

Step 1: Mathematical model

It is tempting to write three models. Do not. All three options are the same model under different restrictions, and only one question changes between them:

Which farms can we buy from, and which of those must share the single tanker?

Optionfreely blended, L\mathcal{L}pooled, R\mathcal{R}model class
1. Business as usuallocal farmsemptyLP
2. Buy a second truckall farmsemptyLP
3. Pool the remote farmslocal farmsremote farmsbilinear NLP

Sets. L\mathcal{L}, the farms whose milk blends freely; R\mathcal{R}, the farms that must share one tanker; S=L∪R\mathcal{S} = \mathcal{L} \cup \mathcal{R}, every farm we buy from; K\mathcal{K}, the customers.

Parameters. ϕs\phi_s, the fat fraction of farm ss’s milk [dimensionless]; κs\kappa_s, its cost per unit [USD/milk]; πk\pi_k, the price customer kk pays [USD/milk]; dkd_k, its maximum demand [milk]; ϕkmin⁡\phi^{\min}_k, the minimum fat fraction it accepts [dimensionless].

The three subsections below write out each option in that notation. Read them together: Options 1 and 2 are the same equations over different farm sets, and Option 3 is those equations with a pool bolted on.

Option 1: business as usual

Only the local farms, and nothing is pooled: L\mathcal{L} is the local farms and R=∅\mathcal{R} = \emptyset. The one decision variable is zl,kz_{l,k}, the amount of milk from farm ll blended into the delivery to customer kk [milk].

max⁡z∑l∈L∑k∈K(πk−κl)zl,kprofits.t.∑l∈Lzl,k≤dk∀k∈Kdemand∑l∈Lϕlzl,k≥ϕkmin⁡∑l∈Lzl,k∀k∈Kblend qualityzl,k≥0\begin{align} \max_{\mathbf{z}} \quad & \sum_{l \in \mathcal{L}} \sum_{k \in \mathcal{K}} (\pi_k - \kappa_l) z_{l,k} && \text{profit} \\ \text{s.t.} \quad & \sum_{l \in \mathcal{L}} z_{l,k} \leq d_k && \forall k \in \mathcal{K} \quad \text{demand} \\ & \sum_{l \in \mathcal{L}} \phi_l z_{l,k} \geq \phi^{\min}_k \sum_{l \in \mathcal{L}} z_{l,k} && \forall k \in \mathcal{K} \quad \text{blend quality} \\ & z_{l,k} \geq 0 \end{align}

The blend quality constraint is the only one worth pausing on. It says the fat delivered to customer kk is at least the fraction ϕkmin⁡\phi^{\min}_k of the milk delivered to customer kk, which is a linear statement even though “average fat fraction” is a ratio: multiplying through by the denominator clears it. Every term is linear, so this is a linear program.

Option 2: a second truck

A second truck means each remote farm’s milk travels in its own tank, so it blends freely exactly like the local milk. Nothing is pooled, so R\mathcal{R} is still empty --- the remote farms simply move into L\mathcal{L}:

L={Farm A,Farm B,Farm C,Farm D},R=∅.\mathcal{L} = \{\text{Farm A}, \text{Farm B}, \text{Farm C}, \text{Farm D}\}, \qquad \mathcal{R} = \emptyset .

The equations are the ones written for Option 1, unchanged. It is still a linear program, and it is a relaxation of Option 3: everything Option 3 can do, Option 2 can do too, by sending the same milk down four separate tanks instead of one. So Option 2’s profit is an upper bound on Option 3’s.

Option 3: pool the remote farms

Only one truck is available for the remote route, so purchases from the remote farms are combined into a single pool of uniform composition, transported, and then blended with local milk. Now L\mathcal{L} is the local farms and R\mathcal{R} the remote ones.

This is the pp-parameterization of the pooling problem: the pool composition is itself a decision variable, pp.

Variables. zl,kz_{l,k}, local milk shipped from l∈Ll \in \mathcal{L} to customer kk; xrx_r, milk bought from remote farm rr; yky_k, pooled milk delivered to customer kk; and pp, the fat fraction of the pool.

max⁡x,y,z,p∑l∈L∑k∈K(πk−κl)zl,k+∑k∈Kπkyk−∑r∈Rκrxrprofits.t.∑l∈Lzl,k+yk≤dk∀k∈Kdemand∑r∈Rxr=∑k∈Kykpool balance∑r∈Rϕrxr=p∑r∈Rxr⏟bilinearpool fat balancep yk⏟bilinear+∑l∈Lϕlzl,k≥ϕkmin⁡(∑l∈Lzl,k+yk)∀k∈Kblend quality\begin{align} \max_{\mathbf{x}, \mathbf{y}, \mathbf{z}, p} \quad & \sum_{l \in \mathcal{L}} \sum_{k \in \mathcal{K}} (\pi_k - \kappa_l) z_{l,k} + \sum_{k \in \mathcal{K}} \pi_k y_k - \sum_{r \in \mathcal{R}} \kappa_r x_r && \text{profit} \\ \text{s.t.} \quad & \sum_{l \in \mathcal{L}} z_{l,k} + y_k \leq d_k && \forall k \in \mathcal{K} \quad \text{demand} \\ & \sum_{r \in \mathcal{R}} x_r = \sum_{k \in \mathcal{K}} y_k && \text{pool balance} \\ & \sum_{r \in \mathcal{R}} \phi_r x_r = \underbrace{p \sum_{r \in \mathcal{R}} x_r}_{\textbf{bilinear}} && \text{pool fat balance} \\ & \underbrace{p\, y_k}_{\textbf{bilinear}} + \sum_{l \in \mathcal{L}} \phi_l z_{l,k} \geq \phi^{\min}_k \Big( \sum_{l \in \mathcal{L}} z_{l,k} + y_k \Big) && \forall k \in \mathcal{K} \quad \text{blend quality} \end{align}

Every variable is nonnegative, yk≤dky_k \leq d_k, and pp is bounded below and above by the smallest and largest fat fractions among the remote farms --- a pool cannot be richer than its richest input.

The pool fat balance can be written either as p∑r∈Rxrp \sum_{r \in \mathcal{R}} x_r, as above and as the Pyomo code below does, or as p∑k∈Kykp \sum_{k \in \mathcal{K}} y_k. The two agree on the feasible set, because the pool balance constraint immediately above forces ∑rxr=∑kyk\sum_{r} x_r = \sum_{k} y_k.

The last two constraints contain bilinear terms: a product of the composition variable pp with a flow variable. A bilinear term is smooth and differentiable everywhere. The feasible set of this particular model is nonconvex, as the explicit midpoint counterexample below proves. A product in a formula alone does not prove that every instance has a nonconvex feasible set or exclude all possible reformulations.

This is the model, and Options 1 and 2 are inside it. Set R=∅\mathcal{R} = \emptyset: there is no tanker, so x\mathbf{x}, y\mathbf{y} and pp are never declared, the pool balance and pool fat balance disappear, the p ykp\,y_k term in the blend quality constraint is zero, and what is left is exactly the linear program of Option 1. A nonempty remote set activates the bilinear block; the data and constraints determine its feasible geometry. The model class in the table above is a consequence of the restriction, not an independent choice.

Local milk blends freely; remote milk shares one pool before reaching customers.

Step 2: Model size and active constraints

Count declared variables, equality rows, inequality rows, and lower/upper bound sides separately. A count is an implementation check, not a feasibility proof or a formula for local dimension. For a regular equality system h(x)=0h(\mathbf x)=0 with full row rank mm, the nearby equality manifold has dimension n−mn-m. Dependent rows do not each remove a dimension; singular systems need separate analysis. Inequalities and bounds may be inactive, active and independent, or active and dependent.

For example, x=0x=0 and 2x=02x=0 are two equalities in one variable and are feasible. Two inconsistent equalities in the same variable are infeasible. More inequalities than variables is also possible: only some may bind, and even active rows can be dependent. The diet example in Linear Programming has three food quantities, four nutrient inequalities, and three lower bounds.

The following tables count the actual declared rows. Here L=∣L∣L=|\mathcal L|, R=∣R∣R=|\mathcal R|, K=∣K∣K=|\mathcal K|; bound sides are not general constraint rows.

Option 1: business as usual

L=2L=2, R=0R=0, K=3K=3.

ComponentSymbolic countThis instance
continuous variables zl,kz_{l,k}LKLK6
equality rows00
linear inequality rows2K2K6
lower bound sidesLKLK6
upper bound sides00

The inequalities are demand and blend-quality requirements. This count does not identify their active set.

Option 2: a second truck

L=4L=4, R=0R=0, K=3K=3. The same equations now allow separate streams from all farms.

ComponentSymbolic countThis instance
continuous variablesLKLK12
equality rows00
linear inequality rows2K2K6
lower bound sidesLKLK12
upper bound sides00

The six inequality rows remain, while the number of shipment variables increases.

Option 3: pool the remote farms

L=2L=2, R=2R=2, K=3K=3.

ComponentSymbolic countThis instance
continuous variables z,x,y,p\mathbf z,\mathbf x,\mathbf y,pLK+R+K+1LK+R+K+112
linear equality rows11
nonlinear equality rows11
linear inequality rowsKK3
nonlinear inequality rowsKK3
lower bound sidesLK+R+K+1LK+R+K+112
upper bound sidesK+1K+14

There are 16 bound sides: one lower side for every variable, one upper side for each yky_k, and one upper side for pp. The yky_k upper bound is implied by nonnegative local flows and the demand row, but is explicitly declared in this implementation. The same number of variables as Option 2 does not imply the same feasible geometry or difficulty. The ordering proof below compares feasible plans directly.

Activity. Predict each count before running the actual Pyomo counter. Reconcile any disagreement by identifying the exact variable, row, or bound side.

Step 3: Pyomo implementation

One function, create_milk_model(local, pooled), and the two arguments are the two halves of the question from Step 1:

Optioncall
1. Business as usualcreate_milk_model(local_farms, [])
2. Buy a second truckcreate_milk_model(all_farms, [])
3. Pool the remote farmscreate_milk_model(local_farms, remote_farms)

The short add_pool_block helper is called by this builder; it is the actual pool implementation used in every solve below. There is no second model builder. Farms in local blend freely; farms in pooled share one tanker. If pooled is empty the pool variables are never declared and Pyomo is handed a linear program --- the code reduces the same way the mathematics did in Step 1.

Units. Milk here is measured in generic units, so the notebook declares a milk unit and a USD currency and hangs them on every Param and Var. Fat content stays dimensionless, because it is a mass fraction. The builder ends with assert_units_consistent, which is the part that earns the declaration: it is what would catch a price or a cost mixed into a constraint that balances amounts of milk. It cannot catch everything: fat content is dimensionless, so a fat balance and a milk balance carry the same units.

The optional fat_data argument supplies a new farm-assay dictionary for sensitivity experiments; omitting it uses the original data. The pool composition bounds are calculated from the same model parameters, so a changed assay also changes the valid mixture range. assert_units_consistent checks dimensions when called. It does not test feasibility, data validity, or optimality.

def add_pool_block(m):
    """Add the shared-composition block to the already declared farm/customer data."""
    # Amounts use the same milk unit as customer demands.
    m.x = pyo.Var(m.R, domain=pyo.NonNegativeReals, units=u.milk)
    m.y = pyo.Var(m.K, bounds=lambda b, k: (0, b.demand[k]), units=u.milk)
    m.p = pyo.Var(bounds=(min(pyo.value(m.fat[r]) for r in m.R),
                         max(pyo.value(m.fat[r]) for r in m.R)))
    @m.Constraint()
    def pool_balance(b):
        return sum(b.x[r] for r in b.R) == sum(b.y[k] for k in b.K)
    # Using sum_R x or sum_K y here agrees because of pool_balance.
    @m.Constraint()
    def pool_quality(b):
        return sum(b.fat[r] * b.x[r] for r in b.R) == b.p * sum(b.x[r] for r in b.R)
def create_milk_model(local, pooled, fat_data=None):
    """Create the milk blending/pooling model in Pyomo

    One model covers all three options. The only thing that changes is which
    farms are reachable, and which of them must share the single tanker:

        Option 1  local=local_farms, pooled=[]            business as usual
        Option 2  local=all_farms,   pooled=[]            a second truck
        Option 3  local=local_farms, pooled=remote_farms  one truck, one pool

    Farms in `local` blend freely: their milk reaches each customer as its own
    stream z_{l,k}. Farms in `pooled` share one tanker, so their milk is first
    mixed into a single stream of composition p and only then blended. If
    `pooled` is empty there is no tanker, the pool variables are never
    declared, and every remaining term is linear -- the model is an LP.

    Arguments:
        local: list of farm names whose milk blends freely
        pooled: list of farm names whose milk must share one tanker

    Returns:
        m: Pyomo concrete model
    """
    m = pyo.ConcreteModel("Milk blending and pooling")

    # Freely blended farms, L in the notes
    m.L = pyo.Set(initialize=local)

    # Pooled farms, R in the notes. Empty for Options 1 and 2.
    m.R = pyo.Set(initialize=pooled)

    # All farms sourced from, L union R
    m.S = pyo.Set(initialize=list(local) + list(pooled))

    # Customers, K in the notes
    m.K = pyo.Set(initialize=customer_names)

    # Fat fraction of the milk from farm s, phi_s [dimensionless]
    fat_values = fat if fat_data is None else fat_data
    m.fat = pyo.Param(m.S, initialize={s: fat_values[s] for s in m.S})

    # Purchase cost per unit from farm s, kappa_s [USD/milk]
    m.cost = pyo.Param(m.S, initialize={s: cost[s] for s in m.S}, units=u.USD / u.milk)

    # Price paid per unit by customer k, pi_k [USD/milk]
    m.price = pyo.Param(m.K, initialize=price, units=u.USD / u.milk)

    # Maximum demand of customer k, d_k [milk]
    m.demand = pyo.Param(m.K, initialize=demand, units=u.milk)

    # Minimum fat fraction customer k accepts, phi_min_k [dimensionless]
    m.min_fat = pyo.Param(m.K, initialize=min_fat)

    # Freely blended milk from farm l to customer k, z_{l,k} [milk]
    m.z = pyo.Var(m.L, m.K, domain=pyo.NonNegativeReals, units=u.milk)

    # Only pooled options contain the shared-composition variables and rows.
    if len(m.R) > 0:
        add_pool_block(m)

    # Helper expressions, written so the constraints below read the same way
    # whether or not a pool exists.
    def pooled_milk(b, k):
        return b.y[k] if len(b.R) > 0 else 0.0

    def pooled_fat(b, k):
        return b.p * b.y[k] if len(b.R) > 0 else 0.0

    # Maximize profit [USD]
    @m.Objective(sense=pyo.maximize)
    def profit(b):
        revenue_and_cost_local = sum(
            (b.price[k] - b.cost[l]) * b.z[l, k] for l in b.L for k in b.K
        )
        if len(b.R) == 0:
            return revenue_and_cost_local
        return (
            revenue_and_cost_local
            + sum(b.price[k] * b.y[k] for k in b.K)
            - sum(b.cost[r] * b.x[r] for r in b.R)
        )

    # Deliveries cannot exceed each customer's demand [milk]
    @m.Constraint(m.K)
    def demand_limit(b, k):
        return sum(b.z[l, k] for l in b.L) + pooled_milk(b, k) <= b.demand[k]

    # Each delivery meets its fat spec. BILINEAR when a pool exists. [milk]
    @m.Constraint(m.K)
    def blend_quality(b, k):
        fat_delivered = pooled_fat(b, k) + sum(b.fat[l] * b.z[l, k] for l in b.L)
        milk_delivered = sum(b.z[l, k] for l in b.L) + pooled_milk(b, k)
        return fat_delivered >= b.min_fat[k] * milk_delivered

    # Raises UnitsError if any constraint or the objective is inconsistent
    assert_units_consistent(m)

    return m
def model_size(m, label):
    """Count declared rows and bound sides; do not infer local dimension from counts."""
    variables = list(m.component_data_objects(pyo.Var, active=True))
    rows = list(m.component_data_objects(pyo.Constraint, active=True))
    linear = lambda row: row.body.polynomial_degree() in (0, 1)
    print(label)
    print(f"  continuous variables      {len(variables):3d}")
    print(f"  linear equality rows      {sum(c.equality and linear(c) for c in rows):3d}")
    print(f"  nonlinear equality rows   {sum(c.equality and not linear(c) for c in rows):3d}")
    print(f"  linear inequality rows    {sum(not c.equality and linear(c) for c in rows):3d}")
    print(f"  nonlinear inequality rows {sum(not c.equality and not linear(c) for c in rows):3d}")
    print(f"  lower bound sides         {sum(x.lb is not None for x in variables):3d}")
    print(f"  upper bound sides         {sum(x.ub is not None for x in variables):3d}\n")
# The farm partition selects the physical transport restriction.
m1 = create_milk_model(local_farms, [])
m2 = create_milk_model(all_farms, [])
m3 = create_milk_model(local_farms, remote_farms)

Option 1: business as usual

model_size(m1, "Option 1: local farms only")
Option 1: local farms only
  continuous variables        6
  linear equality rows        0
  nonlinear equality rows     0
  linear inequality rows      6
  nonlinear inequality rows   0
  lower bound sides           6
  upper bound sides           0

Option 2: a second truck

model_size(m2, "Option 2: all farms, one truck each")
Option 2: all farms, one truck each
  continuous variables       12
  linear equality rows        0
  nonlinear equality rows     0
  linear inequality rows      6
  nonlinear inequality rows   0
  lower bound sides          12
  upper bound sides           0

Option 3: pool the remote farms

The pool block is the only part of the builder that Options 1 and 2 skip. Its two equality constraints are exactly the two that Step 2 counted.

model_size(m3, "Option 3: remote farms pooled")
Option 3: remote farms pooled
  continuous variables       12
  linear equality rows        1
  nonlinear equality rows     1
  linear inequality rows      3
  nonlinear inequality rows   3
  lower bound sides          12
  upper bound sides           4

Step 4: Analyze results

One model uses one report function. The pool rows appear only when a pool exists. Using Ipopt throughout holds the solver family fixed, while model restrictions and initialization can still change the returned point. LP and nonlinear results need feasibility and termination checks; global certification requires an appropriate bound or proof.

solver = pyo.SolverFactory("ipopt")


def solve_and_report(m, title, opt=None):
    """Solve one option and print the supplier and customer tables.

    Arguments:
        m: a Pyomo concrete model from create_milk_model
        title: heading printed above the tables
        opt: solver to use; defaults to Ipopt with no options set

    Returns:
        the operating profit at the returned point
    """
    opt = solver if opt is None else opt
    results = opt.solve(m)
    assert pyo.check_optimal_termination(results), f"Solve failed for {title}"

    pooled = len(m.R) > 0

    print(f"{title}")
    if pooled:
        print(f"  pool composition p = {pyo.value(m.p):6.4f}")
    print(f"  profit             = {pyo.value(m.profit):,.2f}\n")

    # One row per farm: what its milk cost, and where it went.
    rows = []
    for s in m.S:
        row = {"fat": pyo.value(m.fat[s]), "cost": pyo.value(m.cost[s])}
        for k in m.K:
            row[k] = pyo.value(m.z[s, k]) if s in m.L else 0.0
        if pooled:
            row["Pool"] = pyo.value(m.x[s]) if s in m.R else 0.0
        rows.append(row)
    print("  Supplier report")
    display(pd.DataFrame(rows, index=list(m.S)).round(4))

    # One row per customer: what was delivered, and at what fat fraction.
    rows = []
    for k in m.K:
        row = {"min_fat": pyo.value(m.min_fat[k]), "demand": pyo.value(m.demand[k])}
        for l in m.L:
            row[l] = pyo.value(m.z[l, k])
        total = sum(pyo.value(m.z[l, k]) for l in m.L)
        fat_out = sum(pyo.value(m.z[l, k]) * pyo.value(m.fat[l]) for l in m.L)
        if pooled:
            row["Pool"] = pyo.value(m.y[k])
            total += pyo.value(m.y[k])
            fat_out += pyo.value(m.y[k]) * pyo.value(m.p)
        row["Total"] = total
        row["fat delivered"] = fat_out / total if total > 0 else np.nan
        rows.append(row)
    print("  Customer report")
    display(pd.DataFrame(rows, index=list(m.K)).round(4))

    return pyo.value(m.profit)

Option 1: business as usual

profit_1 = solve_and_report(m1, "Option 1, local farms only")
Option 1, local farms only
  profit             = 81,000.00

  Supplier report
Loading...
  Customer report
Loading...

Both local farms are used. All three blend-quality constraints bind in the reported baseline. The LP solution is checked numerically; its convexity permits a global certificate when the necessary feasibility and dual conditions hold. A solver name or termination message alone is not that certificate.

Option 2: a second truck

profit_2 = solve_and_report(m2, "Option 2, all farms, one truck each")
Option 2, all farms, one truck each
  profit             = 122,441.18

  Supplier report
Loading...
  Customer report
Loading...

Sourcing from the remote farms is worth a great deal --- but Option 2 needs a second truck to keep the two remote supplies separated in transit. Note also that the local farms are displaced entirely, and that Customer 2 is delivered milk richer than it requires. That is product giveaway: the optimizer hands over quality because the alternative costs more.

Option 3: pool the remote farms

This is the only one of the three that is hard, and the rest of this step is about why.

nlp_solver = pyo.SolverFactory("ipopt")

nlp_solver.options["bound_frac"] = 0.01
profit_3 = solve_and_report(m3, "Option 3, pooled, bound_frac = 0.01", nlp_solver)
Option 3, pooled, bound_frac = 0.01
  pool composition p = 0.0330
  profit             = 102,833.33

  Supplier report
Loading...
  Customer report
Loading...

Solve it twice.

Ipopt’s bound_frac sets a relative interior distance for initial bound adjustment, together with the absolute-distance option bound_push. It can change the initial values of several variables without changing the model. Solve with two values and compare the returned feasible plans. See the official Ipopt initialization options.

nlp_solver.options["bound_frac"] = 0.5
m3_alt = create_milk_model(local_farms, remote_farms)
profit_3_alt = solve_and_report(
    m3_alt, "Option 3, pooled, bound_frac = 0.5", nlp_solver
)
Option 3, pooled, bound_frac = 0.5
  pool composition p = 0.0450
  profit             = 101,392.15

  Supplier report
Loading...
  Customer report
Loading...

Activity

Same model, same solver, same tolerances. One option changed, and it only affects where the solver starts. Which of the two answers is right, and how would you know?

Why: fix pp and look.

Fixing pp makes every remaining term linear. The sweep solves an LP at each sampled composition. Three labeled peak candidates occur at 0.033, 0.040, and 0.045; a finite grid by itself is not a proof that it found every local or global optimum.

The profile can jump at p=0.045p=0.045. Below that value, Customer 1 cannot receive pooled milk: its minimum fat is 0.045, the richest local farm has exactly that fraction, and every other available stream is leaner. At p=0.045p=0.045, pooled milk can serve Customer 1. The code computes the left-branch limit by fixing p=0.045p=0.045 while retaining y1=0y_1=0, and separately records the near-left sample at 0.045−10−70.045-10^{-7}. These are different quantities, and solver tolerances matter near the switch.

Do not predict the returned solution from the closest scalar p0p_0. The full initial point has twelve coordinates. The max_iter=0 probes below report the bound-adjusted pp for two settings; the main runs report where the solver ends. Reproduce the complete initialization and settings when comparing basins.

# ---------- SOLVE ----------------------------------------------------------
# Fix p and every remaining term is linear: what is left is an LP, one per
# value of p. Build the Pyomo model ONCE and re-fix p between solves --
# rebuilding it at every grid point costs far more than the solves do.
#
# The grid is split at the two customer fat requirements that fall strictly
# inside the range of p, so a sampled curve does not join across a possible switch. Each
# segment stops just short of its right-hand breakpoint, so nothing draws a
# line across a jump that is not there.

# The model's own bounds on p: a pool is no richer than its richest input and
# no leaner than its leanest.
p_lo = min(fat[r] for r in remote_farms)  # 0.033
p_hi = max(fat[r] for r in remote_farms)  # 0.050

# Derived from the data, not hard-coded, so the sweep follows the instance if
# the instance ever changes.
breaks = sorted({v for v in min_fat.values() if p_lo < v < p_hi})  # 0.040, 0.045

m_sweep = create_milk_model(local_farms, remote_farms)


def profit_at_fixed_p(p_value):
    """Solve the pooling model with the pool composition p fixed. This is an LP."""
    m_sweep.p.fix(p_value)
    status = solver.solve(m_sweep)
    if not pyo.check_optimal_termination(status):
        return np.nan
    return pyo.value(m_sweep.profit)


eps = 1e-7
edges = [p_lo] + breaks + [p_hi]
segments = []
for lo, hi in zip(edges[:-1], edges[1:]):
    grid = np.linspace(lo, hi - eps, 400)
    segments.append((grid, np.array([profit_at_fixed_p(p) for p in grid])))

# The right-hand end of the last segment IS attained, so include it.
grid, vals = segments[-1]
segments[-1] = (np.append(grid, p_hi), np.append(vals, profit_at_fixed_p(p_hi)))

# Three peak candidates: the lower bound on p and each breakpoint.
maxima = [(p, profit_at_fixed_p(p)) for p in [p_lo] + breaks]

# Keep the near-left sample separate from the left-branch limiting LP.
near_left_sample = profit_at_fixed_p(breaks[-1] - eps)
# For p < Customer 1's minimum, every permitted stream is too lean
# except local Farm A, so pooled delivery to Customer 1 must be zero.
m_sweep.p.fix(breaks[-1])
m_sweep.y["Customer 1"].fix(0)
left_status = solver.solve(m_sweep)
assert pyo.check_optimal_termination(left_status)
jump_limit = pyo.value(m_sweep.profit)
m_sweep.y["Customer 1"].unfix()


# Where did the two Ipopt runs above START? `bound_frac` pushes every variable
# off its bounds before the first iteration; read that pushed-in point back by
# solving with max_iter = 0. Pyomo warns that the solve did not converge --
# it was never meant to.
def initial_p(bound_frac):
    """Ipopt's pushed-in initial value of p, for a given bound_frac."""
    probe = pyo.SolverFactory("ipopt")
    probe.options["bound_frac"] = bound_frac
    probe.options["max_iter"] = 0
    m = create_milk_model(local_farms, remote_farms)
    probe.solve(m)
    return pyo.value(m.p)


ipopt_runs = [
    {
        "label": "bound_frac = 0.01",
        "bound_frac": 0.01,
        "p_start": initial_p(0.01),
        "p_land": pyo.value(m3.p),
        "profit_land": profit_3,
    },
    {
        "label": "bound_frac = 0.5",
        "bound_frac": 0.5,
        "p_start": initial_p(0.5),
        "p_land": pyo.value(m3_alt.p),
        "profit_land": profit_3_alt,
    },
]

print(f"{sum(len(g) for g, _ in segments) + 5} LP solves (including the separate left-branch limit)")
for p_star, f_star in maxima:
    print(f"  peak candidate at p = {p_star:.3f}:  profit = {f_star:12,.2f}")
for run in ipopt_runs:
    print(
        f"  {run['label']:<20} starts at p = {run['p_start']:.6f}"
        f" and lands at p = {run['p_land']:.4f}"
    )
WARNING: Loading a SolverResults object with a warning status into
model.name="Milk blending and pooling";
    - termination condition: maxIterations
    - message from solver: Ipopt 3.13.2\x3a Maximum Number of Iterations
      Exceeded.
WARNING: Loading a SolverResults object with a warning status into
model.name="Milk blending and pooling";
    - termination condition: maxIterations
    - message from solver: Ipopt 3.13.2\x3a Maximum Number of Iterations
      Exceeded.
1206 LP solves (including the separate left-branch limit)
  peak candidate at p = 0.033:  profit =   102,833.33
  peak candidate at p = 0.040:  profit =   100,088.23
  peak candidate at p = 0.045:  profit =   101,392.15
  bound_frac = 0.01    starts at p = 0.033170 and lands at p = 0.0330
  bound_frac = 0.5     starts at p = 0.041500 and lands at p = 0.0450
# ---------- EXTRACT --------------------------------------------------------
# Pyomo objects -> plain Python. After this cell nothing below touches a model
# or a solver: the plotting cell reads `results` and nothing else, so it can be
# re-run as many times as it takes to get the labels off each other without
# paying for 1205 solves again.

results = {
    "bounds": {"p_lo": float(p_lo), "p_hi": float(p_hi)},
    "breaks": [float(b) for b in breaks],
    # One table per continuous piece of the profit function.
    "segments": [
        helper.table(pd.DataFrame({"p": g, "profit": v})) for g, v in segments
    ],
    "maxima": helper.table(
        pd.DataFrame(maxima, columns=["p", "profit"])
    ),
    # The value approached from the left at the jump, and never attained.
    "jump_limit": {"p": float(breaks[-1]), "profit": float(jump_limit)},
    "near_left_sample": {"p": float(breaks[-1] - eps), "profit": float(near_left_sample), "epsilon": float(eps)},
    "ipopt_runs": helper.table(pd.DataFrame(ipopt_runs)),
}

# ---------- ARCHIVE --------------------------------------------------------
# figures/results/pooling-profit-vs-p.json, committed to the repo, so a change
# to the house style can redraw this figure with no solver installed.
# `source_tag` points at the model cell above, so scripts/check_results_fresh.py
# can tell you when the model has changed and these numbers have not. A no-op
# on Colab, where there is nothing to commit to.
helper.save_results(
    "pooling-profit-vs-p",
    results,
    notebook="notebooks/1-dev/Milk-Pooling.ipynb",
    source_tag="handout:milk-pooling-model",
    source_cells=[("notebooks/1-dev/Milk-Pooling.ipynb", t) for t in ['results:pooling-data', 'handout:milk-pooling-model', 'handout:milk-pool-block', 'results:pooling-report-solve', 'results:pooling-primary-solve', 'results:pooling-alternate-solve', 'results:pooling-profile-solve', 'results:pooling-profile-extract']],
    description="Profit of the milk pooling model as a function of the pool "
    "composition p, swept as an LP over three continuous pieces, with the "
    "three labeled peak candidates and the two Ipopt runs marked.",
    solver="Ipopt via Pyomo",
);
[helper] wrote figures/results/pooling-profit-vs-p.json
# The PLOTTING function: it takes the extracted results, not the Pyomo model.
#
# This cell is tagged `figure:pooling-profit-vs-p`, which makes it the single
# source of the figure in the lecture handout. See figures/README.md;
# figures/render_from_notebook.py re-runs exactly this cell against the
# archived JSON when the house style changes, so there is no second copy of the
# plotting code anywhere.


def plot_pooling_profit_vs_p(results):
    """Profit against the pool composition p: three labeled peak candidates and a branch switch.

    Two things the usual phrasing -- "three local maxima near 0.033, 0.040 and
    0.045" -- does not say, and the figure shows:

    * The BEST of the three sits ON the lower bound of p. It is not found by
      setting a derivative to zero.
    * The profit is neither smooth nor even continuous. The kink at p = 0.040
      is Customer 3's minimum fat fraction and the JUMP at p = 0.045 is
      Customer 1's: at p = 0.045 the pool on its own can finally satisfy the
      largest, best-paying customer, and 6,000 units of demand become servable
      in one step. It is drawn as a discontinuity -- two segments, an open
      circle for the limit from the left, a filled one for the value attained
      -- because joining them with a line would draw a claim that is false.

    The two Ipopt runs are marked where they START, on the axis. The second
    starts nearer the maximum at 0.040 than the one at 0.045 and walks to
    0.045 anyway: the starting point is twelve numbers, not one.

    Greyscale: the profit curve is the only series. Nothing is keyed by colour.
    """
    segments = [helper.as_dataframe(t) for t in results["segments"]]
    maxima = helper.as_dataframe(results["maxima"])
    runs = helper.as_dataframe(results["ipopt_runs"])
    p_lo = results["bounds"]["p_lo"]
    p_hi = results["bounds"]["p_hi"]
    jump = results["jump_limit"]

    blue = "#0072B2"  # Okabe-Ito

    fig, ax = plt.subplots(figsize=(7.2, 4.6))

    for seg in segments:
        ax.plot(seg["p"], seg["profit"], color=blue, linestyle="-", linewidth=2.4)

    # --- the three local maxima -------------------------------------------
    for _, row in maxima.iterrows():
        ax.plot([row["p"]], [row["profit"]], marker="o", markersize=9,
                color="black", zorder=5, linestyle="none")

    # Open circle: the limit from the left at the jump, which is NOT attained.
    ax.plot([jump["p"]], [jump["profit"]], marker="o", markersize=9,
            markerfacecolor="white", markeredgecolor="black",
            markeredgewidth=1.6, linestyle="none", zorder=5)

    # --- direct labels on the maxima --------------------------------------
    label_offsets = [(10, 4), (-4, 14), (8, 4)]
    label_align = ["left", "center", "left"]
    for (_, row), (dx, dy), ha in zip(maxima.iterrows(), label_offsets, label_align):
        ax.annotate(
            # {,} rather than a bare comma: mathtext sets a bare comma as
            # punctuation and inserts a space, giving "$102, 833".
            f"$p = {row['p']:.3f}$\n$\\${row['profit']:,.0f}$".replace(",", "{,}"),
            xy=(row["p"], row["profit"]),
            xytext=(dx, dy),
            textcoords="offset points",
            fontsize=11,
            ha=ha,
            va="bottom",
            linespacing=1.05,
        )

    ax.annotate(
        "the best of the three is\non the LOWER BOUND of $p$",
        xy=(p_lo, maxima["profit"].iloc[0]),
        xytext=(0.05, 0.60),
        textcoords="axes fraction",
        fontsize=11,
        ha="left",
        va="center",
        arrowprops=dict(arrowstyle="->", color="black", linewidth=1.1,
                        shrinkB=8.0),
    )

    # --- where the two Ipopt runs started, and where they went -------------
    y_lo, y_hi = ax.get_ylim()
    tick = y_lo + 0.035 * (y_hi - y_lo)
    for _, run in runs.iterrows():
        ax.plot([run["p_start"]], [tick], marker="^", markersize=8,
                color="black", linestyle="none", clip_on=False, zorder=6)
        ax.annotate("$p_0$", xy=(run["p_start"], tick), xytext=(0, 9),
                    textcoords="offset points", fontsize=10, ha="center",
                    va="bottom")
    ax.annotate(
        "starts here $\\rightarrow$ lands at $0.045$,\n"
        "though $0.040$ is nearer",
        xy=(runs["p_start"].iloc[1], tick),
        xytext=(0.05, 0.30),
        textcoords="axes fraction",
        fontsize=11,
        ha="left",
        va="center",
        arrowprops=dict(arrowstyle="->", color="black", linewidth=1.1,
                        shrinkB=6.0),
    )

    # Headroom at the top for the two labels that sit above their markers.
    y_lo2, y_hi2 = ax.get_ylim()
    ax.set_ylim(y_lo2, y_hi2 + 0.13 * (y_hi2 - y_lo2))

    ax.yaxis.set_major_formatter(
        plt.FuncFormatter(lambda v, _pos: f"{v:,.0f}")
    )
    ax.set_xlabel("pool composition $p$")
    ax.set_ylabel("profit [\\$]")
    ax.set_xlim(p_lo - 0.0004, p_hi + 0.0004)
    ax.set_xticks(np.arange(0.033, 0.0501, 0.003))

    fig.tight_layout()
    ax.tick_params(colors="black")
    for spine in ax.spines.values():
        spine.set_color("black")
    return fig


fig = plot_pooling_profit_vs_p(results)

# Write media/figures/pooling-profit-vs-p.{png,pdf} -- what the lecture handout
# \includegraphics. A no-op on Colab, where there is no repo to write to.
helper.save_figure(fig, "pooling-profit-vs-p");
[helper] wrote media/figures/pooling-profit-vs-p.png and .pdf
Fixed-composition LP values, left-branch limit, and the two initialization probes.

The reported Option 3 profit is evaluated at the returned point from the specified initialization. It is not the profit at the initial point. Changing bound_frac to 0.5 returns a different plan with profit about 101,392. Both are numerical local-solver outcomes; neither termination message establishes global optimality. Record the initial values or the settings that produced them, feasibility residuals, and termination status with a nonconvex result.

Summary of the three options

One builder, three restrictions, three answers. The middle column is what was passed to create_milk_model, so this is a table of restrictions --- not a table of unrelated models.

summary = pd.DataFrame(
    [
        {
            "Option": "1. Local farms only",
            "L (blended)": ", ".join(local_farms),
            "R (pooled)": "(empty)",
            "Model class": "LP",
            "Profit": profit_1,
            "p": np.nan,
            "Catch": "leaves money on the table",
        },
        {
            "Option": "2. All farms, one truck each",
            "L (blended)": ", ".join(all_farms),
            "R (pooled)": "(empty)",
            "Model class": "LP",
            "Profit": profit_2,
            "p": np.nan,
            "Catch": "needs a second truck",
        },
        {
            "Option": "3. Remote farms pooled",
            "L (blended)": ", ".join(local_farms),
            "R (pooled)": ", ".join(remote_farms),
            "Model class": "bilinear NLP",
            "Profit": profit_3,
            "p": pyo.value(m3.p),
            "Catch": "nonconvex; bound_frac = 0.01",
        },
    ]
)
display(summary.round(4))
Loading...
# Actual solved profits, printed together for the lecture handout.
for label, value in [("1. Local farms only", profit_1),
                     ("2. All farms, separate", profit_2),
                     ("3. Pooled, bound_frac=.01", profit_3),
                     ("3. Pooled, bound_frac=.5", profit_3_alt)]:
    print(f"{label:28s} operating profit = ${value:,.2f}")
1. Local farms only          operating profit = $81,000.00
2. All farms, separate       operating profit = $122,441.18
3. Pooled, bound_frac=.01    operating profit = $102,833.33
3. Pooled, bound_frac=.5     operating profit = $101,392.15
# Regression guard. These three numbers are what this notebook is for; if a
# change to the builder moves one of them, that is the thing to notice first.
# Option 3's value is the one reached from bound_frac = 0.01 -- the other local
# solution, 101,392.16, is equally valid output from the same model.
for got, want, label in [
    (profit_1, 81_000.00, "Option 1"),
    (profit_2, 122_441.18, "Option 2"),
    (profit_3, 102_833.33, "Option 3, bound_frac = 0.01"),
    (profit_3_alt, 101_392.16, "Option 3, bound_frac = 0.50"),
]:
    assert abs(got - want) < 0.01, f"{label}: {got:,.2f} != {want:,.2f}"
    print(f"{label:<28} {got:>12,.2f}")
Option 1                        81,000.00
Option 2                       122,441.18
Option 3, bound_frac = 0.01    102,833.33
Option 3, bound_frac = 0.50    101,392.15
# Rebuild each assay case so the pool bounds use the changed farm data.
assay_rows = []
for farm_c_fat in [0.031, 0.033, 0.035]:
    assay = dict(fat)
    assay["Farm C"] = farm_c_fat
    case = create_milk_model(local_farms, remote_farms, fat_data=assay)
    opt = pyo.SolverFactory("ipopt")
    opt.options["bound_frac"] = 0.01
    status = opt.solve(case)
    assert pyo.check_optimal_termination(status)
    violation = max(max(0, pyo.value(row.lower - row.body) if row.has_lb() else 0,
                        pyo.value(row.body - row.upper) if row.has_ub() else 0)
                    for row in case.component_data_objects(pyo.Constraint))
    assert violation < 1e-3
    assay_rows.append({"Farm C fat": farm_c_fat, "returned p": pyo.value(case.p),
                       "operating profit": pyo.value(case.profit),
                       "max row violation": violation,
                       "termination": str(status.solver.termination_condition)})
display(pd.DataFrame(assay_rows).round(6))
Loading...

Feasible-plan proof of the profit ordering

Let Vi∗V_i^* denote the best achievable operating profit in Option ii, under the same prices, assays, demands and available farms, with disjoint local/remote sets and a nonempty remote set. There are no additional investment costs, stream capacities or transport penalties. Then

V1∗≤V3∗≤V2∗.V_1^*\le V_3^*\le V_2^*.
Disaggregate a pooled plan into separate streams without changing amounts, fat or operating profit.

Option 1 into Option 3. Retain every local delivery and set x=y=0\mathbf x=\mathbf y=\mathbf0. Choose any pp within its assay bounds. Both pool balances hold and the objective is unchanged. Thus every Option 1 plan has an equally profitable pooled realization.

Option 3 into Option 2. Given a feasible pooled plan, put Q=∑rxr=∑kykQ=\sum_r x_r=\sum_k y_k. If Q>0Q>0, replace its remote shipments by

zr,k=xrykQ.z_{r,k}=\frac{x_r y_k}{Q}.

The remote-farm totals are ∑kzr,k=xr\sum_k z_{r,k}=x_r, and each customer’s remote quantity is ∑rzr,k=yk\sum_r z_{r,k}=y_k. Pool fat balance gives ∑rϕrxr=pQ\sum_r\phi_r x_r=pQ, so

∑rϕrzr,k=pyk.\sum_r\phi_r z_{r,k}=p y_k.

Each customer’s amount and fat delivery stay unchanged, as do remote purchase cost and sales revenue. The original local shipments remain. This constructs a feasible Option 2 plan with the same profit. If Q=0Q=0, nonnegativity forces all xr,ykx_r,y_k to zero; take all new remote shipments zero and do not divide by QQ.

These embeddings compare optimal values, not every pair of local-solver results. They also explain what would break the proof: an extra farm-to-customer capacity, different costs, or a changed investment objective must be checked again.

A feasible midpoint test

Use only Customer 2, whose demand is 2,500 and minimum fat is 0.030; set all local shipments and other deliveries to zero.

PlanxCx_CxDx_Dy2y_2ppfat into poolfat out
A10001000.0333.3003.300
B02002000.05010.00010.000
midpoint501001500.04156.6506.225
The chord between feasible pooling plans misses the fat-balance equation at the midpoint.

Both endpoints satisfy all bounds, balances, demand and quality requirements. Their arithmetic midpoint violates pool fat balance by 0.425 milk units of fat. Hence the original feasible set is nonconvex. This is a proof about these equations and data; it does not assert that every model with a product is nonconvex or that every conceivable reformulation is impossible.

Operating value, aggregation and uncertainty

The reported pooled candidate improves on the local baseline by 21,833.33,about52.721,833.33, about 52.7% of the 41,441.18 gain available in the separate-stream LP. The separate-stream plan exceeds that pooled candidate by $19,607.84. This last difference is a comparison of reported plans; it equals the global value gap only if the pooled optimum is independently certified. None of these numbers subtracts a truck purchase price. A capital decision needs equipment and transport costs on the same time horizon.

For L=40L=40, K=500K=500, R=2R=2, the pooled formulation has LK+R+K+1=20,503LK+R+K+1=20,503 variables. The LKLK shipment block dominates for this stated modest remote-farm count. Aggregating customers reduces both KK and LKLK; grouping farms reduces LKLK. An averaged customer specification need not meet every original customer’s quality requirement. Keep disaggregation and validation in the workflow.

Fat assays, prices and demands are measured or forecast inputs. Change an assay through fat_data, rebuild, and solve with recorded starts; then check the resulting plan against the original and perturbed requirements. A change in a local-solver result can reflect both changed data and a different basin. A scenario comparison or multistart is not automatically a robust guarantee, an expected-value policy, or a global sensitivity derivative.

For a systematic upper bound, the existing global-optimization guide derives the McCormick relaxation, runs the bound and candidate calculations, and explains the remaining gap. The complete model and original data stay here.