MIQP FAQ: Mixed-Integer Quadratic Programming Basics

An MIQP includes at least one integer or binary decision variable and at least one quadratic term in the objective function, while all constraints remain linear. The quadratic term in the objective typically represents squared deviations, variance-like risk measures, or pairwise interactions between decision variables. 

Technical distinction: If all variables are continuous (no integers), the problem is a quadratic program (QP). If the model has integer variables but a linear objective and linear constraints, it is a mixed-integer linear program (MILP). If the model has integer variables and quadratic terms appear in the constraints, it becomes a mixed-integer quadratically constrained program (MIQCP), which is a more complex problem class. MIQP sits between MILP and MIQCP: it has integer variables and a quadratic objective, but all constraints remain linear. 

This distinction is important for both modeling and computational complexity: 

• MIQP (Mixed-Integer Quadratic Programming): Integer variables + quadratic objective + linear constraints 

• MIQCP (Mixed-Integer Quadratically Constrained Programming): Integer variables + quadratic constraints (objective may be linear or quadratic) 

MIQCP problems are generally more challenging to solve than MIQP problems because quadratic constraints create additional nonlinear feasible regions. Common MIQCP applications include the pooling problem in petrochemicals, problems with ratio constraints, and certain pricing models. In contrast, MIQP typically models optimization problems where the nonlinearity appears naturally in the objective (such as minimizing variance or deviation), while operational constraints remain linear. 

When modeling your problem, if the quadratic relationships describe what you’re trying to optimize (cost, risk, deviation), they belong in the objective, making it MIQP. If quadratic relationships describe physical or logical restrictions (blending ratios, physics equations, nonlinear capacity limits), they belong in constraints, making it MIQCP. 

MILP is often preferred when a linear approximation is accurate enough and keeps the model tractable. MIQP becomes useful when linearization would: 

• Distort the decision: The true objective penalty is inherently curved (for example, variance, risk aversion, or quadratic cost structures) 

• Require excessive approximation overhead: Many additional variables and constraints would be needed to approximate the curvature acceptably 

• Miss important economic relationships: Pairwise interactions or economies/diseconomies of scale that are naturally quadratic 

A practical guideline: if the quadratic term represents a performance metric stakeholders already track (portfolio variance, deviation from target, smoothness), MIQP can encode that metric more directly and accurately than linear proxies. However, if a piecewise-linear approximation is sufficient and simpler to explain, MILP may be preferable. 

MIQP appears across many industries: 

• Finance: Portfolio selection with mean-variance optimization and limits on the number of assets or trades 

• Energy: Unit commitment or generation scheduling with quadratic generation costs and discrete on/off decisions 

• Manufacturing: Production planning with quadratic inventory or backlog penalties, combined with discrete batch or setup decisions 

• Workforce and operations: Assignment or scheduling with quadratic smoothness penalties (avoiding large workload variations) combined with discrete assignment choices 

• Transportation and logistics: Vehicle routing or network design with quadratic congestion or imbalance costs 

• Product design: Component selection problems with quadratic performance deviation penalties 

These examples share a common structure: combinatorial yes/no or integer decisions in the constraints, coupled with a curved trade-off captured in the objective function. 

Quadratic terms in the objective typically encode: 

• Risk and diversification: Minimizing portfolio variance (a quadratic function of asset weights and covariances) to control concentration risk 

• Deviation penalties: Penalizing squared deviations from demand, quality targets, or service levels (quadratic penalties grow faster than linear ones, discouraging large deviations) 

• Smoothness and stability: Penalizing abrupt changes in resource levels, production rates, or staffing across time periods (squared differences between consecutive periods) 

• Interaction effects: Capturing that two choices together have synergistic or conflicting effects on cost or performance 

When communicating to stakeholders, describe the quadratic component as encoding a preference for balanced, stable, or diversified plans, rather than as a mathematical abstraction. The quadratic structure mathematically formalizes the intuition that “large deviations or imbalances are disproportionately undesirable.” 

Not necessarily, though it can be. Integer variables create combinatorial complexity, and the quadratic objective adds nonlinearity. However, computational difficulty depends heavily on: 

• The number and structure of integer variables: Tightly constrained integer variables may limit the search space favorably 

• The structure of the quadratic objective: How strongly the quadratic terms couple variables together 

• Convexity of the quadratic objective: Convex quadratic objectives enable stronger algorithmic techniques 

• Problem scaling and bounds: Tighter variable bounds and well-scaled data reduce solver effort 

Modern solvers like Gurobi have specialized algorithms for MIQP that can handle many practical instances efficiently, particularly when the quadratic objectiveis convex. In some cases, a well-formulated MIQP may solve faster than a heavily linearized MILP approximation with many additional variables. 

The distinction between convex and nonconvex quadratic objectives is critical: 

• Convex MIQP: The quadratic objective has a “bowl-shaped” structure (technically, the Hessian matrix of the quadratic form is positive semidefinite). Convex objectives create a single global trade-off surface without local optima in the continuous relaxation. This enables solvers to use stronger bounding techniques, and provides better optimization guarantees. 

• Nonconvex MIQP: The quadratic objective may have “saddle points” or multiple local optima in the continuous relaxation. This significantly increases computational complexity, as solvers must work harder to guarantee global optimality. 

Practical implications: 

• Convex MIQP is generally the preferred modeling target when the problem allows it 

• Common convex formulations include minimizing sum of squares (deviations, tracking errors) and mean-variance portfolio optimization with positive semidefinite covariance matrices 

• Nonconvex MIQP may still correctly model your problem (for example, certain bilinear or interaction terms), but requires additional computational effort and careful result validation 

Gurobi can solve both convex and nonconvex MIQP problems to global optimality. If you are uncertain whether your model is convex, check the mathematical structure of your quadratic terms or use solver diagnostics. 

For MIQP formulations, modern solvers like Gurobi can provide: 

• A proven optimal solution: When solved to completion within tolerances, the solver guarantees the returned solution is optimal 

• Proof of infeasibility or unboundedness: If the problem has no feasible solution or if the objective is unbounded, the solver detects and reports this 

• Optimality gap: If you terminate early (for example, due to a time limit), the solver returns the best feasible solution found along with an optimality gap that quantifies how far this solution could be from the true global optimum 

The optimality gap is computed from the best-known solution (upper bound for minimization) and the best-known relaxation bound (lower bound for minimization). For example, a 2% gap means the current solution’s objective value is guaranteed to be within 2% of optimal. This information is essential for production decision-making, as it quantifies solution quality confidence. 

Model validation should focus on decision quality, business relevance, and robustness: 

• Backtesting: Test on historical data instances to verify decisions align with known outcomes or expert judgment 

• Sensitivity analysis: Vary key parameters (penalty weights, risk aversion, capacities, costs) systematically to assess decision stability 

• Constraint verification: Carefully audit to ensure all business rules and operational constraints are correctly encoded, especially integer restrictions 

• Comparison against baselines: Compare against simpler alternatives (a MILP approximation, heuristic rules, or historical decisions) to quantify the value added by the quadratic objective 

• Feasibility checks on adjustments: If decision-makers manually adjust the model’s recommended plan, verify that modifications maintain feasibility and re-optimize if needed 

Additionally, for models with quadratic risk or deviation terms, validate that the penalized behaviors (concentration, large deviations) genuinely align with business priorities, and that the trade-off between the linear and quadratic components reflects true organizational preferences. 

Quadratic objectives often include weight parameters that balance competing objectives (for example, minimizing cost versus minimizing risk or deviation). Common approaches for selecting these weights include: 

• Normalization and scaling: Scale weights so that marginal changes correspond to meaningful units of business KPIs (for example, currency or percentage points) 

• Calibration on historical data: Tune weights using past instances and validate with out-of-sample testing 

• Efficient frontier analysis: For problems with multiple objectives (such as cost versus risk), solve parametrically across a range of weights to generate an efficient frontier and let decision-makers select their preferred trade-off 

• Sensitivity analysis: Identify weight ranges where decisions change significantly versus ranges where decisions are stable; prefer weights in stable regions for robust planning 

The goal is not to find a single “perfect” weight, but rather to identify a defensible range of weights that yields stable and acceptable decisions. Documenting this analysis builds stakeholder confidence and ensures transparency.