Overcome non-linear constraints with new design?

by

Summary

This incident stemmed from an attempt to model a multi‑shop, multi‑product optimization problem in GLPK/MathProg using linear programming, but the design introduced non‑linear constraints by multiplying two decision variables. The solver rejected the model because LP/MIP engines require all constraints to be linear.

Root Cause

The failure was caused by multiplication of two variables:

  • quantities[p] * sellToShop[p,s]
  • Both are decision variables, so their product is non‑linear
  • GLPK/MathProg does not support non‑linear expressions in MIP models
  • The design attempted to encode conditional logic (“quantity only matters if sold”) using variable multiplication instead of linearization

Why This Happens in Real Systems

Real optimization systems frequently hit this issue because:

  • Conditional logic (“if sold then quantity applies”) is not directly expressible in linear form
  • Beginners assume they can multiply variables the same way they multiply numbers
  • Binary variables tempt users to encode logic via multiplication, which is non‑linear
  • LP/MIP solvers require linearity, so any variable–variable product is invalid

Real-World Impact

This design flaw leads to:

  • Model infeasibility: solver refuses to run
  • Incorrect optimization behavior if non-linearities are hidden or approximated
  • Unbounded or meaningless solutions when constraints fail to enforce intended logic
  • Engineering delays because the model must be redesigned using linearization techniques

Example or Code (if necessary and relevant)

Below is a valid linearization pattern for linking quantity and a binary “is sold” variable:

var quantity{p,s} >= 0;
var sellToShop{p,s}, binary;

s.t. link_min{p,s}:
    quantity[p,s] >= MINQUANTITY[p] * sellToShop[p,s];

s.t. link_max{p,s}:
    quantity[p,s] <= MAXQUANTITY[p] * sellToShop[p,s];

This avoids multiplying variables and enforces:

  • If sellToShop[p,s] = 0 → quantity forced to 0
  • If sellToShop[p,s] = 1 → quantity is within allowed bounds

How Senior Engineers Fix It

Experienced engineers solve this class of problems by applying standard linearization patterns:

  • Replace variable–variable products with:
    • Big‑M constraints
    • Indicator constraints
    • Auxiliary variables
  • Model quantities as a matrix (quantity[p,s]) instead of a single vector
  • Use binary variables only to activate constraints, never inside arithmetic expressions
  • Separate revenue and cost terms to avoid global coupling errors
  • Ensure per‑product profit constraints are written independently

Typical senior‑level fixes include:

  • profit[p] = sum_s price[p,s] * quantity[p,s] - transport_cost[p]
  • transport_cost[p] = sum_s quantity[p,s]
  • profit[p] >= MINPROFIT[p]

All linear, all solver‑friendly.

Why Juniors Miss It

This class of bug is extremely common among new LP/MIP users because:

  • They think in code, not in linear algebra
  • They assume binary variables behave like booleans in programming languages
  • They expect the solver to “understand” conditional logic automatically
  • They underestimate how strict linearity requirements are
  • They try to encode logic using arithmetic instead of constraints

The key takeaway: LP/MIP modeling is about expressing logic through linear constraints, not through variable multiplication.

Leave a Comment