CONSTRAINER: Promptable Graph-Structured Optimization via Constraint Conditioning
Organizations: Emory University · Argonne National Laboratory · Causal Dynamics Lab
Abstract
Neural methods for graph-structured optimization have achieved strong performance within individual problem classes, but are typically trained for fixed formulations, limiting reuse across related problem variants. Recent progress in foundation models has motivated shared neural backbones trained across multiple graph-structured optimization tasks; however, existing approaches primarily share instance-level representations while treating feasibility constraints implicitly. A key source of shared structure across constrained optimization problems is the constraint set itself, which often exhibits substantial overlap across tasks. We propose CONSTRAINER, a constraint-conditioned framework for graph-structured optimization that treats constraints as structured inputs. Constraint specifications are parsed into operator graphs and encoded using a graph neural network to produce invariant constraint embeddings, which condition a shared backbone model for solution prediction. We evaluate our approach on power grid optimization and mixed-integer linear programming problems, where it shows improved solution optimality and enables efficient transfer learning and generalization compared to baseline methods.
Figures & tables
| PF | ACOPF | DCOPF | DCOTS | DCTNEP | ||||||
| Method | ACPF Feas | DCPF Feas | Gap | Feas | Gap | Feas | Gap | Feas | Gap | Feas |
| GNN (CANOS) | 95.11 | 97.14 | 4.80 | 93.00 | 3.60 | 94.20 | 6.10 | 88.45 | 5.40 | 85.32 |
| GAT | 96.42 | 97.86 | 4.10 | 94.35 | 3.05 | 95.65 | 5.30 | 89.96 | 4.60 | 86.71 |
| GT (MTL) | 97.88 | 98.72 | 3.55 | 95.60 | 2.35 | 97.10 | 4.90 | 90.85 | 3.80 | 87.94 |
| CONSTRAINER | 99.03 | 99.50 | 3.01 | 96.10 | 1.50 | 99.02 | 4.50 | 91.22 | 2.90 | 88.91 |
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
| Problem | Constraint Types | Representative Equations | Class | Description |
| AC Power Flow (AC PF) | AC power balance; voltage magnitude limits; branch Ohm’s law | ; ; | NLP | Solve nonlinear AC network physics (voltages, injections, flows). |
| DC Power Flow (DC PF) | Linearized power flow; nodal power balance | ; | LP | Linear active-power-only approximation of power flow. |
| AC Optimal Power Flow (AC OPF) | AC power balance; generator limits; voltage limits; thermal limits | ; ; ; | NLP | Minimize generation cost subject to full nonlinear AC network constraints. |
| DC Optimal Power Flow (DC OPF) | Linear DC power flow; generator limits; line thermal limits | ; ; | LP/QP | Economic dispatch with linearized DC network and flow limits. |
| DC Optimal Transmission Switching (DC OTS) | Linear DC power flow; line-status binaries; thermal limits; generator limits | ; ; ; | MILP | DC OPF with binary switching of transmission elements. |
| DC Transmission Network Expansion Planning (DC TNEP) | DC power flow; build binaries; thermal limits; budget constraint; generator limits | ; ; ; | MILP | Decide which DC lines to build or upgrade under budget and DC network constraints. |
| Problem | Constraint Types | Objective Function | Type | Description |
| ATSP | Degree; Subtour elimination | ILP/MILP | Find minimum-cost Hamiltonian tour in directed graph. | |
| CVRP | Flow; Capacity; Subtour elimination | MILP | Deliver to all customers with limited vehicle capacity. | |
| CVRPTW | Flow; Capacity; Time windows; Time propagation | Same as CVRP | MILP | Serve all customers respecting time-window constraints. |
| OP | Flow; Budget; Reward linking; Subtour elimination | MILP | Maximize collected reward under travel budget. | |
| Knapsack (KP) | Weight constraint | ILP | Select items maximizing value under total weight. | |
| MVC | Edge covering: | ILP | Choose minimum vertices covering all edges. |
| Problem | Node Type | Node Features | Edge Features |
| ATSP | City | Random ID feature (symmetry breaking) | Asymmetric distance / cost matrix |
| CVRP | Customer / Depot | Demand, depot indicator, random ID | Distance / travel cost |
| CVRPTW | Customer / Depot | Demand, time window , service time, depot flag | Distance / travel time |
| OP (Orienteering) | Location | Prize / reward, random ID | Distance / travel cost |
| KP (Knapsack) | Item | Weight, value | – |
| MVC (Min Vertex Cover) | Graph node | Random ID, optional degree | Binary adjacency |
| Problem | Node Features | Edge Features |
| ACPF | Bus voltage bounds , bus type (PQ/PV/Slack), base kV; Load demand ; Fixed generator injections | Line/transformer resistance , reactance , line charging , thermal limits , angle difference bounds , tap ratio, phase shift |
| ACOPF | Bus voltage bounds and type; Generator limits , cost coefficients , voltage setpoint ; Load ; Shunt parameters | Line/transformer parameters , charging susceptance, thermal limits (rate A/B/C), tap ratio, phase shift, angle difference bounds |
| DCOPF | Reference bus indicator; Generator limits and cost; Active load | Line susceptance and thermal limits |
| DCOTS | Reference bus indicator; Generator limits and cost; Active load | Line susceptance and thermal limits; binary line switching variable (on/off) |
| DCTNEP | Reference bus indicator; Generator limits and cost; Active load | Candidate line susceptance and thermal limits; binary line construction variable with investment cost |
| Method | Training time (hr) | Inference (ms / instance) |
| OPTFM | 0.31 | 1230 |
| GOAL | 0.32 | 334.6 23.8 |
| CONSTRAINER | 0.26 | 325.0 17.6 |
| Problem size (nodes) | Inference time (ms) |
| 100 | 60.1 |
| 200 | 69.2 |
| 500 | 345.8 |
| Constraint Type | Geometric Object | Invariances to Learn | Contrastive Signal | Positive Pair Construction | Negative Pair Construction |
| Linear Equality | Hyperplane | Scaling invariance; parallelism; translation; redundancy | Identify equivalent hyperplanes | Rescale ; add redundant copies; reorder variables | Rotate normal; shift ; inconsistent systems |
| Linear Inequality | Half-space | Tightness ordering; half-space orientation; subset relations | Ordered distances based on looseness/tightness | Generate looser/tighter ; same normal direction | Reverse inequality; change normal; produce disjoint regions |
| Affine Constraint | Shifted subspace | Affine transform invariance; equivalence of same geometry | Close embeddings for affine-equivalent forms | Apply ; add dummy variables | Non-parallel normals; incompatible affine offsets |
| Box Constraint | Hyperrectangle | Nesting; axis-aligned invariance; independent dims | Encode bounding hierarchy | Nested boxes; reorder dimensions | Disjoint boxes; rotated boxes; contradictory bounds |
| Integer Constraint | Lattice | Relaxation equivalence; parity structure; modular patterns | Integer relaxed hull (close but distinct) | Integer vs continuous versions; parity vs equivalent parity | Arbitrary continuous sets; incompatible mod classes |
| Logical Big-M | Union of polyhedra; disjunctions | Branch invariance; M-insensitivity; piecewise geometry | Capture branch semantics rather than algebra | Same implication w/ different ; reordering binary vars | Different logical semantics; huge destroying geometry |
| PF | ACOPF | |||
| Case | ACPF Feas | DCPF Feas | Gap | Feas |
| Case118 | 99.03 | 99.50 | 3.01 | 96.10 |
| Case300 | 98.70 | 99.10 | 3.30 | 95.40 |
| Case500 | 97.90 | 98.60 | 6.70 | 93.00 |
| Case2000 | 94.80 | 96.10 | 16.10 | 88.00 |
| Method | 100 nodes | 500 nodes | 1000 nodes |
| GOAL | 0.91% | 2.37% | 2.17% |
| OPTFM | 0.97% | 3.19% | 3.27% |
| CONSTRAINER | 0.50% | 1.18% | 1.70% |
| Case30 | Case118 | |||
| Method | Feas | Gap | Feas | Gap |
| FSNet [ Nguyen and Donti, 2025 ] | 100 | 0.82 | 100 | 0.90 |
| CONSTRAINER (ours) | 98.20 | 2.05 | 96.10 | 3.01 |
| CONSTRAINER + FSNet L-BFGS | 100 | 1.03 | 100 | 1.39 |
| Cross-attention placement | Opt. gap on MIS |
| Layer 1 | 0.522% |
| Layer | 0.500% |
| Layer | 0.533% |
| ATSP | CVRP | CVRPTW | OP | JSSP | UMSP | MVC | KP | |
| -value | 1.3e-3 | 1.5e-3 | 4.2e-8 | 1.3e-2 | 2.0e-4 | 8.7e-10 | – | – |
| Win-rate (%) | 78 | 83 | 95 | 77 | 88 | 86 | 92 | 80 |
| Outcome | sig. | sig. | sig. | sig. | sig. | sig. | parity | parity |
| Method | Gap (%) | Time / instance |
| CONSTRAINER | 0.32 (median 0) | 53 ms |
| CP-SAT, matched time | 3.23 | 53 ms |
| CP-SAT, to reach CONSTRAINER’s quality | 0.32 | 707 ms ( ) |
| CP-SAT, to prove optimality | 0.00 | 6.1 s ( ) |
| Type | Change | |
| Numeric | coefficient / constant | 0.055 |
| coefficient / constant | 0.069 | |
| coefficient / constant | 0.084 | |
| right-hand side | 0.143 | |
| Reformulation | canonicalized (rescale, reorder, term move, slack, dummy variable) | 0.000 |
| big-M reformulation (held-out) | 0.007 |
| ATSP | CVRP | CVRPTW | OP | KP | MVC | UMSP | JSSP | |
| 3 | 4 | 7 | 4 | 1 | 3 | 3 | 4 | |
| DAG nodes | 21 | 42 | 55 | 39 | 18 | 15 | 21 | 28 |
| Encode time (ms) | 22.0 | 21.2 | 20.4 | 14.2 | 20.1 | 23.1 | 22.8 | 22.8 |
Constrained Optimization
Constrained optimization finds the best decisions while satisfying equality, inequality, resource, safety, or fairness requirements.
See all 368 papers