betaFeedback

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

min⁡x,ycT(x,y)s.t.x∈X,y∈arg⁡min⁡y′∈Y q(x)Ty′.(1)\begin{aligned} \min_{x,y}\quad&c^{\mathsf{T}}(x,y)\\ \text{s.t.}\quad&x \in\mathcal{X},\\ &y \in\underset{y' \in\mathcal{Y}}{\arg\min}\ q(x)^{\mathsf{T}}y'. \tag*{(1)} \end{aligned}

Here, x∈X⊆{0,1}nx \in\mathcal{X} \subseteq\{0,1\}^{n} represents the leader’s decisions, where X\mathcal{X} is a set of binary vectors described by linear inequalities. Vector yy represents the follower’s decisions, and cc collects the coefficients of the leader’s linear objective in (x,y)(x,y). The follower solves a shortest-path problem, and Y\mathcal{Y} consists of the arc-incidence vectors of the feasible paths. The leader affects the follower’s optimization solely through arc costs q(x)q(x) that are affine in xx. 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.

  1. 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.

  1. 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.

  1. 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).

  1. 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 D=(V,A)\mathcal{D}=(\mathcal{V},\mathcal{A}) be the directed graph for the follower’s problem, with distinct root r∈Vr\in\mathcal{V} and destination t∈Vt\in\mathcal{V}. We also assume D\mathcal{D} to be acyclic, we allow parallel arcs and retain only nodes and arcs on r⇝tr\rightsquigarrow t paths. This preprocessing preserves all follower choices and makes rr and tt the unique source and sink, respectively. Two network examples are illustrated in Figure 1.

Follower networks

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 x∈Xx\in\mathcal{X}. 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 xx, and its arc weights are given by q(x)=Qx+q0q(x)=Qx+q_0, where Q∈RA×nQ\in\mathbb{R}^{\mathcal{A}\times n} and q0∈RAq_0\in\mathbb{R}^{\mathcal{A}}. For each arc a∈Aa\in\mathcal{A}, let u(a)u(a) and v(a)v(a) denote its tail and head. The node–arc incidence matrix D∈RV×AD\in\mathbb{R}^{\mathcal{V}\times\mathcal{A}} has column Da=eu(a)−ev(a)D_a=e_{u(a)}-e_{v(a)}, where eue_u is the unit vector indexed by node uu.

Recall that Y\mathcal{Y} is the set of arc-incidence vectors of r⇝tr\rightsquigarrow t 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,

conv⁡(Y)={y∈R+A:Dy=er−et}.(2)\operatorname{conv}(\mathcal{Y})=\left\{\mathbf{y}\in\mathbb{R}_{+}^{\mathcal{A}}:D\mathbf{y}=\mathbf{e}_{r}-\mathbf{e}_{t}\right\}. \tag*{(2)}

Strong-duality reformulation

In what follows, let

Ω:={(x,θ,y)∈X×RV×Y:q(x)Ty≤θr, DTθ≤q(x), θt=0}.\Omega:=\left\{(\mathbf{x},\boldsymbol{\theta},\mathbf{y})\in\mathcal{X}\times\mathbb{R}^{\mathcal{V}}\times\mathcal{Y}:\mathbf{q}(\mathbf{x})^{\mathsf{T}}\mathbf{y}\leq\theta_r,\ D^{\mathsf{T}}\boldsymbol{\theta}\leq\mathbf{q}(\mathbf{x}),\ \theta_t=0\right\}.

The constraints x∈X\mathbf{x}\in\mathcal{X} and y∈Y\mathbf{y}\in\mathcal{Y} describe leader feasibility and follower path-incidence vectors, respectively. The dual arc inequalities DTθ≤q(x)D^{\mathsf{T}}\boldsymbol{\theta}\leq\mathbf{q}(\mathbf{x}) couple leader decisions and node potentials. The bilinear optimality constraint q(x)Ty≤θr\mathbf{q}(\mathbf{x})^{\mathsf{T}}\mathbf{y}\leq\theta_r enforces strong duality and couples all three variable blocks, x\mathbf{x}, θ\boldsymbol{\theta} and y\mathbf{y}. Here, we normalize the dual node potentials θ\boldsymbol{\theta} by θt=0\theta_t=0. Following from (2) and strong duality, (1) admits the following equivalent single-level formulation:

min⁡(x,θ,y)∈Ω cT(x,y).(3)\min_{(\mathbf{x},\boldsymbol{\theta},\mathbf{y})\in\Omega}\ \mathbf{c}^{\mathsf{T}}(\mathbf{x},\mathbf{y}). \tag*{(3)}

This formulation is exact for binary (x,y)(\mathbf{x},\mathbf{y}) [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 X≠∅\mathcal{X}\ne\varnothing, 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 X\mathcal{X}. Section 3.3 shows that the root supply er−et\mathbf{e}_r-\mathbf{e}_t 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 conv⁡(Ω)\operatorname{conv}(\Omega) is a polytope. This can be seen from a disjunctive programming perspective, which we formalize in the following proposition.

Proposition 1. conv⁡(Ω)\operatorname{conv}(\Omega) 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 conv⁡(Y)\operatorname{conv}(\mathcal{Y}), and we may also replace X\mathcal{X} by conv⁡(X)\operatorname{conv}(\mathcal{X}). As the next example shows, however, the interaction between the variable blocks can still leave fractional points outside conv⁡(Ω)\operatorname{conv}(\Omega) and an objective gap.

Example 1. Let X={0,1}\mathcal{X} = \{0,1\} and consider two parallel arcs a1,a2a_1,a_2 from rr to tt, with weights qa1(x)=1−2xq_{a_1}(x) = 1 - 2x and qa2(x)=0q_{a_2}(x) = 0. The network is illustrated in Figure 1. The follower’s path set is Y={(1,0),(0,1)}\mathcal{Y} = \{(1,0),(0,1)\}, with yiy_i indicating arc aia_i. Since θt=0\theta_t = 0 and y2=1−y1y_2 = 1-y_1, we retain only (x,θr,y1)(x,\theta_r,y_1). Replacing X\mathcal{X} and Y\mathcal{Y} by their convex hulls in (3) gives (1−2x)y1≤θr≤min⁡{1−2x,0}(1-2x)y_1 \leq\theta_r \leq\min\{1-2x,0\} for 0≤x,y1≤10 \leq x,y_1 \leq1. The fractional point (1/2,0,1)(1/2,0,1) is feasible, but lies outside the segment joining the only binary-feasible solutions (0,0,0)(0,0,0) and (1,−1,1)(1,-1,1). For the objective x−y1x-y_1, it has value −1/2-1/2, whereas both binary solutions have value zero.

Let ϕ(x)\phi(x) denote the follower’s optimal value for x∈conv⁡(X)x \in\operatorname{conv}(\mathcal{X}). In the example, the dual arc inequalities impose θr≤ϕ(x)=min⁡{1−2x,0}\theta_r \leq\phi(x) = \min\{1-2x,0\}, while convexifying the leader–potential set gives the stronger inequality θr≤−x\theta_r \leq-x. 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

S={(x,θ)∈X×RV:DTθ≤q(x), θt=0}\mathcal{S} = \{(x,\theta) \in\mathcal{X} \times\mathbb{R}^{V} : D^{\mathsf{T}}\theta\leq q(x),\ \theta_t = 0\}

and its relaxation

P={(x,θ)∈conv⁡(X)×RV:DTθ≤q(x), θt=0}.\mathcal{P} = \{(x,\theta) \in\operatorname{conv}(\mathcal{X}) \times\mathbb{R}^{V} : D^{\mathsf{T}}\theta\leq q(x),\ \theta_t = 0\}.

We refer to S\mathcal{S} as the leader–potential set, and to P\mathcal{P} as its continuous relaxation. We note that structures similar to P\mathcal{P} 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 conv⁡(X)\operatorname{conv}(\mathcal{X}) in P\mathcal{P} isolates the interaction between leader decisions and potentials. For a set CC in (x,θ)(x,\theta)-space, write C(xˉ)={θ:(xˉ,θ)∈C}C(\bar{x}) = \{\theta: (\bar{x},\theta) \in C\} for its potential fiber. Every fiber P(xˉ)\mathcal{P}(\bar{x}) with xˉ∈conv⁡(X)\bar{x} \in\operatorname{conv}(\mathcal{X}) is nonempty, as witnessed by shortest-path costs from each node to tt. Moreover, S(x^)=P(x^)\mathcal{S}(\hat{x}) = \mathcal{P}(\hat{x}) for x^∈X\hat{x} \in\mathcal{X}, so Proj⁡xS=X\operatorname{Proj}_x \mathcal{S} = \mathcal{X}. The finitely many nonempty fibers of S\mathcal{S} are pointed polyhedra with a common recession cone, hence conv⁡(S)\operatorname{conv}(\mathcal{S}) is also a polyhedron.

With the bilinear optimality constraint retained, convexifying SS excludes every point outside conv⁡(Ω)\operatorname{conv}(\Omega). Define

E={(x,θ,y):(x,θ)∈conv⁡(S), y∈conv⁡(Y), q(x)Ty≤θr}.\mathcal{E}=\left\{(\boldsymbol{x},\boldsymbol{\theta},\boldsymbol{y}):(\boldsymbol{x},\boldsymbol{\theta})\in\operatorname{conv}(S),\ \boldsymbol{y}\in\operatorname{conv}(\mathcal{Y}),\ q(\boldsymbol{x})^{\mathsf{T}}\boldsymbol{y}\leq\theta_r\right\}.

Proposition 2. conv⁡(E)=conv⁡(Ω)\operatorname{conv}(\mathcal{E})=\operatorname{conv}(\Omega).

Thus every point of E\mathcal{E} is a convex combination of feasible single-level solutions, and every linear objective has the same optimal value over E\mathcal{E} and Ω\Omega. This justifies focusing on valid inequalities for SS. Although E\mathcal{E} may be nonconvex, these inequalities also strengthen the McCormick relaxation of the bilinear terms. In Example 1, adding conv⁡(S)={(x,θr):0≤x≤1, θr≤−x}\operatorname{conv}(S)=\{(\boldsymbol{x},\theta_r):0\leq x\leq1,\ \theta_r\leq-x\} to that relaxation even yields an ideal formulation.

Valid inequalities and network flows

We now characterize all valid inequalities for SS. Consider valid inequalities for conv⁡(S)\operatorname{conv}(S) of the form

βTθ≤πTx+π0.(4)\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{\theta}\leq\boldsymbol{\pi}^{\mathsf{T}}\boldsymbol{x}+\pi_0. \tag*{(4)}

With β=0\boldsymbol{\beta}=\boldsymbol{0}, those are precisely the valid inequalities for Proj⁡xS=X\operatorname{Proj}_{\boldsymbol{x}}S=\mathcal{X}. 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 β=0\boldsymbol{\beta}=\boldsymbol{0}, and one can resort to general integer-programming techniques. Our focus is on inequalities with β≠0\boldsymbol{\beta}\ne\boldsymbol{0}, which account for the interaction between leader decisions and node potentials. Since θt=0\theta_t=0, we may choose βt=−∑u∈V∖{t}βu\beta_t=-\sum_{u\in\mathcal{V}\setminus\{t\}}\beta_u without changing the inequality. Throughout, we use this representative, so that ∑u∈Vβu=0\sum_{u\in\mathcal{V}}\beta_u=0.

All valid inequalities of interest have node potential coefficients β\boldsymbol{\beta} that define valid supplies over the network. Intuitively, β\boldsymbol{\beta} derives from nonnegative combinations of the follower’s dual inequalities, thus columns of DD. 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

B={Dλ:λ∈R+A},Λ(β)={λ∈R+A:Dλ=β}.\mathcal{B}=\{D\boldsymbol{\lambda}:\boldsymbol{\lambda}\in\mathbb{R}_{+}^{\mathcal{A}}\},\qquad\Lambda(\boldsymbol{\beta})=\{\boldsymbol{\lambda}\in\mathbb{R}_{+}^{\mathcal{A}}:D\boldsymbol{\lambda}=\boldsymbol{\beta}\}.

For β∈B\boldsymbol{\beta}\in\mathcal{B}, acyclicity makes Λ(β)\Lambda(\boldsymbol{\beta}) a nonempty polytope, and linear programming duality gives the finite, attained value

fβ(x):=max⁡θ∈P(x)βTθ=min⁡λ∈Λ(β)q(x)Tλ,∀x∈conv⁡(X).(5)f_{\boldsymbol{\beta}}(\boldsymbol{x}):=\max_{\boldsymbol{\theta}\in P(\boldsymbol{x})}\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{\theta}=\min_{\boldsymbol{\lambda}\in\Lambda(\boldsymbol{\beta})}q(\boldsymbol{x})^{\mathsf{T}}\boldsymbol{\lambda},\qquad\forall\boldsymbol{x}\in\operatorname{conv}(\mathcal{X}). \tag*{(5)}

Proposition 3. Let β\boldsymbol{\beta} satisfy ∑u∈Vβu=0\sum_{u\in\mathcal{V}}\beta_u=0. Inequality (4) is valid for SS if and only if β∈B\boldsymbol{\beta}\in\mathcal{B} and

πTx+π0≥fβ(x)∀x∈X.\boldsymbol{\pi}^{\mathsf{T}}\boldsymbol{x}+\pi_0\geq f_{\boldsymbol{\beta}}(\boldsymbol{x})\qquad\forall\boldsymbol{x}\in\mathcal{X}.

Equivalently, for every x∈X\boldsymbol{x}\in\mathcal{X} there exists a flow certificate λx∈Λ(β)\boldsymbol{\lambda}^{\boldsymbol{x}}\in\Lambda(\boldsymbol{\beta}) such that

πTx+π0≥q(x)Tλx.(6)\boldsymbol{\pi}^{\mathsf{T}}\boldsymbol{x}+\pi_0\geq q(\boldsymbol{x})^{\mathsf{T}}\boldsymbol{\lambda}^{\boldsymbol{x}}. \tag*{(6)}

By Proposition 3, the right-hand side of any valid inequality defines an affine upper bound for fβf_{\beta} on X\mathcal{X}. Since the graph is acyclic, Λ(β)\Lambda(\beta) is a polytope, and fβf_{\beta} can be expressed as a minimum of finitely many affine functions of xx, one for each extreme point of Λ(β)\Lambda(\beta). Although fβf_{\beta} is therefore concave, we are interested in upper bounds for the function over X\mathcal{X} only, which means they might imply stronger bounds at fractional leader coordinates than the function itself. For β∈B\beta\in\mathcal{B}, let f^β\hat{f}_{\beta} be the smallest concave function on conv⁡(X)\operatorname{conv}(\mathcal{X}) bounded below by fβf_{\beta} on X\mathcal{X}, that is, let f^β\hat{f}_{\beta} be the concave envelope of fβf_{\beta} over X\mathcal{X}.

Corollary 1. For β∈B\beta\in\mathcal{B}, (4) is valid for SS if and only if πTx+π0\pi^{\mathsf{T}}x+\pi_0 is an affine upper bound of f^β\hat{f}_{\beta} on conv⁡(X)\operatorname{conv}(\mathcal{X}).

Consequently, at every xˉ∈conv⁡(X)\bar{x} \in\operatorname{conv}(\mathcal{X}), there exists a supporting hyperplane of the hypograph of f^β\hat{f}_{\beta} whose associated valid inequality has minimal right-hand side at xˉ\bar{x} among all valid inequalities with potential coefficients β\beta.

Root supply and optimality gap

The root potential θr\theta_r 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 xx and θr\theta_r. We show that this family suffices to recover the optimal value of the bilevel problem.

The root supply βr=er−et\beta^r=e_r-e_t supplies one unit of flow at the root rr and consumes it at the target tt. Since Λ(βr)=conv⁡(Y)\Lambda(\beta^r)=\operatorname{conv}(\mathcal{Y}), (5) gives

fβr(x)=min⁡y∈Yq(x)Ty=ϕ(x).f_{\beta^r}(x)=\min_{y\in\mathcal{Y}}q(x)^{\mathsf{T}}y=\phi(x).

Thus, the associated root cuts1 have the form θr≤πTx+π0\theta_r\leq\pi^{\mathsf{T}}x+\pi_0, where the right-hand side is an affine upper bound of the follower’s value function on X\mathcal{X}. Let ϕ^=f^βr\hat{\phi}=\hat{f}_{\beta^r} denote its concave envelope over X\mathcal{X}. By Corollary 1, adding all root cuts to P\mathcal{P} gives the closure

Rr={(x,θ)∈P:θr≤ϕ^(x)}.(7)R_r=\{(x,\theta)\in\mathcal{P}:\theta_r\leq\hat{\phi}(x)\}. \tag*{(7)}

Lemma 1. The root closure satisfies

Proj⁡(x,θr)Rr=Proj⁡(x,θr)conv⁡(S)={(x,η):x∈conv⁡(X), η≤ϕ^(x)}.\operatorname{Proj}_{(x,\theta_r)}R_r=\operatorname{Proj}_{(x,\theta_r)}\operatorname{conv}(S)=\{(x,\eta):x\in\operatorname{conv}(\mathcal{X}),\ \eta\leq\hat{\phi}(x)\}.

The projection equality implies that, for every a∈Rna\in\mathbb{R}^n and γ≤0\gamma\leq0,

min⁡(x,θ)∈RraTx+γθr=min⁡(x,θ)∈SaTx+γθr.(8)\min_{(x,\theta)\in R_r}a^{\mathsf{T}}x+\gamma\theta_r=\min_{(x,\theta)\in S}a^{\mathsf{T}}x+\gamma\theta_r. \tag*{(8)}

Thus, root cuts close the gap for objectives on SS involving the potentials only through θr\theta_r. This has an important consequence for problems with interdiction objectives [11], which can be formulated [8, 14, 6] as in (8) with a=0a=0 and γ=−1\gamma=-1. 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

Er={(x,θ,y):(x,θ)∈Rr, y∈conv⁡(Y), q(x)Ty≤θr}.\mathcal{E}_r = \{(\boldsymbol{x},\boldsymbol{\theta},\boldsymbol{y}) : (\boldsymbol{x},\boldsymbol{\theta}) \in\mathcal{R}_r,\ \boldsymbol{y} \in\operatorname{conv}(\mathcal{Y}),\ \boldsymbol{q}(\boldsymbol{x})^\mathsf{T}\boldsymbol{y} \le\theta_r\}.

For a point of Er\mathcal{E}_r, take a convex decomposition of its leader component attaining the root envelope and a convex decomposition of its follower path component. The ϕ^(x)\hat{\phi}(\boldsymbol{x}) 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 Proj⁡(x,y)Er\operatorname{Proj}_{(\boldsymbol{x},\boldsymbol{y})}\mathcal{E}_r is a convex combination of bilevel-feasible leader–path pairs. Moreover, for every linear objective cT(x,y)\boldsymbol{c}^\mathsf{T}(\boldsymbol{x},\boldsymbol{y}),

min⁡(x,θ,y)∈ErcT(x,y)=min⁡(x,θ,y)∈ΩcT(x,y).\min_{(\boldsymbol{x},\boldsymbol{\theta},\boldsymbol{y}) \in\mathcal{E}_r} \boldsymbol{c}^\mathsf{T}(\boldsymbol{x},\boldsymbol{y}) = \min_{(\boldsymbol{x},\boldsymbol{\theta},\boldsymbol{y}) \in\Omega} \boldsymbol{c}^\mathsf{T}(\boldsymbol{x},\boldsymbol{y}).

The theorem strengthens the conclusion of Proposition 2 for the objective of interest: convexifying the entire leader–potential set S\mathcal{S} 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 conv⁡(S)\operatorname{conv}(\mathcal{S}). This limitation persists for the larger family of all unit supplies, namely eu−ev\boldsymbol{e}_u-\boldsymbol{e}_v for distinct nodes uu, vv joined by a directed u⇝vu \leadsto v path, as the following example shows.

Example 2 (Unit supplies are insufficient). Let X={0,1}2\mathcal{X}=\{0,1\}^2 and V={r,u,v,t}\mathcal{V}=\{r,u,v,t\}. The arcs r→ur\to u and r→vr\to v have cost zero. There are two parallel u→tu\to t arcs of costs 00 and 1−x1−x21-x_1-x_2, and two parallel v→tv\to t arcs of costs 00 and x2−x1x_2-x_1, as illustrated in Figure 1. The point

xˉ=(1/2,1/2),(θˉr,θˉu,θˉv,θˉt)=(−1/2,0,0,0)\bar{\boldsymbol{x}}=(1/2,1/2),\qquad(\bar{\theta}_r,\bar{\theta}_u,\bar{\theta}_v,\bar{\theta}_t)=(-1/2,0,0,0)

belongs to P\mathcal{P} and satisfies every cut with a unit supply, including every root cut. Nevertheless, the inequality

θu+θv≤−x1\theta_u+\theta_v\le-x_1

is valid for S\mathcal{S} and violated by this point. Its supply is eu+ev−2et\boldsymbol{e}_u+\boldsymbol{e}_v-2\boldsymbol{e}_t.

Unit supplies contain a generator of every extreme ray of B\mathcal{B}, since this cone is generated by the columns of DD, each of which is a unit supply. Thus even inequalities from all extreme supply directions can leave points outside conv⁡(S)\operatorname{conv}(\mathcal{S}) 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 P\mathcal{P}, 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 (xˉ,θˉ,yˉ)(\bar{x},\bar{\theta},\bar{y}) be an optimal solution from any continuous relaxation of Ω\Omega. If xˉ\bar{x} is fractional and its active leader constraints have rank nn, then an inequality for X\mathcal{X} alone suffices to separate it. As previously discussed, we will not concentrate on this case.

For candidates with xˉ∈conv⁡(X)\bar{x} \in\operatorname{conv}(\mathcal{X}), Proposition 2 justifies focusing on the leader–potential set. Define Ξ\Xi to be a continuous relaxation of Ω\Omega as follows:

Ξ:={(x,θ,y)∈conv⁡(X)×RV×conv⁡(Y):q(x)Ty≤θr, DTθ≤q(x), θt=0}.\Xi:= \left\{(x,\theta,y) \in\operatorname{conv}(\mathcal{X}) \times\mathbb{R}^{V} \times\operatorname{conv}(\mathcal{Y}) : q(x)^{\mathsf{T}}y \le\theta_r,\ D^{\mathsf{T}}\theta\le q(x),\ \theta_t = 0\right\}.

The proposition also shows that inequalities of the form (4) with β≠0\beta\ne0 are sufficient to separate any point in Ξ∖conv⁡(Ω)\Xi\setminus\operatorname{conv}(\Omega). We explore this result in the following lemma.

Lemma 2. Every extreme point (xˉ,θˉ,yˉ)∈Ξ(\bar{x},\bar{\theta},\bar{y}) \in\Xi satisfies yˉ∈Y\bar{y} \in\mathcal{Y}, and (xˉ,θˉ)(\bar{x},\bar{\theta}) is a vertex of P\mathcal{P}.

We therefore focus on vertices of P\mathcal{P} with fractional leader coordinates, which necessarily lie outside conv⁡(S)\operatorname{conv}(\mathcal{S}) and admit a separating inequality.

Fixing node potential coefficients β\beta

Let (xˉ,θˉ)(\bar{x},\bar{\theta}) be a vertex of P\mathcal{P} with fractional leader coordinates. By Proposition 3, a cut-generating linear program (CGLP) can jointly select (β,π,π0)(\beta,\pi,\pi_0) 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 ∣X∣∣A∣|\mathcal{X}||\mathcal{A}| flow variables, and may be exponentially large. We instead construct the node potential coefficients β\beta from the arc inequalities active at (xˉ,θˉ)(\bar{x},\bar{\theta}), preserving the existence of a separating cut while leaving the leader coefficients to be optimized.

Proposition 3 restricts admissible β\beta to the supply cone B\mathcal{B}, but does not determine which supplies admit separation at the candidate. For fixed β∈B∖{0}\beta\in\mathcal{B} \setminus\{0\}, Corollary 1 gives the maximum attainable violation as

vβ(xˉ,θˉ):=βTθˉ−f^β(xˉ).(9)v_{\beta}(\bar{x},\bar{\theta}) := \beta^{\mathsf{T}}\bar{\theta} - \hat{f}_{\beta}(\bar{x}). \tag*{(9)}

A separating inequality with this β\beta exists if and only if this value is positive.

For any (xˉ,θˉ)∈P(\bar{x},\bar{\theta}) \in\mathcal{P}, define its active arcs by

A0={a∈A:DaTθˉ=qa(xˉ)}.\mathcal{A}_0 = \left\{a \in\mathcal{A} : D_a^{\mathsf{T}}\bar{\theta} = q_a(\bar{x})\right\}.

Connectivity and spanning trees below refer to the underlying undirected graph; each selected arc retains its original orientation.

Lemma 3. For (xˉ,θˉ)∈P(\bar{x},\bar{\theta}) \in\mathcal{P}, the active-arc graph (V,A0)(\mathcal{V},\mathcal{A}_0) is connected if and only if θˉ\bar{\theta} is a vertex of P(xˉ)\mathcal{P}(\bar{x}). In particular, it is connected at every vertex of P\mathcal{P}.

Figure 2 illustrates the connected active-arc graph at a fractional vertex of P\mathcal{P}.

Active arcs at a vertex of $\mathcal{P}$

Figure 2. Active arcs at a vertex of P\mathcal{P} with X={0,1}\mathcal{X}=\{0,1\} and (xˉ,θˉ)=(1/2,0)(\bar{x},\bar{\theta})=(1/2,0). 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 (x,θr,θu,θv)(x,\theta_r,\theta_u,\theta_v).

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 P(x)\mathcal{P}(\boldsymbol{x}). The network structure makes the required row selection inexpensive: after eliminating θt\theta_t, a spanning tree of active arcs provides a minimum-cardinality full-rank collection of ∣V∣−1|\mathcal{V}|-1 rows. Once the active-arc graph is available, such a tree can be found by graph traversal in O(∣V∣+∣A0∣)O(|\mathcal{V}|+|\mathcal{A}_0|) time, without matrix rank computations. Positive weights on its arcs then determine a supply vector β\beta; the following lemma establishes the resulting separation guarantee.

Lemma 4. Suppose (xˉ,θˉ)∈P(\bar{x},\bar{\theta})\in\mathcal{P} has a connected active-arc graph. Choose a spanning tree T⊆A0T\subseteq\mathcal{A}_0 and weights wa>0w_a>0 for a∈Ta\in T. Then

β=∑a∈TwaDa\beta=\sum_{a\in T}w_aD_a

belongs to B∖{0}\mathcal{B}\setminus\{0\}. Moreover, vβ(xˉ,θˉ)>0v_\beta(\bar{x},\bar{\theta})>0 if and only if (xˉ,θˉ)∉conv⁡(S)(\bar{x},\bar{\theta})\notin\operatorname{conv}(\mathcal{S}). In particular, this construction guarantees separation at every vertex of P\mathcal{P} with fractional leader coordinates.

The weighted sum of the tree inequalities is valid for P\mathcal{P} and active at (xˉ,θˉ)(\bar{x},\bar{\theta}), 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 X\mathcal{X}. The guarantee concerns the existence of a cut, not its strength relative to other supply vectors.

Let P+\mathcal{P}^{+} be obtained from P\mathcal{P} by adding finitely many valid inequalities (βj)Tθ≤ℓj(x)(\beta^{j})^{\mathsf{T}}\theta\leq\ell_j(x), with affine ℓj\ell_j and βj∈B\beta^{j}\in\mathcal{B}. Unlike for P\mathcal{P}, the active-arc graph at a vertex of P+\mathcal{P}^{+} need not be connected. Consider first the case in which (V,A0)(\mathcal{V},\mathcal{A}_0) consists of two components, C0C_0 containing tt and C1C_1. A spanning tree in each component fixes all differences of node potential variables, allowing only for a common shift of the potentials in C1C_1. An active added cut fixes this shift whenever its total supply ∑u∈C1βuj\sum_{u\in C_1}\beta^j_u 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.

Connected components before and after adding one cut

Figure 3. Connected components before and after adding one cut, with X={0,1}X = \{0,1\} and potentials ordered as (r,u,v,t)(r,u,v,t). Solid arcs are active, dashed arcs are inactive, and shading identifies components of the original active-arc graph. The root cut is valid since ϕ(0)=0\phi(0)=0 and ϕ(1)=−2\phi(1)=-2. In (b), it is active and fixes the relative shift between C1C_1 and C0C_0.

Proposition 4. Let (xˉ,θˉ)(\bar{x},\bar{\theta}) be a vertex of P+\mathcal{P}^+, let C0,…,Cc−1C_0,\ldots,C_{c-1} be its active-arc components, with t∈C0t \in C_0, and let J0J_0 index its active added cuts. The matrix

Γjℓ=∑u∈Cℓβuj,j∈J0, ℓ=1,…,c−1,\Gamma_{j\ell} = \sum_{u \in C_\ell} \beta^j_u,\qquad j \in J_0,\ \ell= 1,\ldots,c-1,

has rank c−1c-1. Choose a spanning tree in each component, with union FF, and a set J⊆J0J \subseteq J_0 indexing c−1c-1 independent rows of Γ\Gamma. The corresponding ∣V∣−1|V|-1 original arc inequalities and added cuts form a minimum-cardinality full-rank collection in the node potential coordinates, excluding θt\theta_t. For any positive weights waw_a and μj\mu_j, the supply

β=∑a∈FwaDa+∑j∈Jμjβj\beta= \sum_{a \in F} w_a D_a + \sum_{j \in J} \mu_j \beta^j

belongs to B∖{0}\mathcal{B} \setminus\{0\}. Moreover, vβ(xˉ,θˉ)>0v_\beta(\bar{x},\bar{\theta}) > 0 if and only if (xˉ,θˉ)∉conv⁡(S)(\bar{x},\bar{\theta}) \notin\operatorname{conv}(S). In particular, it admits a separating inequality whenever xˉ\bar{x} is fractional.

The network structure therefore keeps row selection inexpensive within each component: graph traversal selects the forest, and c−1c-1 linearly independent active cuts fix the remaining degrees of freedom. For c=1c=1, 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 r→tr \to t 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 β\beta that admits separation leaves the leader variable coefficients to be determined. For fixed β∈B∖{0}\beta\in\mathcal{B} \setminus\{0\} and a point (xˉ,θˉ)∈P(\bar{x},\bar{\theta}) \in\mathcal{P}, Corollary 1 gives the attained maximum violation as

vβ(xˉ,θˉ)=max⁡π,π0 βTθˉ−πTxˉ−π0v_{\beta}(\bar{x},\bar{\theta}) = \max_{\pi,\pi_0}\ \beta^{\mathsf{T}}\bar{\theta} - \pi^{\mathsf{T}}\bar{x} - \pi_0
s.t.πTxk+π0≥fβ(xk),k=1,…,K,(10)\text{s.t.}\quad\pi^{\mathsf{T}}x^k + \pi_0 \ge f_{\beta}(x^k), \qquad k = 1,\ldots,K, \tag*{(10)}

where x1,…,xKx^1,\ldots,x^K is an enumeration of the feasible points in X\mathcal{X}. Each value fβ(xk)f_{\beta}(x^k) can be computed by a minimum-cost flow problem. Given these values, LP (10) has only n+1n+1 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 A0\mathcal{A}_0. For a vertex of P\mathcal{P} 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 β\beta. When a linear description of conv⁡(X)\operatorname{conv}(\mathcal{X}) 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 β\beta.

Proposition 5. Membership in the root-cut closure RrR_r is NP-hard, even for candidates in P\mathcal{P} when X={0,1}n\mathcal{X} = \{0,1\}^n and the graph consists of two parallel r→tr \to t arcs, one with constant cost. Consequently, exact separation of root cuts and exact evaluation of ϕ^\hat{\phi} are NP-hard under the same restrictions.

The proof, given in section A, reduces PARTITION to membership at xˉ=121\bar{x} = \frac{1}{2}\mathbf{1}. 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 P\mathcal{P} 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 conv⁡(X)\operatorname{conv}(\mathcal{X}), 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 PP 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 (x^,y^)∈X×Y(\hat{x},\hat{y}) \in\mathcal{X} \times\mathcal{Y} for which the potential constraints in (3) are feasible. Weak duality and the optimality constraint give θr=q(x^)⊤y^\theta_r = q(\hat{x})^\top\hat{y}. For each node uu, choose an r⇝ur \leadsto u path ρu\rho_u and a u⇝tu \leadsto t path τu\tau_u, allowing the empty path at an endpoint. Summing the dual arc inequalities along these paths yields

q(x^)Ty^−∑a∈ρuqa(x^)≤θu≤∑a∈τuqa(x^).q(\hat{x})^{\mathsf{T}}\hat{y}-\sum_{a\in\rho_u}q_a(\hat{x})\le\theta_u\le\sum_{a\in\tau_u}q_a(\hat{x}).

Thus the feasible potentials for each fixed pair form a bounded polyhedron. Since X\mathcal{X} and Y\mathcal{Y} are finite, Ω\Omega 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 Ω⊆E⊆conv⁡(Ω)\Omega\subseteq\mathcal{E}\subseteq\operatorname{conv}(\Omega). Taking the convex hull gives conv⁡(E)=conv⁡(Ω)\operatorname{conv}(\mathcal{E})=\operatorname{conv}(\Omega).

The inclusion Ω⊆E\Omega\subseteq\mathcal{E} follows from S⊆conv⁡(S)\mathcal{S}\subseteq\operatorname{conv}(\mathcal{S}) and Y⊆conv⁡(Y)\mathcal{Y}\subseteq\operatorname{conv}(\mathcal{Y}). For the reverse containment in conv⁡(Ω)\operatorname{conv}(\Omega), take (xˉ,θˉ,yˉ)∈E(\bar{x},\bar{\theta},\bar{y})\in\mathcal{E} and choose finite convex representations

(xˉ,θˉ)=∑iλi(xi,θi),yˉ=∑jμjyj,(\bar{x},\bar{\theta})=\sum_i\lambda_i(x^i,\theta^i),\qquad\bar{y}=\sum_j\mu_j y^j,

where (xi,θi)∈S(x^i,\theta^i)\in\mathcal{S}, yj∈Yy^j\in\mathcal{Y}, λi,μj≥0\lambda_i,\mu_j\geq0, and ∑iλi=∑jμj=1\sum_i\lambda_i=\sum_j\mu_j=1. Since the path set Y\mathcal{Y} is independent of the leader assignment, every pair (i,j)(i,j) combines a feasible follower path with dual-feasible potentials at xix^i. Weak duality then gives us q(xi)Tyj−θri≥0q(x^i)^{\mathsf{T}}y^j-\theta^i_r\geq0 for each pair (i,j)(i,j). Because the candidate solution satisfies the follower’s optimality constraint and q(x)q(x) is affine, we have

0≥q(xˉ)Tyˉ−θˉr=∑i,jλiμj(q(xi)Tyj−θri)≥0.0\geq q(\bar{x})^{\mathsf{T}}\bar{y}-\bar{\theta}_r=\sum_{i,j}\lambda_i\mu_j\bigl(q(x^i)^{\mathsf{T}}y^j-\theta^i_r\bigr)\geq0.

For every (i,j)(i,j) pair with λiμj>0\lambda_i\mu_j>0 the optimality gap must vanish, that is, q(xi)Tyj−θri=0q(x^i)^{\mathsf{T}}y^j-\theta^i_r=0. Hence each positively weighted triple (xi,θi,yj)(x^i,\theta^i,y^j) belongs to Ω\Omega. Finally, the weights λiμj\lambda_i\mu_j sum to one and satisfy

(xˉ,θˉ,yˉ)=∑i,jλiμj(xi,θi,yj),(\bar{x},\bar{\theta},\bar{y})=\sum_{i,j}\lambda_i\mu_j(x^i,\theta^i,y^j),

proving E⊆conv⁡(Ω)\mathcal{E}\subseteq\operatorname{conv}(\Omega).

Flow characterization and fixed-supply convexification

Proof of Proposition 3. We first verify (5) and supply admissibility. For any x∈conv⁡(X)x\in\operatorname{conv}(\mathcal{X}), the potential maximization is feasible, and its linear programming dual is

min⁡{q(x)Tλ:Dλ+μet=β, λ≥0, μ∈R}.\min\{q(x)^{\mathsf{T}}\lambda:D\lambda+\mu e_t=\beta,\ \lambda\geq0,\ \mu\in\mathbb{R}\}.

Summing the balance equations gives μ=0\mu=0 because ∑u∈Vβu=0\sum_{u\in V}\beta_u=0. Hence dual feasibility is equivalent to β∈B\beta\in\mathcal{B}. If (4) is valid, its right-hand side bounds the potential objective on any fiber indexed by x∈Xx\in\mathcal{X}. Such a fiber exists because X≠∅\mathcal{X}\neq\varnothing, so linear programming duality implies β∈B\beta\in\mathcal{B}.

For β∈B\beta\in\mathcal{B}, the recession cone of Λ(β)\Lambda(\beta) consists of nonnegative circulations. Acyclicity implies that the only such circulation is zero, so Λ(β)\Lambda(\beta) 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

βTθ=(xu)TDTθ≤q(x)Tx≤πTx+π0for all θ∈S(x),\beta^{\mathsf{T}}\theta= (x^{\mathsf{u}})^{\mathsf{T}}D^{\mathsf{T}}\theta\le q(x)^{\mathsf{T}}x \le\pi^{\mathsf{T}}x+\pi_0 \qquad\text{for all }\theta\in S(x),

proving validity.

Root supply and the optimality gap

Proof of Lemma 1. We first determine the possible values of the root potential θr\theta_r for a fixed leader decision x∈conv⁡(X)x \in\operatorname{conv}(\mathcal{X}). Assigning each node its shortest-path cost to tt gives feasible potentials with θr=ϕ(x)\theta_r=\phi(x). Since rr has no incoming arcs, decreasing only θr\theta_r preserves feasibility. Together with weak duality, this proves

Proj⁡θrP(x)=(−∞,ϕ(x)].\operatorname{Proj}_{\theta_r}\mathcal{P}(x)=(-\infty,\phi(x)].

We next show that convexifying SS replaces this upper bound by the concave envelope of the values at integer leader decisions. Let x1,…,xKx^1,\ldots,x^K be an enumeration of X\mathcal{X} and fix xˉ∈conv⁡(X)\bar{x}\in\operatorname{conv}(\mathcal{X}). The concave envelope has the representation

ϕ^(xˉ)=max⁡{∑k=1Kαkϕ(xk):∑k=1Kαkxk=xˉ, ∑k=1Kαk=1, α≥0}.(11)\hat{\phi}(\bar{x})=\max\left\{\sum_{k=1}^{K}\alpha_k\phi(x^k):\sum_{k=1}^{K}\alpha_kx^k=\bar{x},\ \sum_{k=1}^{K}\alpha_k=1,\ \alpha\geq0\right\}. \tag*{(11)}

Indeed, the right-hand side is a concave upper bound of the values on X\mathcal{X}, and every such upper bound dominates it by concavity. The maximum is attained because the feasible weight set is nonempty and compact and each ϕ(xk)\phi(x^k) is finite. Every convex combination of points of SS with leader component xˉ\bar{x} has root potential at most the corresponding weighted sum of follower values, and hence at most ϕ^(xˉ)\hat{\phi}(\bar{x}). To attain this bound, choose weights αk\alpha_k maximizing (11) and, for each kk, let θk\theta^k be the shortest-path potentials for arc costs q(xk)q(x^k). Then (xk,θk)∈S(x^k,\theta^k)\in S and θrk=ϕ(xk)\theta_r^k=\phi(x^k), so

(xˉ,θˉ):=∑kαk(xk,θk)∈conv⁡(S),θˉr=ϕ^(xˉ).(\bar{x},\bar{\theta}):=\sum_k\alpha_k(x^k,\theta^k)\in\operatorname{conv}(S),\qquad\bar{\theta}_r=\hat{\phi}(\bar{x}).

Decreasing every θrk\theta_r^k by the same nonnegative amount preserves membership in SS and yields every smaller value of θˉr\bar{\theta}_r. This proves the asserted projection of conv⁡(S)\operatorname{conv}(S).

Finally, we compare this projection with that of the root closure. Since ϕ\phi is concave, ϕ^≤ϕ\hat{\phi}\leq\phi on conv⁡(X)\operatorname{conv}(\mathcal{X}). The first part of the proof therefore shows that imposing θr≤ϕ^(x)\theta_r\leq\hat{\phi}(x) on P\mathcal{P} leaves precisely the root potential values (−∞,ϕ^(x)](-\infty,\hat{\phi}(x)] for each x∈conv⁡(X)x\in\operatorname{conv}(\mathcal{X}). By (7), this proves the equality for Rr\mathcal{R}_r.

Proof of Theorem 1. Take (xˉ,θˉ,yˉ)∈Er(\bar{x},\bar{\theta},\bar{y})\in E_r. Choose weights αk\alpha_k attaining (11) and write yˉ=∑jμjyj\bar{y}=\sum_j\mu_j y^j with yj∈Yy^j\in\mathcal{Y}, μj≥0\mu_j\geq0, and ∑jμj=1\sum_j\mu_j=1. Feasibility and the affinity of qq give

ϕ^(xˉ)≥θˉr≥q(xˉ)Tyˉ=∑k,jαkμjq(xk)Tyj≥∑kαkϕ(xk)=ϕ^(xˉ).\begin{aligned} \hat{\phi}(\bar{x})\geq\bar{\theta}_r\geq q(\bar{x})^{\mathsf{T}}\bar{y} \\ &=\sum_{k,j}\alpha_k\mu_jq(x^k)^{\mathsf{T}}y^j\geq\sum_k\alpha_k\phi(x^k)=\hat{\phi}(\bar{x}). \end{aligned}

All inequalities are equalities. Each difference q(xk)⊤yj−ϕ(xk)q(x^k)^\top y^j-\phi(x^k) is nonnegative, so it vanishes whenever αkμj>0\alpha_k\mu_j>0. Every positively weighted pair (xk,yj)(x^k,y^j) is therefore bilevel feasible, and

(xˉ,yˉ)=∑k,jαkμj(xk,yj).(\bar{x},\bar{y})=\sum_{k,j}\alpha_k\mu_j(x^k,y^j).

This proves the convex-combination claim and bounds every linear leader objective below by the bilevel optimum. Conversely, Ω⊆Er\Omega\subseteq E_r because root cuts are valid for SS. The optimal values consequently coincide.

Reduction to the dual network polyhedron

Proof of Lemma 2. Let (xˉ,θˉ,yˉ)(\bar{x},\bar{\theta},\bar{y}) be an extreme point of R\mathcal{R}. Decompose yˉ\bar{y} into path-incidence vectors. Weak duality gives q(xˉ)⊤y≥θˉrq(\bar{x})^\top y\ge\bar{\theta}_r 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 (xˉ,θˉ)(\bar{x},\bar{\theta}). Extremality forces all those paths to equal yˉ\bar{y}, proving yˉ∈Y\bar{y}\in\mathcal{Y}.

Now suppose (xˉ,θˉ)(\bar{x},\bar{\theta}) is a nontrivial convex combination of two points of P\mathcal{P}. With yˉ\bar{y} fixed, the gap q(x)⊤yˉ−θrq(x)^\top\bar{y}-\theta_r is affine and nonnegative on P\mathcal{P}. It vanishes at the candidate, so it vanishes at both endpoints. Appending yˉ\bar{y} to these endpoints gives a nontrivial convex representation in R\mathcal{R}, a contradiction.

Constructive supply selection

Proof of Lemma 3. If the active-arc graph of a point (xˉ,θˉ)∈P(\bar{x},\bar{\theta})\in\mathcal{P} is connected, a displacement of node potentials preserving its arc equalities must be constant on all nodes. The normalization at tt makes that displacement zero. Hence the active equalities uniquely determine the node potentials from xˉ\bar{x}, proving that θˉ\bar{\theta} is a vertex of the fiber P(xˉ)\mathcal{P}(\bar{x}). If the graph is disconnected, shift every node potential in a component not containing tt by ε\varepsilon or by −ε-\varepsilon. Active equalities are preserved, and the finitely many inactive arc inequalities remain feasible for sufficiently small ε>0\varepsilon>0. These two distinct feasible node potential vectors have midpoint θˉ\bar{\theta}, contradicting fiber extremality. Finally, a nontrivial convex representation within a fiber also gives one in P\mathcal{P}, so every vertex of P\mathcal{P} is a fiber vertex.

Proof of Lemma 4. The vector β\beta is the supply of the nonnegative flow with value waw_a on TT and zero elsewhere. It is nonzero because a DAG has no nonzero nonnegative circulation. Summing the selected inequalities gives the valid inequality

β⊤θ≤ℓ(x),ℓ(x)=∑a∈Twaqa(x).\beta^\top\theta\le\ell(x),\qquad\ell(x)=\sum_{a\in T}w_aq_a(x).

with equality at the candidate.

The node potentials θˉ\bar{\theta} uniquely maximize β⊤θ\beta^\top\theta on P(xˉ)\mathcal{P}(\bar{x}). To see this, fix x=xˉx=\bar{x} and take any θ∈P(xˉ)\theta\in\mathcal{P}(\bar{x}). The slack of the aggregated inequality is

ℓ(xˉ)−β⊤θ=∑a∈Twa(qa(xˉ)−Da⊤θ)≥0.\ell(\bar{x})-\beta^\top\theta=\sum_{a\in T}w_a\left(q_a(\bar{x})-D_a^\top\theta\right)\ge0.

The candidate θˉ\bar{\theta} attains the upper bound ℓ(xˉ)\ell(\bar{x}) because every arc of TT is active there. Any potential vector θ\theta attaining the same bound must make every slack in the sum zero, since the slacks are nonnegative and all weights are strictly positive. Hence DaT(θ−θˉ)=0D_a^T(\theta-\bar{\theta})=0 for every a∈Ta\in T, so the displacement θ−θˉ\theta-\bar{\theta} has equal values at the endpoints of every tree arc. Connectivity makes this displacement constant on all nodes, and θt=θˉt=0\theta_t=\bar{\theta}_t=0 makes the constant zero. In other words, θ\theta must be equal to θˉ\bar{\theta}.

Applying the convex-combination representation in (11) to fβf_\beta gives the attained identity

f^β(xˉ)=max⁡{βTθ:(xˉ,θ)∈conv⁡(S)}.(12)\hat{f}_\beta(\bar{x})=\max\{\beta^T\theta:(\bar{x},\theta)\in\operatorname{conv}(S)\}. \tag*{(12)}

Indeed, any convex combination of points of SS has objective at most the corresponding weighted integer-fiber values, and maximizing weights together with maximizing fiber potentials attain equality. Since conv⁡(S)⊆P\operatorname{conv}(S)\subseteq P, (12) gives f^β(xˉ)≤βTθˉ\hat{f}_\beta(\bar{x})\leq\beta^T\bar{\theta}. Equality holds if the candidate belongs to conv⁡(S)\operatorname{conv}(S). Conversely, if equality holds, an attaining hull potential also maximizes the objective βTθ\beta^T\theta over P(xˉ)P(\bar{x}), so uniqueness makes it θˉ\bar{\theta}.

The difference βTθˉ−f^β(xˉ)\beta^T\bar{\theta}-\hat{f}_\beta(\bar{x}) is the maximum attainable violation vβ(xˉ,θˉ)v_\beta(\bar{x},\bar{\theta}) defined in (9). We have shown that this difference is nonnegative and vanishes precisely when the candidate belongs to conv⁡(S)\operatorname{conv}(S). A vertex of PP in conv⁡(S)\operatorname{conv}(S) must itself belong to SS, since all positively weighted points in a convex representation from S⊆PS\subseteq P must equal that vertex. A vertex with fractional leader coordinates is therefore outside conv⁡(S)\operatorname{conv}(S), proving the final assertion.

Proof of Proposition 4. A displacement preserving all active arc equalities is constant on each component CℓC_\ell and zero on C0C_0 after imposing θt=0\theta_t=0. Write its remaining component values as δ1,…,δc−1\delta_1,\ldots,\delta_{c-1}. It preserves the active added cuts precisely when Γδ=0\Gamma\boldsymbol{\delta}=0. If Γ\Gamma had rank less than c−1c-1, a nonzero such displacement of sufficiently small magnitude in either direction would preserve every constraint of P+P^+, contradicting the vertex assumption. Thus rank Γ=c−1\Gamma=c-1.

The selected forest has ∣V∣−c|V|-c arcs and forces componentwise constancy. The selected c−1c-1 rows of Γ\Gamma force all remaining component shifts to vanish. Consequently, the ∣V∣−1|V|-1 selected rows have full rank in the free potential coordinates, which is the minimum possible cardinality. This also covers c=1c=1, when no added row is needed.

Each selected potential coefficient belongs to B\mathcal{B}, so their positive combination β\beta also belongs to B\mathcal{B}. 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 β≠0\beta\ne0.

The weighted sum of the selected inequalities is

βTθ≤ℓ(x),ℓ(x)=∑a∈Fwaqa(x)+∑j∈Jμjℓj(x).\beta^T\theta\leq\ell(x),\qquad \ell(x)=\sum_{a\in F}w_aq_a(x)+\sum_{j\in J}\mu_j\ell_j(x).

It is valid for P+P^+ and active at the candidate. Equality in the fiber at xˉ\bar{x} forces every selected inequality to be active, and full rank makes θˉ\bar{\theta} its unique solution. Hence θˉ\bar{\theta} uniquely maximizes βTθ\beta^T\theta over P+(xˉ)P^+(\bar{x}). Because conv⁡(S)⊆P+\operatorname{conv}(S)\subseteq P^+, the attained identity (12) gives exactly the same zero-violation equivalence as in the preceding proof. Finally, a vertex of P+P^+ with fractional leader coordinates cannot belong to conv⁡(S)\operatorname{conv}(S), since S⊆P+S\subseteq P^+ and its leader coordinates are binary.

Complexity of separation

Proof of Proposition 5. Assume rational data with binary encoding. Let s1,…,sns_1,\ldots,s_n be positive integer weights. The Partition problem [15] asks whether there exists a subset I⊆{1,…,n}I \subseteq\{1,\ldots,n\} such that

∑i∈Isi=∑i∉Isi\sum_{i\in I} s_i = \sum_{i\notin I} s_i

Write W=∑i=1nsiW=\sum_{i=1}^n s_i. Set X={0,1}n\mathcal{X}=\{0,1\}^n and give the two parallel arcs costs

qa1(x)=2sTx−W,qa2(x)=0.q_{a_1}(\mathbf{x})=2\mathbf{s}^{\mathsf{T}}\mathbf{x}-W,\qquad q_{a_2}(\mathbf{x})=0.

The point xˉ=121\bar{\mathbf{x}}=\frac{1}{2}\mathbf{1}, θˉr=θˉt=0\bar{\theta}_r=\bar{\theta}_t=0 belongs to P\mathcal{P}, with both arc inequalities active. Its root-supply function is ϕ(x)=min⁡{2sTx−W,0}\phi(\mathbf{x})=\min\{2\mathbf{s}^{\mathsf{T}}\mathbf{x}-W,0\}, so ϕ^≤0\hat{\phi}\leq0. The candidate belongs to Rr\mathcal{R}_r if and only if ϕ^(xˉ)=0\hat{\phi}(\bar{\mathbf{x}})=0.

If x∗∈{0,1}n\mathbf{x}^*\in\{0,1\}^n satisfies 2sTx∗=W2\mathbf{s}^{\mathsf{T}}\mathbf{x}^*=W, then its complement also does, and both have follower value zero. Their average is xˉ\bar{\mathbf{x}}, so (11) gives ϕ^(xˉ)=0\hat{\phi}(\bar{\mathbf{x}})=0. 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 ϕ(xk)=0\phi(\mathbf{x}^k)=0, hence 2sTxk≥W2\mathbf{s}^{\mathsf{T}}\mathbf{x}^k\geq W. Their weighted average satisfies

∑k=1Kαk2sTxk=2sTxˉ=W.\sum_{k=1}^{K}\alpha_k 2\mathbf{s}^{\mathsf{T}}\mathbf{x}^k=2\mathbf{s}^{\mathsf{T}}\bar{\mathbf{x}}=W.

Every positively weighted assignment therefore satisfies equality and solves the Partition instance with weights (s1,…,sn)(s_1,\ldots,s_n). 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 ϕ^\hat{\phi} decides it by comparison with zero. Both tasks are therefore NP-hard as well.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11]DeNegre, S.: Interdiction and discrete bilevel linear programming. Ph.D. thesis, Lehigh University, USA (2011)
  12. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_dj4tqs8d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI Codex (GPT-6)

View statement
Looking for related papers…
Contents