Delphi.science

Valid Inequalities for Bilevel 0-1 Shortest-Path Problems

Source: arxiv.org/abs/2611.18537

Bruno M. Pacheco, Margarida Carvalho, Kim Yu

arXivarxiv/2611.18537Nov 13, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.18537
curl -X POST /api/v1/records/arxiv/2611.18537/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18537/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'