Problem
Core problem representation with variables, constraints, and objective
Core problem representation with variables, constraints, and objective
Central data structure holding the optimization problem definition.
ProblemProperties Struct:
- Convexity classification (Convex, Nonconvex, NotSet)
- Problem type flags (MINLP, MIQP, MILP, NLP, etc.)
- Variable counts by type (real, binary, integer, auxiliary)
- Constraint counts by type (linear, quadratic, nonlinear)
SpecialOrderedSet Struct:
- SOS1 (at most one variable nonzero) or SOS2 (contiguous nonzeros)
- Variables and optional weights
Problem Class:
- allVariables, realVariables, binaryVariables, etc.
- linearConstraints, quadraticConstraints, nonlinearConstraints
- objectiveFunction (linear, quadratic, or nonlinear)
- Sparsity patterns for Jacobian and Hessian
- Feasibility bound propagation (FBBT) for tightening bounds
Key Methods:
- add(): Add variables, constraints, objective
- finalize(): Compute properties and sparsity patterns
- getMostDeviatingNumericConstraint(): Find worst violation
- createCopy(): Clone for reformulation
Algorithm
Sparsity Pattern Extraction (getConstraintsJacobianSparsityPattern): Identifies nonzero structure for efficient derivative computation:
Jacobian ∂g_i/∂x_j: sparse pattern for AD evaluation Used by NLP solvers (Ipopt) and for hyperplane construction.
Complexity: $O(nnz)$ where nnz = number of variable appearances in constraints
References:
- Belotti et al. (2009) - Branching and bounds tightening techniques
- ESH (Extended Supporting Hyperplane) uses this for cut generation
- McCormick (1976) - Convex relaxations via factorable functions
See Also
- Solver.h for problem loading via setProblem()
- ReformulatedProblem for auxiliary variable introduction
Source
Header file: `src/Model/Problem.h`