cuopt-numerical-optimization-formulation

Numerical Optimization Formulation

Concepts and workflow for going from a problem description to a clear formulation across LP, MILP, and QP. No API code here.

What is LP / MILP / QP

• LP: Linear objective, linear constraints, continuous variables.
• MILP: Same as LP plus some integer or binary variables (e.g., scheduling, facility location, selection).
• QP: Quadratic objective (e.g., x², x·y terms — portfolio variance, least squares), linear constraints. QP support in cuOpt is currently in beta.

Identifying problem type

Property	LP	MILP	QP
Objective	Linear	Linear	Quadratic (xᵀQx + cᵀx)
Constraints	Linear	Linear	Linear + convex quadratic (inequality only) via second-order cones
Variables	Continuous	Mixed: continuous + integer/binary	Continuous
Sense	min or max	min or max	minimize only (negate to max)
Duals / sensitivity	Dual values + reduced costs	None (integer optima)	Dual values + reduced costs

If the objective is purely linear, prefer LP/MILP — do not artificially introduce quadratic terms. If any variable is integer or binary, the problem is MILP regardless of the rest.

Post-solve sensitivity (LP / QP only). Continuous LP and QP solutions expose dual values (the marginal objective change per unit a binding constraint is relaxed: where to invest to improve the outcome) and reduced costs (for a variable the optimizer left at zero, how far it must improve to enter the solution: a near-miss). MILP solutions have no duals — integer optima are not continuous, so there are none to return. Duals are also unavailable when the model includes quadratic constraints — the second-order cone path returns primal values only. See the language-specific API skills for how to retrieve them after a solve.

Required formulation questions

Ask these if not already clear:

1. Decision variables — What are they? Bounds?
2. Objective — Minimize or maximize? Linear or quadratic? For QP: any squared or cross terms (x², x·y)? If maximize a quadratic, the user must negate and minimize.
3. Constraints — Linear inequalities/equalities? Convex quadratic constraints (inequality only) are also supported, handled as second-order cones; non-convex or equality quadratic constraints are not.
4. Variable types — All continuous (LP / QP) or some integer/binary (MILP)?
5. Convexity (QP only) — For minimization, the quadratic form (matrix Q) should be positive semi-definite for well-posed problems.

Typical modeling elements

• Continuous variables — production amounts, flow, allocations, portfolio weights.
• Binary variables — open/close, yes/no (e.g., facility open, item selected).
• Linking constraints — e.g., production only if facility open (Big-M or indicator).
• Resource constraints — linear cap on usage (materials, time, capacity).
• Quadratic objective terms — variance (xᵀQx), squared error (‖Ax − b‖²), interaction terms.

Typical QP use cases

• Portfolio optimization — minimize variance subject to return and budget.
• Least squares — minimize ‖Ax − b‖² subject to linear constraints.
• Other quadratic objectives with linear constraints.

---

Problem statement parsing

When the user gives problem text, classify every sentence and then summarize before formulating. The parsing framework below applies regardless of LP / MILP / QP.

Classify every sentence as parameter/given, constraint, decision, or objective. Watch for implicit constraints (e.g., committed vs optional phrasing) and implicit objectives (e.g., "determine the plan" + costs → minimize total cost).

Ambiguity: If anything is still ambiguous, ask the user or solve all plausible interpretations and report all outcomes; do not assume a single interpretation.

🔒 MANDATORY: When in Doubt — Ask

• If there is any doubt about whether a constraint or value should be included, ask the user and state the possible interpretations.

🔒 MANDATORY: Complete-Path Runs — Try All Variants

• When the user asks to run the complete path (e.g., end-to-end, full pipeline), run all plausible variants and report all outcomes so the user can choose; do not assume a single interpretation.

Three labels

Label	Meaning	Examples (sentence type)
Parameter / given	Fixed data, inputs, facts. Not chosen by the model.	"Demand is 100 units." "There are 3 factories." "Costs are $5 per unit."
Constraint	Something that must hold. May be explicit or implicit from phrasing.	"Capacity is 200." "All demand must be met." "At least 2 shifts must be staffed."
Decision	Something we choose or optimize.	"How much to produce." "Which facilities to open." "How many workers to hire."
Objective	What to minimize or maximize. May be explicit ("minimize cost") or implicit ("determine the plan" with costs given).	"Minimize total cost." "Determine the production plan" (with costs) → minimize total cost.

Implicit constraints: committed vs optional phrasing

Committed/fixed phrasing → treat as parameter or implicit constraint (everything mentioned is given or must happen). Not a decision.

Phrasing	Interpretation	Why
"Plans to produce X products"	Constraint: all X must be produced.	Commitment; production level is fixed.
"Operates 3 factories"	Parameter: all 3 are open. Not a location-selection problem.	Current state is fixed.
"Employs N workers"	Parameter: all N are employed. Not a hiring decision.	Workforce size is given.
"Has a capacity of C"	Parameter (C) + constraint: usage ≤ C.	Capacity is fixed.
"Must meet all demand"	Constraint: demand satisfaction.	Explicit requirement.

Optional/decision phrasing → treat as decision.

Phrasing	Interpretation	Why
"May produce up to …"	Decision: how much to produce.	Optional level.
"Can choose to open" (factories, sites)	Decision: which to open.	Selection is decided.
"Considers hiring"	Decision: how many to hire.	Hiring is under consideration.
"Decides how much to order"	Decision: order quantities.	Explicit decision.
"Wants to minimize/maximize …"	Objective (drives decisions).	Goal; decisions are the levers.

Implicit objectives — do not miss

If the problem asks to "determine the plan" (or similar) but does not state "minimize" or "maximize" explicitly, the objective is often implicit. You MUST identify it and state it before formulating; do not build a model with no objective.

Phrasing / context	Likely implicit objective	Why
"Determine the production plan" + costs given (per unit, per hour, etc.)	Minimize total cost (production + inspection/sales + overtime, etc.)	Plan is chosen; costs are specified → natural goal is to minimize total cost.
"Determine the plan" + costs and revenues given	Maximize profit (revenue − cost)	Both sides of the ledger → optimize profit.
"Try to determine the monthly production plan" + workshop hour costs, inspection/sales costs	Minimize total cost	All cost components are given; no revenue to maximize → minimize total cost.

Rule: When the problem gives cost (or cost and revenue) data and asks to "determine", "find", or "establish" the plan, always state the objective explicitly (e.g., "I'm treating the objective as minimize total cost, since only costs are given."). If both cost and revenue are present, state whether you use "minimize cost" or "maximize profit". Ask the user if unclear.

Parsing workflow

1. Split the problem text into sentences or logical clauses.
2. Label each: parameter/given | constraint | decision | objective (if stated).
3. Identify the objective (explicit or implicit): If the problem says "minimize/maximize X", that's the objective. If it only says "determine the plan" (or "find", "establish") but gives costs (and possibly revenues), the objective is implicit — state it (e.g., minimize total cost, or maximize profit) and confirm with the user if ambiguous.
4. Flag implicit constraints: For each sentence, ask — "Does this state a fixed fact or a requirement (→ parameter/constraint), or something we choose (→ decision)?"
5. Resolve ambiguity by checking verbs and modals:
   • "is", "has", "operates", "employs", "plans to" (fixed/committed) → parameter or implicit constraint.
   • "may", "can choose", "considers", "decides", "wants to" (optional) → decision or objective.
6. 🔒 MANDATORY — If anything is still ambiguous (e.g., a value or constraint could be read two ways): ask the user which interpretation is correct, or solve all plausible interpretations and report all outcomes. Do not assume a single interpretation.
7. Summarize for the user: list parameters, constraints (explicit + flagged implicit), decisions, and objective (explicit or inferred) before writing the math formulation.

Parsing checklist

• Every sentence has a label (parameter | constraint | decision | objective if stated).
• Objective is identified: Explicit ("minimize/maximize X") or implicit ("determine the plan" + costs → minimize total cost; + revenues → maximize profit). Never formulate without stating the objective.
• Committed phrasing ("plans to", "operates", "employs") → not decisions.
• Optional phrasing ("may", "can choose", "considers") → decisions.
• Implicit constraints from committed phrasing are written out (e.g., "all X must be produced").
• 🔒 MANDATORY — Ambiguity: Any phrase that could be read two ways → I asked the user or I will solve all interpretations and report all outcomes (no silent single interpretation).
• Summary is produced before formulating (parameters, constraints, decisions, objective).

Example

Text: "The company operates 3 factories and plans to produce 500 units. It may use overtime at extra cost. Minimize total cost."

Sentence / phrase	Label	Note
"Operates 3 factories"	Parameter	All 3 open; not facility selection.
"Plans to produce 500 units"	Constraint (implicit)	All 500 must be produced.
"May use overtime at extra cost"	Decision	How much overtime is a decision.
"Minimize total cost"	Objective	Drives decisions.

Result: Parameters = 3 factories, 500 units target. Constraints = produce exactly 500 (implicit from "plans to produce"). Decisions = production allocation across factories, overtime amounts. Objective = minimize cost.

Implicit-objective example: A problem that asks to "determine the production plan" (or similar) and gives cost components (e.g., workshop, inspection, sales) but does not state "minimize" or "maximize" → Objective is implicit: minimize total cost. Always state it explicitly: "The objective is to minimize total cost."

---

QP rule: minimize only

QP objectives must be minimization. To maximize a quadratic expression, negate it and minimize; then negate the optimal value.

For minimization to be well-posed, the quadratic form Q should be positive semi-definite. If Q is indefinite, the problem is non-convex and may not have a finite optimum.

---

Common patterns

The remaining sections cover specific LP/MILP modeling patterns. Each is independent — read the one that matches your problem.

Piecewise-linear objectives with integer production

When modeling concave piecewise-linear profit/cost functions (e.g., decreasing marginal profit for bulk sales), the standard approach uses continuous segment variables with upper bounds equal to each segment's width. For a maximization with concave profit, the solver fills higher-profit segments first naturally.

Gotcha: If the quantity being produced is discrete (pieces, units, items), the total production variable must be INTEGER, even though segment variables can remain CONTINUOUS. Without this, the LP relaxation may yield a fractional total that produces a different (higher or lower) objective than the true integer optimum.

Pattern

x_total  — INTEGER (total production of a product)
s1, s2, … — CONTINUOUS (amount sold in each price segment, bounded by segment width)

Link: x_total = s1 + s2 + …
Resource constraints use x_total.
Objective uses segment variables × segment profit rates.

Cutting stock / trim loss problems

In cutting stock problems, waste area includes both trim loss (unused width within each cutting pattern) and over-production (excess strips produced beyond demand). Minimizing only trim loss (waste width × length per pattern) ignores over-production and yields an incorrect objective.

Correct objective

Since the total useful area demanded is a constant, minimizing waste is equivalent to minimizing total material area consumed:

minimize  sum_j (roll_width_j × x_j)

where x_j is the length cut using pattern j. The waste area is then:

waste = total_material_area − required_useful_area

where required_useful_area = sum_i (order_width_i × order_length_i).

Gotcha

Using sum_j (waste_width_j × x_j) as the objective only captures trim loss — the unused strip within each pattern. It does not penalize over-production of an order. The solver will over-produce narrow orders to fill patterns efficiently, but that excess material is still waste. Always use total material area as the objective.

Goal programming (preemptive / lexicographic)

Goal programming optimizes multiple objectives in priority order. Implement it as sequential solves — one per priority level.

Formulation pattern

1. Hard constraints — capacity limits, non-negativity, etc. These hold in every phase.
2. Goal constraints — for each goal, introduce deviation variables (d⁻ for underachievement, d⁺ for overachievement) and write an equality: expression + d⁻ − d⁺ = target.
3. Solve sequentially by priority:
   • Phase 1: minimize (or maximize) the relevant deviation for the highest-priority goal.
   • Phase k: fix all higher-priority deviations at their optimal values, then optimize priority k's deviation.

Variable types in goal programming

Deviation variables (d⁻, d⁺) and slack/idle-time variables are always continuous. However, decision variables must still be INTEGER when they represent discrete/countable quantities (units produced, vehicles, workers, etc.). Do not let the presence of continuous deviation variables cause you to make all variables continuous — the integrality of decision variables directly affects feasibility and objective values.

Multi-p

...