/cuopt-numerical-optimization-formulation

name: cuopt-numerical-optimization-formulation
version: "26.10.00"
description: LP, MILP, QP — concepts, problem-text parsing, and formulation patterns (parameters, constraints, decisions, objective). Concepts only; no API.
license: Apache-2.0
metadata:
  author: NVIDIA cuOpt Team
  tags:
    - linear-programming
    - milp
    - qp
    - formulation
    - concepts

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 pr