WorksMathematics
Valid Inequalities for Bilevel 0-1 Shortest-Path Problems
Abstract
We characterize valid inequalities for bilevel programs in which the leader makes binary decisions, and the follower solves a shortest-path problem. We exploit a dualize-and-combine reformulation and show that even with ideal formulations for the leader and the follower primal solution sets, fractional solutions may still appear in the continuous relaxation. From that reformulation, we identify that the interaction between the leader variables and the follower dual variables, which we capture through a leader-potential set, is the key structure to be convexified to guarantee that a continuous relaxation recovers the optimal value of the original problem, closing the objective gap. Furthermore, we characterize the valid inequalities for the leader-potential set through network flows, and identify a family of inequalities we name root cuts that suffice to recover the optimal value. Complementary to the structural results, we prove that the cut generation problem is NP-hard even with partially fixed coefficients and a network with two nodes and two parallel arcs. Motivated by the complexity result, we propose a constructive method to fix coefficients in the valid inequalities while preserving separation guarantees, by exploiting the network structure.
Introduction
Bilevel programs model hierarchical decisions in which a leader, at the upper level, anticipates the optimal response of a follower, at the lower level [10, 16]. In this work, we are interested in bilevel binary programs of the form
Here, represents the leader’s decisions, where is a set of binary vectors described by linear inequalities. Vector represents the follower’s decisions, and collects the coefficients of the leader’s linear objective in . The follower solves a shortest-path problem, and consists of the arc-incidence vectors of the feasible paths. The leader affects the follower’s optimization solely through arc costs that are affine in . The formulation adopts the optimistic assumption, under which ties among optimal follower paths are resolved in the leader’s favor.
Shortest-path followers as above arise in a wide range of optimization settings, and in many of these contexts, the leader naturally affects the follower’s objective. Network pricing is one such example, where a leader anticipates how users (followers) will route through a network in response to her decisions [17, 4, 7]. The same structure also arises when a combinatorial follower is represented by a finite-stage dynamic program [6], such as a decision diagram [18, 2]. In these representations, which may be exponentially large, paths through an acyclic state-transition graph encode follower solutions, and arc weights accumulate their objective values. When the follower’s feasible set is fixed, and its objective coefficients depend affinely on binary leader decisions, this yields precisely the follower structure in (1). Similarly, our setting accommodates certain interdiction models after transferring linking constraints—lower-level constraints parametric on the leader’s variables—to the follower’s objective and constructing a network reformulation based on the follower’s dynamic-programming representation. Knapsack interdiction provides such an example [8, 14, 6]. Related network formulations encode leader-dependent follower feasibility through arc capacities or represent the follower’s value function over leader decisions [21, 19].
Under common assumptions, the standard arc-flow formulation of the follower’s shortest path is ideal. Thus, traditional dualize-and-combine can be directly applied to solve the bilevel problem, enforcing follower’s optimality through primal feasibility, dual feasibility, and strong duality [7, 18, 6]. In our setting, this yields an extended single-level formulation in the leader decisions, network paths (follower’s primal), and node potentials (follower’s dual), linked by a bilinear optimality constraint. However, even with ideal descriptions of the leader and follower feasible sets, the resulting single-level relaxation can contain fractional points outside the convex hull of bilevel-feasible solutions. In other words, the relaxation may still contain fractional optimal solutions that satisfy follower’s optimality and have strictly better objective values than any feasible solution to the original problem.
While cutting-planes have demonstrated success in separating fractional solutions in general mixed-integer programming, in bilevel settings we observe an absence of methods targeting fractional points that satisfy the follower-optimality condition. Existing cut generation for mixed-integer bilevel optimization targets, in particular, points that satisfy all leader and follower constraints, including integrality, but violate follower optimality [12, 13]. When a point with a fractional leader decision already satisfies the follower-optimality condition, Tahernejad and Ralphs Tahernejad and Ralphs [20] discuss the use of standard mixed-integer linear programming cuts. Recent work by Vásquez et al. Vásquez et al. [22] derives cuts in the original variable space from networks that jointly encode the binary leader assignments and the follower’s value function, and strengthens them via network-based tilting. In contrast, our bilevel problem (1) contains a network structure only in the follower, and we explore how this structure can be leveraged to characterize the convex hull of feasible solutions. Davarnia et al. Davarnia et al. [9] convexify bilinear terms over a dual network polytope and a simplex leader to strengthen dual formulations of network interdiction. In our setting, the leader decisions interact with the follower’s dual through the arc costs, and not through bilinear terms. Furthermore, we do not assume the leader to be restricted to simplex variables.
Contributions and organization. We describe our problem setting in Section 2, and we make the following contributions in Sections 3–4.
We establish the role of leader–potential convexification in the full single-level formulation (Section 3.1). With the follower’s path polytope and the bilinear optimality constraint retained, we show that convexifying the leader–potential set makes every remaining feasible point a convex combination of feasible single-level solutions.
We characterize all valid linear inequalities to the leader–potential set (Section 3.2). Specifically, we provide necessary and sufficient conditions for the coefficients of node potential variables through network flow.
For a subclass of valid inequalities with special structures, which we call root cuts, we prove that adding them to the continuous relaxation already suffices to recover the optimal value of the original problem (Section 3.3).
We propose a constructive coefficient fixing for the node potentials enhanced by the network structure (Section 4.1), and we prove that the cut generation problem is NP-hard even with fixed node potential coefficients and a network consisting of two parallel arcs (Section 4.2).
Problem Setting
We first detail the follower’s problem in Section 2.1 and then derive the single-level reformulation of (1) via dualize-and-combine in Section 2.2.
Network assumptions and path formulation
Let be the directed graph for the follower’s problem, with distinct root and destination . We also assume to be acyclic, we allow parallel arcs and retain only nodes and arcs on paths. This preprocessing preserves all follower choices and makes and the unique source and sink, respectively. Two network examples are illustrated in Figure 1.

Figure 1. Follower networks. Arc labels give costs.
The above graph assumptions are not stringent; they naturally accommodate the representations from finite-stage dynamic programs and decision diagrams [6, 2], but also broader routing settings through equivalent representations. When we have multiple independent shortest-path followers, connecting copies of their networks in series yields a single path problem of size linear in their original size, with each path selecting one route per follower. For cyclic networks, acyclic representations preserve all optimal follower paths if every directed cycle has strictly positive cost for every . Both constructions preserve the leader’s linear objective and optimistic tie-breaking under projection. Common assumptions such as positive base costs and nonnegative tolls [7] or absence of nonpositive cost cycles [17, 5] satisfy the condition for an acyclic representation.
The follower’s path set is independent of , and its arc weights are given by , where and . For each arc , let and denote its tail and head. The node–arc incidence matrix has column , where is the unit vector indexed by node .
Recall that is the set of arc-incidence vectors of paths. By flow decomposition and acyclicity, every nonnegative unit flow is a convex combination of path-incidence vectors. Thus, the follower has a bounded ideal linear formulation and a finite optimal value for every leader assignment. In particular,
Strong-duality reformulation
In what follows, let
The constraints and describe leader feasibility and follower path-incidence vectors, respectively. The dual arc inequalities couple leader decisions and node potentials. The bilinear optimality constraint enforces strong duality and couples all three variable blocks, , and . Here, we normalize the dual node potentials by . Following from (2) and strong duality, (1) admits the following equivalent single-level formulation:
This formulation is exact for binary [18], but its continuous relaxation may have fractional extreme points. We seek valid inequalities to strengthen it.
Valid Inequalities
This section identifies which valid inequalities must be added to the relaxation of (3) to recover the bilevel optimum. Throughout this section, we assume , since otherwise (1) is infeasible and every inequality is valid. Section 3.1 shows that it suffices to convexify the set coupling leader decisions and node potentials. Section 3.2 characterizes its valid inequalities through network supplies and affine upper bounds of minimum-cost flow values over . Section 3.3 shows that the root supply suffices for the bilevel objective and establishes the limits of more general unit supplies for full convexification.
We first justify seeking a linear description of the feasible hull despite the bilinear optimality constraint. Although the extended formulation (3) introduces continuous variables, the convex hull of its feasible solutions is a polytope. This can be seen from a disjunctive programming perspective, which we formalize in the following proposition.
Proposition 1. is a polytope.
Consequently, finitely many valid linear inequalities suffice to recover the bilevel optimum from the continuous relaxation of (3). To identify a structured source of such inequalities, we first account for leader and follower integrality separately. The follower’s flow formulation already describes , and we may also replace by . As the next example shows, however, the interaction between the variable blocks can still leave fractional points outside and an objective gap.
Example 1. Let and consider two parallel arcs from to , with weights and . The network is illustrated in Figure 1. The follower’s path set is , with indicating arc . Since and , we retain only . Replacing and by their convex hulls in (3) gives for . The fractional point is feasible, but lies outside the segment joining the only binary-feasible solutions and . For the objective , it has value , whereas both binary solutions have value zero.
Let denote the follower’s optimal value for . In the example, the dual arc inequalities impose , while convexifying the leader–potential set gives the stronger inequality . This motivates studying that set and the effect of its convexification on the full formulation.
The dual network polyhedron
For fixed leader decisions, the dual arc inequalities define a dual network flow polyhedron [3]. Allowing the arc weights to depend on the leader gives the mixed-integer set
and its relaxation
We refer to as the leader–potential set, and to as its continuous relaxation. We note that structures similar to have been explored under the names dual network polytope [9] and dual network flow polyhedra [3] in different settings and with objectives distinct from ours.
Using in isolates the interaction between leader decisions and potentials. For a set in -space, write for its potential fiber. Every fiber with is nonempty, as witnessed by shortest-path costs from each node to . Moreover, for , so . The finitely many nonempty fibers of are pointed polyhedra with a common recession cone, hence is also a polyhedron.
With the bilinear optimality constraint retained, convexifying excludes every point outside . Define
Proposition 2. .
Thus every point of is a convex combination of feasible single-level solutions, and every linear objective has the same optimal value over and . This justifies focusing on valid inequalities for . Although may be nonconvex, these inequalities also strengthen the McCormick relaxation of the bilinear terms. In Example 1, adding to that relaxation even yields an ideal formulation.
Valid inequalities and network flows
We now characterize all valid inequalities for . Consider valid inequalities for of the form
With , those are precisely the valid inequalities for . Note that we assume only that the leader has a linear formulation, thus there is no structure to be exploited in generating the valid inequalities with , and one can resort to general integer-programming techniques. Our focus is on inequalities with , which account for the interaction between leader decisions and node potentials. Since , we may choose without changing the inequality. Throughout, we use this representative, so that .
All valid inequalities of interest have node potential coefficients that define valid supplies over the network. Intuitively, derives from nonnegative combinations of the follower’s dual inequalities, thus columns of . Combining these columns with nonnegative weights can therefore be viewed as assigning flows to the arcs. We define the supply cone and its associated flow sets by
For , acyclicity makes a nonempty polytope, and linear programming duality gives the finite, attained value
Proposition 3. Let satisfy . Inequality (4) is valid for if and only if and
Equivalently, for every there exists a flow certificate such that
By Proposition 3, the right-hand side of any valid inequality defines an affine upper bound for on . Since the graph is acyclic, is a polytope, and can be expressed as a minimum of finitely many affine functions of , one for each extreme point of . Although is therefore concave, we are interested in upper bounds for the function over only, which means they might imply stronger bounds at fractional leader coordinates than the function itself. For , let be the smallest concave function on bounded below by on , that is, let be the concave envelope of over .
Corollary 1. For , (4) is valid for if and only if is an affine upper bound of on .
Consequently, at every , there exists a supporting hyperplane of the hypograph of whose associated valid inequality has minimal right-hand side at among all valid inequalities with potential coefficients .
Root supply and optimality gap
The root potential is the only potential in the follower’s optimality constraint of (3), and no potential appears in the leader’s objective. This motivates studying inequalities involving only and . We show that this family suffices to recover the optimal value of the bilevel problem.
The root supply supplies one unit of flow at the root and consumes it at the target . Since , (5) gives
Thus, the associated root cuts1 have the form , where the right-hand side is an affine upper bound of the follower’s value function on . Let denote its concave envelope over . By Corollary 1, adding all root cuts to gives the closure
Lemma 1. The root closure satisfies
The projection equality implies that, for every and ,
Thus, root cuts close the gap for objectives on involving the potentials only through . This has an important consequence for problems with interdiction objectives [11], which can be formulated [8, 14, 6] as in (8) with and . Precisely, for bilevel shortest-path problems with interdiction objectives, root cuts yield an LP relaxation that recovers the optimal objective value.
More interestingly, this same family actually suffices for the general case, which we prove below. Define the relaxation
For a point of , take a convex decomposition of its leader component attaining the root envelope and a convex decomposition of its follower path component. The bound and the bilinear optimality constraint force the follower optimality gaps to zero (under the product weights), so every (positively weighted) leader–path pair is bilevel feasible.
Theorem 1. Every point of is a convex combination of bilevel-feasible leader–path pairs. Moreover, for every linear objective ,
The theorem strengthens the conclusion of Proposition 2 for the objective of interest: convexifying the entire leader–potential set is unnecessary to close the bilevel gap. The result concerns the complete family of root cuts with the bilinear optimality constraint retained; it does not assert gap closure after McCormick relaxation.
Even the complete family of root cuts can fail to describe . This limitation persists for the larger family of all unit supplies, namely for distinct nodes , joined by a directed path, as the following example shows.
Example 2 (Unit supplies are insufficient). Let and . The arcs and have cost zero. There are two parallel arcs of costs and , and two parallel arcs of costs and , as illustrated in Figure 1. The point
belongs to and satisfies every cut with a unit supply, including every root cut. Nevertheless, the inequality
is valid for and violated by this point. Its supply is .
Unit supplies contain a generator of every extreme ray of , since this cone is generated by the columns of , each of which is a unit supply. Thus even inequalities from all extreme supply directions can leave points outside unseparated.
Cut Generation
In this section, we explore the generation of linear valid inequalities (cuts) to separate a given point of a continuous relaxation of (3), possibly already strengthened by other valid inequalities. In particular, we study cut generation for the leader–potential set, construct node potential coefficients that separate fractional vertices of , and analyze the complexity of separation under partially-fixed coefficients.
Our structured approach to the single-level reformulation (3) can guide the choice of variables involved in separation. Let be an optimal solution from any continuous relaxation of . If is fractional and its active leader constraints have rank , then an inequality for alone suffices to separate it. As previously discussed, we will not concentrate on this case.
For candidates with , Proposition 2 justifies focusing on the leader–potential set. Define to be a continuous relaxation of as follows:
The proposition also shows that inequalities of the form (4) with are sufficient to separate any point in . We explore this result in the following lemma.
Lemma 2. Every extreme point satisfies , and is a vertex of .
We therefore focus on vertices of with fractional leader coordinates, which necessarily lie outside and admit a separating inequality.
Fixing node potential coefficients
Let be a vertex of with fractional leader coordinates. By Proposition 3, a cut-generating linear program (CGLP) can jointly select and the flow certificates, subject to a linear normalization fixing the coefficient scale. Its explicit formulation requires one flow certificate (6) per leader assignment, hence flow variables, and may be exponentially large. We instead construct the node potential coefficients from the arc inequalities active at , preserving the existence of a separating cut while leaving the leader coefficients to be optimized.
Proposition 3 restricts admissible to the supply cone , but does not determine which supplies admit separation at the candidate. For fixed , Corollary 1 gives the maximum attainable violation as
A separating inequality with this exists if and only if this value is positive.
For any , define its active arcs by
Connectivity and spanning trees below refer to the underlying undirected graph; each selected arc retains its original orientation.
Lemma 3. For , the active-arc graph is connected if and only if is a vertex of . In particular, it is connected at every vertex of .
Figure 2 illustrates the connected active-arc graph at a fractional vertex of .

Figure 2. Active arcs at a vertex of with and . Arc labels give costs. Solid arcs are active, and the dashed arc has slack 1. The red highlight marks a spanning tree of active arcs. The four active equalities uniquely determine .
Our construction is based on a standard geometric observation: a positive combination of full-rank active inequality rows yields an optimization direction uniquely maximized by the associated basic solution. We apply this observation to the fiber . The network structure makes the required row selection inexpensive: after eliminating , a spanning tree of active arcs provides a minimum-cardinality full-rank collection of rows. Once the active-arc graph is available, such a tree can be found by graph traversal in time, without matrix rank computations. Positive weights on its arcs then determine a supply vector ; the following lemma establishes the resulting separation guarantee.
Lemma 4. Suppose has a connected active-arc graph. Choose a spanning tree and weights for . Then
belongs to . Moreover, if and only if . In particular, this construction guarantees separation at every vertex of with fractional leader coordinates.
The weighted sum of the tree inequalities is valid for and active at , so it does not itself separate. It selects the potential coefficients; separation comes from strengthening the affine right-hand side over the discrete leader set . The guarantee concerns the existence of a cut, not its strength relative to other supply vectors.
Let be obtained from by adding finitely many valid inequalities , with affine and . Unlike for , the active-arc graph at a vertex of need not be connected. Consider first the case in which consists of two components, containing and . A spanning tree in each component fixes all differences of node potential variables, allowing only for a common shift of the potentials in . An active added cut fixes this shift whenever its total supply is nonzero. At a vertex, at least one such cut must exist; otherwise, a small shift in either direction would preserve feasibility. Thus two trees and one active added cut suffice to determine the node potentials. Figure 3 illustrates how adding a cut can produce a new fractional vertex with two active-arc components. The following proposition extends this construction to any number of components.

Figure 3. Connected components before and after adding one cut, with and potentials ordered as . Solid arcs are active, dashed arcs are inactive, and shading identifies components of the original active-arc graph. The root cut is valid since and . In (b), it is active and fixes the relative shift between and .
Proposition 4. Let be a vertex of , let be its active-arc components, with , and let index its active added cuts. The matrix
has rank . Choose a spanning tree in each component, with union , and a set indexing independent rows of . The corresponding original arc inequalities and added cuts form a minimum-cardinality full-rank collection in the node potential coordinates, excluding . For any positive weights and , the supply
belongs to . Moreover, if and only if . In particular, it admits a separating inequality whenever is fractional.
The network structure therefore keeps row selection inexpensive within each component: graph traversal selects the forest, and linearly independent active cuts fix the remaining degrees of freedom. For , no added cut is needed and the spanning-tree construction applies directly.
On a practical setting, there is strong reason to start with root supplies before attempting the constructions suggested above. By Theorem 1, root cuts suffice to close the bilevel objective gap when the bilinear optimality constraint is retained. Moreover, each root cut has the node potential coefficients of an additional arc, so adding root cuts preserves the spanning-tree construction on the augmented active graph (Lemma 4). Root cuts can therefore be pursued first while retaining an inexpensive way to select other supply vectors when needed.
Complexity of separation
Selecting a supply vector that admits separation leaves the leader variable coefficients to be determined. For fixed and a point , Corollary 1 gives the attained maximum violation as
where is an enumeration of the feasible points in . Each value can be computed by a minimum-cost flow problem. Given these values, LP (10) has only variables, but still one constraint per leader assignment. Replacing each constraint by its flow certificate (6) gives an equivalent CGLP without precomputing the values. The resulting formulation can however still be exponential in size.
We propose two ways to address the exponential size of the CGLP. With respect to the number of leader assignments, we can, for example, consider a split disjunction on one of the fractional coordinates [1]. With respect to the size of the underlying graph, we can restrict the minimum-cost flow problem to the active arcs . For a vertex of with fractional leader coordinates and a supply constructed by Lemma 4, these reductions also preserve the existence of a separating inequality. The two reductions can decrease the maximum violation compared with the original CGLP with fixed . When a linear description of is supplied, the reduced CGLP has polynomial size in that description and the active graph.
To motivate the split relaxation, we also examine the computational complexity of the separation problem for a particular fixed supply vector on a small graph. By exact separation, we mean to determine occurrence of a violation, and if so, to find a violated cut with the fixed supply vector .
Proposition 5. Membership in the root-cut closure is NP-hard, even for candidates in when and the graph consists of two parallel arcs, one with constant cost. Consequently, exact separation of root cuts and exact evaluation of are NP-hard under the same restrictions.
The proof, given in section A, reduces PARTITION to membership at . Both arc inequalities are active at the constructed candidate, so restricting to active arcs leaves the hardness construction intact. The result concerns arbitrary candidates in and also establishes hardness of general fixed-supply separation.
Exact separation therefore remains NP-hard even with an unconstrained leader and a graph consisting of two parallel arcs. The split relaxation addresses a computational difficulty that persists after graph reduction. Combined with the supply construction of Lemma 4, it retains a separating inequality at fractional vertices while admitting a CGLP of polynomial size in the supplied leader formulation and the active graph. To see this, each branch of the split disjunction is described by the given linear description of , the retained arc inequalities, and one split equation. Dualizing cut validity on each disjunction branch introduces one multiplier per row, one coefficient-matching equation per original variable, and one inequality for the right-hand side. Since the disjunction has two branches, the resulting CGLP has size polynomial in the supplied leader description and the active graph.
Conclusions
In this work, motivated by network pricing, follower’s dynamic programming formulations and certain interdiction models, we developed a polyhedral characterization of the bilevel 0–1 shortest-path problem by studying the interaction between leader decisions and follower node potentials. Network flows characterize the valid inequalities for this joint set. With the leader set convexified and the bilinear optimality constraint retained, root cuts strengthen the continuous relaxation of the problem and recover the bilevel optimum for every linear leader objective. Full convexification of the leader–potential set can require coupled supplies even after all unit-supply cuts are added.
We proposed cut generation by constructively fixing supplies. Spanning trees of active arcs yield separating supplies at vertices of with fractional leader coordinates, and active-arc components extend this construction after cuts are added. Nonetheless, we showed that exact fixed-supply separation is NP-hard even for networks with two parallel arcs. For the initial relaxation, split disjunctions and restriction to active arcs reduce the CGLP while preserving separation with the constructed supplies.
Acknowledgments
This work was funded by the FRQNT Doctoral Scholarship No. B2X-367536, and the NSERC Grants No. 2024-04051 and 2024-05059.
OpenAI Codex (GPT-6) was used to assist with literature searches, LaTeX edits, and figure generation. The authors reviewed the content as needed and take full responsibility for this manuscript.
Deferred Proofs
Polyhedrality of the single-level feasible hull
Proof of Proposition 1. Fix for which the potential constraints in (3) are feasible. Weak duality and the optimality constraint give . For each node , choose an path and a path , allowing the empty path at an endpoint. Summing the dual arc inequalities along these paths yields
Thus the feasible potentials for each fixed pair form a bounded polyhedron. Since and are finite, is a finite union of polytopes, and its convex hull is a polytope.
Effect of convexifying the dual network polyhedron
Proof of Proposition 2. It suffices to show . Taking the convex hull gives .
The inclusion follows from and . For the reverse containment in , take and choose finite convex representations
where , , , and . Since the path set is independent of the leader assignment, every pair combines a feasible follower path with dual-feasible potentials at . Weak duality then gives us for each pair . Because the candidate solution satisfies the follower’s optimality constraint and is affine, we have
For every pair with the optimality gap must vanish, that is, . Hence each positively weighted triple belongs to . Finally, the weights sum to one and satisfy
proving .
Flow characterization and fixed-supply convexification
Proof of Proposition 3. We first verify (5) and supply admissibility. For any , the potential maximization is feasible, and its linear programming dual is
Summing the balance equations gives because . Hence dual feasibility is equivalent to . If (4) is valid, its right-hand side bounds the potential objective on any fiber indexed by . Such a fiber exists because , so linear programming duality implies .
For , the recession cone of consists of nonnegative circulations. Acyclicity implies that the only such circulation is zero, so is a nonempty polytope. Strong duality now gives (5), with both optima finite and attained. Maximizing the left-hand side of (4) on each integer fiber proves the affine-upper-bound characterization. An optimal flow on that fiber supplies (6) whenever the upper bound condition holds. Conversely, any such certificate gives
proving validity.
Root supply and the optimality gap
Proof of Lemma 1. We first determine the possible values of the root potential for a fixed leader decision . Assigning each node its shortest-path cost to gives feasible potentials with . Since has no incoming arcs, decreasing only preserves feasibility. Together with weak duality, this proves
We next show that convexifying replaces this upper bound by the concave envelope of the values at integer leader decisions. Let be an enumeration of and fix . The concave envelope has the representation
Indeed, the right-hand side is a concave upper bound of the values on , and every such upper bound dominates it by concavity. The maximum is attained because the feasible weight set is nonempty and compact and each is finite. Every convex combination of points of with leader component has root potential at most the corresponding weighted sum of follower values, and hence at most . To attain this bound, choose weights maximizing (11) and, for each , let be the shortest-path potentials for arc costs . Then and , so
Decreasing every by the same nonnegative amount preserves membership in and yields every smaller value of . This proves the asserted projection of .
Finally, we compare this projection with that of the root closure. Since is concave, on . The first part of the proof therefore shows that imposing on leaves precisely the root potential values for each . By (7), this proves the equality for .
Proof of Theorem 1. Take . Choose weights attaining (11) and write with , , and . Feasibility and the affinity of give
All inequalities are equalities. Each difference is nonnegative, so it vanishes whenever . Every positively weighted pair is therefore bilevel feasible, and
This proves the convex-combination claim and bounds every linear leader objective below by the bilevel optimum. Conversely, because root cuts are valid for . The optimal values consequently coincide.
Reduction to the dual network polyhedron
Proof of Lemma 2. Let be an extreme point of . Decompose into path-incidence vectors. Weak duality gives for each path, and the optimality constraint forces equality in their weighted average. Every positively weighted path therefore gives a feasible triple with the same . Extremality forces all those paths to equal , proving .
Now suppose is a nontrivial convex combination of two points of . With fixed, the gap is affine and nonnegative on . It vanishes at the candidate, so it vanishes at both endpoints. Appending to these endpoints gives a nontrivial convex representation in , a contradiction.
Constructive supply selection
Proof of Lemma 3. If the active-arc graph of a point is connected, a displacement of node potentials preserving its arc equalities must be constant on all nodes. The normalization at makes that displacement zero. Hence the active equalities uniquely determine the node potentials from , proving that is a vertex of the fiber . If the graph is disconnected, shift every node potential in a component not containing by or by . Active equalities are preserved, and the finitely many inactive arc inequalities remain feasible for sufficiently small . These two distinct feasible node potential vectors have midpoint , contradicting fiber extremality. Finally, a nontrivial convex representation within a fiber also gives one in , so every vertex of is a fiber vertex.
Proof of Lemma 4. The vector is the supply of the nonnegative flow with value on and zero elsewhere. It is nonzero because a DAG has no nonzero nonnegative circulation. Summing the selected inequalities gives the valid inequality
with equality at the candidate.
The node potentials uniquely maximize on . To see this, fix and take any . The slack of the aggregated inequality is
The candidate attains the upper bound because every arc of is active there. Any potential vector attaining the same bound must make every slack in the sum zero, since the slacks are nonnegative and all weights are strictly positive. Hence for every , so the displacement has equal values at the endpoints of every tree arc. Connectivity makes this displacement constant on all nodes, and makes the constant zero. In other words, must be equal to .
Applying the convex-combination representation in (11) to gives the attained identity
Indeed, any convex combination of points of has objective at most the corresponding weighted integer-fiber values, and maximizing weights together with maximizing fiber potentials attain equality. Since , (12) gives . Equality holds if the candidate belongs to . Conversely, if equality holds, an attaining hull potential also maximizes the objective over , so uniqueness makes it .
The difference is the maximum attainable violation defined in (9). We have shown that this difference is nonnegative and vanishes precisely when the candidate belongs to . A vertex of in must itself belong to , since all positively weighted points in a convex representation from must equal that vertex. A vertex with fractional leader coordinates is therefore outside , proving the final assertion.
Proof of Proposition 4. A displacement preserving all active arc equalities is constant on each component and zero on after imposing . Write its remaining component values as . It preserves the active added cuts precisely when . If had rank less than , a nonzero such displacement of sufficiently small magnitude in either direction would preserve every constraint of , contradicting the vertex assumption. Thus rank .
The selected forest has arcs and forces componentwise constancy. The selected rows of force all remaining component shifts to vanish. Consequently, the selected rows have full rank in the free potential coordinates, which is the minimum possible cardinality. This also covers , when no added row is needed.
Each selected potential coefficient belongs to , so their positive combination also belongs to . Choose a nonnegative flow representing each selected cut coefficient and aggregate these flows with the selected arc flows using the prescribed positive weights. Full rank ensures that at least one selected coefficient is nonzero, so the aggregate flow is nonzero. Acyclicity precludes it from being a circulation, proving .
The weighted sum of the selected inequalities is
It is valid for and active at the candidate. Equality in the fiber at forces every selected inequality to be active, and full rank makes its unique solution. Hence uniquely maximizes over . Because , the attained identity (12) gives exactly the same zero-violation equivalence as in the preceding proof. Finally, a vertex of with fractional leader coordinates cannot belong to , since and its leader coordinates are binary.
Complexity of separation
Proof of Proposition 5. Assume rational data with binary encoding. Let be positive integer weights. The Partition problem [15] asks whether there exists a subset such that
Write . Set and give the two parallel arcs costs
The point , belongs to , with both arc inequalities active. Its root-supply function is , so . The candidate belongs to if and only if .
If satisfies , then its complement also does, and both have follower value zero. Their average is , so (11) gives . Conversely, suppose this envelope value is zero and take attaining weights in (11). Since all integer follower values are nonpositive, every positively weighted assignment satisfies , hence . Their weighted average satisfies
Every positively weighted assignment therefore satisfies equality and solves the Partition instance with weights . The construction has polynomial encoding length, and Partition is a well-known NP-complete problem, proving NP-hardness of membership under the stated restrictions. An exact root-cut separator decides this membership by reporting whether a violated cut exists, and exact evaluation of decides it by comparison with zero. Both tasks are therefore NP-hard as well.
References
- [1]Balas, E.: Lift-and-project cuts for mixed 0–1 programs, pp. 79–89. Springer International Publishing, Cham (2018). https://doi.org/10.1007/978-3-030-00148-3_6
- [2]Bergmann, D., Ciriani, A.A., Van Hoeve, W.J.: Decision diagrams for optimization. Artificial Intelligence: Foundations, Theory, and Algorithms, Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-42849-9
- [3]Borgwardt, S., Finhold, E., Hemmecke, R.: Quadratic diameter bounds for dual network flow polyhedra. Mathematical Programming 159(1), 237–251 (2016). https://doi.org/10.1007/s10107-015-0956-4
- [4]Brotcorne, L., Labbé, M., Marcotte, P., Savard, G.: A bilevel model for toll optimization on a multicommodity transportation network. Transportation science 35(4), 345–358 (2001)
- [5]Brotcorne, L., Labbé, M., Marcotte, P., Savard, G.: Joint design and pricing on a network. Operations Research 56(5), 1104–1115 (2008). https://doi.org/10.1287/opre.1080.0617
- [6]Bui, Q.M., Carvalho, M., Neto, J.: Solving combinatorial pricing problems using embedded dynamic programming models. INFORMS Journal on Computing 38(2), 548–567 (2026). https://doi.org/10.1287/ijoc.2024.0686
- [7]Bui, Q.M., Gendron, B., Carvalho, M.: A catalog of formulations for the network pricing problem. INFORMS Journal on Computing 34(5), 2658–2674 (2022). https://doi.org/10.1287/ijoc.2022.1198
- [8]Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.J.: Bilevel knapsack with interdiction constraints. INFORMS Journal on Computing 28(2), 319–333 (May 2016). https://doi.org/10.1287/ijoc.2015.0676
- [9]Davarnia, D., Richard, J.P.P., Tawarmalani, M.: Simultaneous convexification of bilinear functions over polytypes with application to network interdiction. SIAM Journal on Optimization 27(3), 1801–1833 (2017). https://doi.org/10.1137/16M1066166
- [10]Dempe, S.: Bilevel optimization: theory, algorithms, applications and a bibliography. In: Dempe, S., Zemkoho, A. (eds.) Bilevel Optimization, Springer Optimization and Its Applications, vol. 161, pp. 581–672. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-52119-6_20
- [11]DeNegre, S.: Interdiction and discrete bilevel linear programming. Ph.D. thesis, Lehigh University, USA (2011)
- [12]Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: A new general-purpose algorithm for mixed-integer bilevel linear programs. Operations Research 65(6), 1615–1637 (2017)DOI
- [13]Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: On the use of intersection cuts for bilevel optimization. Mathematical Programming 172(1), 77–103 (2018)DOI
- [14]Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: Interdiction games and monotonicity, with application to knapsack problems. INFORMS Journal on Computing 31(2), 390–410 (2019). https://doi.org/10.1287/ijoc.2018.0831
- [15]Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85–103. Springer US, Boston, MA (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
- [16]Kleinert, T., Labbé, M., Ljubić, I., Schmidt, M.: A survey on mixed-integer programming techniques in bilevel optimization. EURO Journal on Computational Optimization 9, 100007 (2021). https://doi.org/10.1016/j.ejco.2021.100007
- [17]Labbé, M., Marcotte, P., Savard, G.: A bilevel model of taxation and its application to optimal highway pricing. Management Science 44(12-part-1), 1608–1622 (Dec 1998). https://doi.org/10.1287/mnsc.44.12.1608
- [18]Lozano, L., Bergman, D., Cire, A.A.: Constrained shortest-path reformulations via decision diagrams for structured two-stage optimization problems (Jul 2024). https://doi.org/10.48550/arXiv.2406.12962
- [19]Lozano, L., Bergman, D., Cire, A.A.: Network relaxations for combinatorial bilevel optimization under linear interactions. Operations Research (Aug 2026). https://doi.org/10.1287/opre.2025.2457
- [20]Tahernejad, S., Ralphs, T.K.: Valid inequalities for mixed integer bilevel linear optimization problems. arXiv preprint arXiv:2510.02998 (2025). https://doi.org/10.48550/arXiv.2510.02998
- [21]Vázquez, S., Lozano, L., van Hoeve, W.J.: A single-level reformulation of binary bilevel programs using decision diagrams. Mathematical Programming (Dec 2025). https://doi.org/10.1007/s10107-025-02294-1
- [22]Vázquez, S., Lozano, L., van Hoeve, W.J.: Network flow-based cuts for binary bilevel programs. arXiv preprint arXiv:2610.39261 (2026). https://doi.org/10.48550/arXiv.2610.39261