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 *