pith. sign in

arxiv: 2412.13235 · v4 · submitted 2024-12-17 · 💻 cs.AI · cs.DM

Logic-Constrained Shortest Paths for Flight Planning

Ricardo Euler , Pedro Maristany de las Casas , Ralf Bornd\"orfer This is my paper

Pith reviewed 2026-05-23 06:37 UTC · model grok-4.3

classification 💻 cs.AI cs.DM
keywords logic-constrained shortest pathsflight planningbranch and boundtraffic flow restrictionssatisfiability constraintsshortest path algorithms
0
0 comments X

The pith

A branch-and-bound algorithm for logic-constrained shortest paths computes aircraft routes under real traffic restrictions an order of magnitude faster when its control rules are chosen well.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a branch-and-bound procedure that finds shortest paths on a graph while also satisfying logical constraints on which edges or nodes may be used together. This setting appears in flight planning once air traffic authorities impose traffic flow restrictions that cannot be expressed by simple edge costs. The procedure exposes three tunable parts: how to pick the next node to explore, how to split the search space, and which variables form the conflict set that receives the split. Tailored versions of standard rules are derived for each part, and their effect on search effort is analyzed. On a global flight network paired with roughly 20000 real restrictions, suitable combinations of the three parts reduce running time by roughly a factor of ten compared with generic choices.

Core claim

The logic-constrained shortest path problem can be solved by a branch-and-bound algorithm whose performance depends on the choice of node selection rule, branching rule, and the set of variables called the conflict; tailored variants of these rules, together with an analysis of the conflict's theoretical effect, produce solutions an order of magnitude faster than uninformed selections when applied to flight planning instances.

What carries the argument

The branch-and-bound algorithm for the logic-constrained shortest path problem, whose performance is governed by the node selection rule, the branching rule, and the conflict (the set of variables to which the branching rule is applied).

If this is right

  • Aircraft routes that obey thousands of simultaneous traffic flow restrictions can be computed on a worldwide network without violating any single restriction.
  • Dynamic shortest-path subroutines can be embedded inside the branch-and-bound search to reduce the cost of repeated distance queries.
  • The theoretical impact of different conflict definitions on the size of the search tree can be used to prune unproductive branches earlier.
  • Public release of the flight graph and restriction set allows direct comparison of any new logic-constrained solver against the reported baselines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same three-rule framework could be tested on other routing tasks that combine metric costs with logical exclusion rules, such as pipeline routing or vehicle routing with time windows.
  • Independent implementers can now measure whether the reported order-of-magnitude gap persists when the underlying shortest-path oracle is replaced by a different dynamic algorithm.
  • The conflict analysis may suggest analogous variable-selection heuristics for other satisfiability-augmented shortest-path problems that do not yet have tailored branching rules.

Load-bearing premise

The modeling of traffic flow restrictions as satisfiability constraints on the routing graph accurately captures the real constraints imposed by ATC authorities without introducing modeling errors that would invalidate the computed routes.

What would settle it

Running the algorithm on the released global flight graph together with the 20000 restrictions and checking whether the fastest rule combinations produce feasible routes at the claimed speeds while any slower combinations fail to match reported runtimes.

Figures

Figures reproduced from arXiv: 2412.13235 by Pedro Maristany de las Casas, Ralf Bornd\"orfer, Ricardo Euler.

Figure 1
Figure 1. Figure 1: The upper figure depicts all 19300 airway segments that are contained in at least one [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: DAG D in which the arc (v2, v4) is enforced. Right: Topological sorting of D. 3.3 Validation and Conflict Generation The shortest path p computed in Line 18 induces an assignment Tp. By construction of G∣T , p agrees with T. Hence, it agrees with T ∶= T ∪ Tp (Line 20). Since Tp assigns all graph variables, T does as well, and the formula Φ∣T contains only free variables. If Φ∣T is satisfiable, we hav… view at source ↗
Figure 3
Figure 3. Figure 3: Consider the LCSPP instance (G, Φ, ρ, s, t) given by the above graph G, the CNF formula Φ = (y ∨ z) ∧ (y ∨ ¬z) over the variable set X ∶= Y ∪ Z with Y ∶= {o, x, y} and Z ∶= {z} and the bijection ρ ∶ {(sv), (vt), (vt)} → Y with ρ(sv) = o, ρ(vt) = x and ρ(st) = y. The shortest path in G∣∅ is (s, v, t) with a weight of 2. However, p induces the assignment {¬y} which conflicts with Φ. Branching on z results in… view at source ↗
Figure 4
Figure 4. Figure 4: Height profile and skypath of PedricAir (orange) compared to two historic trajectories [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Left: The speed triangle of the artificial aircraft. When climbing along an arc, the [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Cumulative frequency plot of solved instances per number of B&B nodes (left) and [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Cumulative frequency plot of solved instances per number of B&B nodes (left) and [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of the best branching rule SUP on regular and graph conflicts using best￾first search node selection with the clause branching rule. We plot the percentage of instances solved depending on the number of B&B nodes (left) and on the SP queries (right). The branching rule that attains the least number of B&B nodes is, unsurprisingly, strong branching. This is paid for by computing the most SP queri… view at source ↗
Figure 9
Figure 9. Figure 9: Comparison of dynamic shortest path algorithms (LPA [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Performance of the MIP approach on all 106 domestic OD pairs. Left: Run time of the [PITH_FULL_IMAGE:figures/full_fig_p025_10.png] view at source ↗
read the original abstract

The logic-constrained shortest path problem (LCSPP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSPP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict. While node selection and branching rules have been long studied in the MIP and SAT communities, most of them cannot be applied out of the box for the LCSPP. We review the existing literature and develop tailored variants of the most prominent rules. The conflict, the set of variables to which the branching rule is applied, is unique to the LCSPP. We analyze its theoretical impact on the B&B algorithm. In the second part of the paper, we show how to model the flight planning problem with TFRs as an LCSPP and solve it using the branch and bound algorithm. We demonstrate the algorithm's efficiency on a dataset consisting of a global flight graph and a set of around 20000 real TFRs obtained from our industry partner Lufthansa Systems GmbH. We make this dataset publicly available. Finally, we conduct an empirical in-depth analysis of dynamic shortest path algorithms, node selection rules, branching rules and conflicts. Carefully choosing an appropriate combination yields an improvement of an order of magnitude compared to an uninformed choice.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims to develop a branch-and-bound algorithm for the logic-constrained shortest path problem (LCSPP) with tailored node selection rules, branching rules, and conflict analysis; it models flight planning under ~20,000 real traffic flow restrictions (TFRs) as an LCSPP instance, solves it on a global flight graph from Lufthansa data (made public), and reports an order-of-magnitude runtime improvement from careful choice of B&B components.

Significance. If the LCSPP modeling of TFRs is faithful to real ATC constraints and the empirical gains are robust, the work supplies a practical algorithmic framework plus a reusable dataset for incorporating complex safety constraints into flight planning. The public dataset and theoretical analysis of the conflict set are clear strengths.

major comments (2)
  1. [Modeling of the flight planning problem as LCSPP] The modeling of ~20,000 real TFRs as satisfiability constraints on the routing graph (described in the second part of the paper) is load-bearing for the practical claim, yet the manuscript provides no validation against actual ATC-approved routes, no expert review of the encoding, and no discussion of whether conditional logic or spatial interactions are omitted. If the encoding introduces modeling errors, the reported speedups on the derived LCSPP instance do not translate to the motivating application.
  2. [Empirical in-depth analysis] The headline empirical claim of an order-of-magnitude improvement (abstract and empirical analysis section) is presented without error bars, statistical significance tests, or ablation controls isolating the contributions of node selection, branching rules, and conflict choices; this weakens confidence that the gains are attributable to the proposed tailoring rather than instance-specific effects.
minor comments (1)
  1. [Abstract] The abstract states the performance claim without any mention of variance, statistical testing, or controls, which should be added for clarity even if the full paper contains the details.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the constructive review and for recognizing the strengths of the public dataset and conflict analysis. We address each major comment below with planned revisions where feasible.

read point-by-point responses

  1. Referee: [Modeling of the flight planning problem as LCSPP] The modeling of ~20,000 real TFRs as satisfiability constraints on the routing graph (described in the second part of the paper) is load-bearing for the practical claim, yet the manuscript provides no validation against actual ATC-approved routes, no expert review of the encoding, and no discussion of whether conditional logic or spatial interactions are omitted. If the encoding introduces modeling errors, the reported speedups on the derived LCSPP instance do not translate to the motivating application.

    Authors: The encodings were developed directly from real TFR descriptions supplied by Lufthansa Systems, our industry partner, and are detailed in Section 4. We will add a new subsection explicitly discussing modeling assumptions, including potential omissions around conditional logic and spatial interactions. However, direct validation against ATC-approved routes is not feasible within the paper as such proprietary route data is outside the public dataset scope. revision: partial

  2. Referee: [Empirical in-depth analysis] The headline empirical claim of an order-of-magnitude improvement (abstract and empirical analysis section) is presented without error bars, statistical significance tests, or ablation controls isolating the contributions of node selection, branching rules, and conflict choices; this weakens confidence that the gains are attributable to the proposed tailoring rather than instance-specific effects.

    Authors: The empirical section already compares multiple combinations of the three components across the full dataset and shows consistent gains. We agree additional rigor is warranted and will revise to include explicit ablation tables isolating each component, error bars on runtime metrics over instance subsets, and statistical significance tests (e.g., Wilcoxon) where variance exists. The deterministic nature of the solver limits some statistical options, but these additions will strengthen attribution of the gains. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external literature and real-world data.

full rationale

The paper reviews existing MIP/SAT literature to adapt node selection and branching rules, introduces a conflict concept unique to LCSPP with theoretical analysis, models TFRs as satisfiability constraints on a routing graph, and evaluates the resulting B&B algorithm on a public dataset of ~20000 real TFRs from Lufthansa. No equations or claims reduce by construction to fitted parameters, self-defined quantities, or load-bearing self-citations. The order-of-magnitude improvement is an empirical observation on external data, not a statistical artifact of internal fitting. The modeling step is presented as a direct encoding without circular validation loops.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard graph algorithms and MIP/SAT branching techniques as background; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond the modeling choice of representing TFRs as logical constraints.

axioms (2)
  • standard math Standard shortest-path algorithms such as Dijkstra or A* can be extended with satisfiability constraints via branch-and-bound.
    Invoked when describing the base LCSPP formulation and the B&B framework.
  • domain assumption The routing graph and TFRs can be faithfully represented as a graph plus logical constraints without loss of real-world validity.
    Central modeling step when casting flight planning as LCSPP.

pith-pipeline@v0.9.0 · 5821 in / 1329 out tokens · 22499 ms · 2026-05-23T06:37:26.445601+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

100 extracted references · 100 canonical work pages

  1. [1]

    Blanco, R

    M. Blanco, R. Bornd¨ orfer, N.-D. Hoang, A. Kaier, T. Schlechte, S. Schlobach, The Shortest Path Problem with Crossing Costs, ZIB Report 16-70, Zuse Institute Berlin, 2016. URL: https://opus4.kobv.de/opus4-zib/files/6124/ZR-16-70.pdf

    work page 2016

  2. [2]

    Blanco, R

    M. Blanco, R. Bornd¨ orfer, N.-D. Hoang, A. Kaier, A. Schienle, T. Schlechte, S. Schlobach, Solving time dependent shortest path problems on airway networks using super-optimal wind, in: M. Goerigk, R. F. Werneck (Eds.), 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, number 54 in Open Access Series in Info...

    work page doi:10.4230/oasics.atmos.2016.12 2016

  3. [3]

    Blanco, R

    M. Blanco, R. Bornd¨ orfer, N. D. Ho` ang, A. Kaier, P. Maristany de las Casas, T. Schlechte, S. Schlobach, Cost projection methods for the shortest path problem with crossing costs, in: G. D’Angelo, T. Dollevoet (Eds.), 17th Workshop on Algorithmic Approaches for Trans- portation Modelling, Optimization, and Systems, number 59 in OpenAccess Series in Inf...

    work page doi:10.4230/oasics.atmos.2017.15 2017

  4. [4]

    A. N. Knudsen, M. Chiarandini, K. S. Larsen, Constraint handling in flight planning, in: J. C. Beck (Ed.), Principles and Practice of Constraint Programming, number 10416 in Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 354–369. doi:10.1007/978-3-319-66158-2_23 . 26 R. Euler, P. Maristany, R. Bornd¨ orfer LCSP for Flight Planning

    work page doi:10.1007/978-3-319-66158-2_23 2017

  5. [5]

    A. N. Knudsen, M. Chiarandini, K. S. Larsen, Heuristic variants of A∗search for 3d flight planning, in: W.-J. van Hoeve (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research, number 10848 in Lecture Notes in Computer Science, Springer, 2018, pp. 361–376. doi: 10.1007/978-3-319-93031-2_26

    work page doi:10.1007/978-3-319-93031-2_26 2018

  6. [6]

    Schienle, P

    A. Schienle, P. Maristany de las Casas, M. Blanco, A priori search space pruning in the flight planning problem, in: V. Cacchiani, A. Marchetti-Spaccamela (Eds.), 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, num- ber 75 in Open Access Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum f¨...

    work page doi:10.4230/oasics.atmos.2019.8 2019

  7. [7]

    K¨ uhner, Shortest Paths with Boolean Constraints, Master’s thesis, Freie Universit¨ at Berlin, Department of Mathematics, 2020

    A. K¨ uhner, Shortest Paths with Boolean Constraints, Master’s thesis, Freie Universit¨ at Berlin, Department of Mathematics, 2020

    work page 2020

  8. [8]

    Blanco, R

    M. Blanco, R. Bornd¨ orfer, P. Maristany de las Casas, An A* algorithm for flight planning based on idealized vertical profiles, in: M. D’Emidio, N. Lindner (Eds.), 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, number 106 in Open Access Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum f...

    work page doi:10.4230/oasics.atmos.2022.1 2022

  9. [9]

    Ramalingam, T

    G. Ramalingam, T. Reps, An incremental algorithm for a generalization of the shortest- path problem, Journal of Algorithms 21 (1996) 267–305. doi: 10.1006/jagm.1996.0046

    work page doi:10.1006/jagm.1996.0046 1996

  10. [10]

    Ramalingam, T

    G. Ramalingam, T. Reps, On the computational complexity of dynamic graph problems, Theoretical Computer Science 158 (1996) 233–277. doi: 10.1016/0304-3975(95)00079-8

    work page doi:10.1016/0304-3975(95)00079-8 1996

  11. [11]

    Frigioni, A

    D. Frigioni, A. Marchetti-Spaccamela, U. Nanni, Fully dynamic algorithms for maintaining shortest paths trees, Journal of Algorithms 34 (2000) 251–281. doi: 10.1006/jagm.1999. 1048

    work page doi:10.1006/jagm.1999 2000

  12. [12]

    Narvaez, K.-Y

    P. Narvaez, K.-Y. Siu, H.-Y. Tzeng, New dynamic algorithms for shortest path tree com- putation, IEEE/ACM Transactions on Networking 8 (2000) 734–746. doi: 10.1109/90. 893870

    work page doi:10.1109/90 2000

  13. [13]

    Koenig, M

    S. Koenig, M. Likhachev, D. Furcy, Lifelong planning A⋆, Artificial Intelligence 155 (2004) 93–146. doi:10.1016/j.artint.2003.12.001

    work page doi:10.1016/j.artint.2003.12.001 2004

  14. [14]

    Bauer, D

    R. Bauer, D. Wagner, Batch dynamic single-source shortest-path algorithms: An experi- mental study, in: J. Vahrenhold (Ed.), Experimental Algorithms, number 5526 in Lecture Notes in Computer Science, Springer, 2009, pp. 51–62. doi: 10.1007/978-3-642-02011-7_ 7

    work page doi:10.1007/978-3-642-02011-7_ 2009

  15. [15]

    D’Andrea, M

    A. D’Andrea, M. D’Emidio, D. Frigioni, S. Leucci, G. Proietti, Experimental evaluation of dynamic shortest path tree algorithms on homogeneous batches, in: J. Gudmundsson, J. Katajainen (Eds.), Experimental Algorithms, Springer International Publishing, 2014, pp. 283–294. doi: 10.1007/978-3-319-07959-2_24

    work page doi:10.1007/978-3-319-07959-2_24 2014

  16. [16]

    Bellman, On a routing problem, Quarterly of Applied Mathematics 16 (1958) 87–90

    R. Bellman, On a routing problem, Quarterly of Applied Mathematics 16 (1958) 87–90. doi:10.1090/qam/102435

    work page doi:10.1090/qam/102435 1958

  17. [17]

    E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959) 269–271

    work page 1959

  18. [18]

    R. W. Floyd, Algorithm 97: Shortest path, Communications of the ACM 5 (1962) 345–345. 27 R. Euler, P. Maristany, R. Bornd¨ orfer LCSP for Flight Planning

    work page 1962

  19. [19]

    K. L. Cooke, E. Halsey, The shortest route through a network with time-dependent intern- odal transit times, Journal of Mathematical Analysis and Applications 14 (1966) 493–498. doi:10.1016/0022-247X(66)90009-6

    work page doi:10.1016/0022-247x(66)90009-6 1966

  20. [20]

    E. Q. V. Martins, On a multicriteria shortest path problem, European Journal of Opera- tional Research 16 (1984) 236–245. doi: 10.1016/0377-2217(84)90077-8

    work page doi:10.1016/0377-2217(84)90077-8 1984

  21. [21]

    Gandibleux, F

    X. Gandibleux, F. Beugnies, S. Randriamasy, Martins’ algorithm revisited for multi- objective shortest path problems with a maxmin cost function, 4OR 4 (2006) 47–59. doi:10.1007/s10288-005-0074-x

    work page doi:10.1007/s10288-005-0074-x 2006

  22. [22]

    Delling, T

    D. Delling, T. Pajor, R. F. Werneck, Round-based public transit routing, Transportation Science 49 (2015) 591–604. doi: 10.1287/trsc.2014.0534

    work page doi:10.1287/trsc.2014.0534 2015

  23. [23]

    Parmentier, Algorithms for non-linear and stochastic resource constrained shortest path, Mathematical Methods of Operations Research 89 (2019) 281–317

    A. Parmentier, Algorithms for non-linear and stochastic resource constrained shortest path, Mathematical Methods of Operations Research 89 (2019) 281–317. doi: 10.1007/ s00186-018-0649-x

    work page 2019

  24. [25]

    F. A. Aloul, B. Al Rawi, M. Aboelaze, Identifying the shortest path in large networks using boolean satisfiability, in: 2006 3rd International Conference on Electrical and Electronics Engineering, IEEE, 2006, pp. 1–4. doi: 10.1109/ICEEE.2006.251924

    work page doi:10.1109/iceee.2006.251924 2006

  25. [26]

    H. N. Gabow, S. N. Maheshwari, L. J. Osterweil, On two problems in the generation of program test paths, IEEE Transactions on Software Engineering SE-2 (1976) 227–231. doi:10.1109/TSE.1976.233819

    work page doi:10.1109/tse.1976.233819 1976

  26. [27]

    Pamuk, T

    B. Pamuk, T. ¨Oncan, ˙I. K. Altınel, An efficient branch-and-bound algorithm for the one- to-many shortest path problem with additional disjunctive conflict constraints, European Journal of Operational Research 324 (2025) 398–413. doi: 10.1016/j.ejor.2025.01.044

    work page doi:10.1016/j.ejor.2025.01.044 2025

  27. [28]

    Barrett, R

    C. Barrett, R. Jacob, M. Marathe, Formal-language-constrained path problems, SIAM Journal on Computing 30 (2000) 809–837. doi: 10.1137/S0097539798337716

    work page doi:10.1137/s0097539798337716 2000

  28. [29]

    Nishino, N

    M. Nishino, N. Yasuda, S.-i. Minato, M. Nagata, BDD-constrained search: A unified approach to constrained shortest path problems, Proceedings of the AAAI Conference on Artificial Intelligence 29 (2015). doi: 10.1609/aaai.v29i1.9373

    work page doi:10.1609/aaai.v29i1.9373 2015

  29. [30]

    Kolman, O

    P. Kolman, O. Pangr´ ac, On the complexity of paths avoiding forbidden pairs, Discrete Applied Mathematics 157 (2009) 2871–2876. doi: 10.1016/j.dam.2009.03.018

    work page doi:10.1016/j.dam.2009.03.018 2009

  30. [31]

    Kov´ aˇ c, Complexity of the path avoiding forbidden pairs problem revisited, Discrete Applied Mathematics 161 (2013) 1506–1512

    J. Kov´ aˇ c, Complexity of the path avoiding forbidden pairs problem revisited, Discrete Applied Mathematics 161 (2013) 1506–1512. doi: 10.1016/j.dam.2012.12.022

    work page doi:10.1016/j.dam.2012.12.022 2013

  31. [32]

    Blanco, R

    M. Blanco, R. Bornd¨ orfer, M. Br¨ uckner, N. D. Ho` ang, T. Schlechte, On the path avoiding forbidden pairs polytope, Electronic Notes in Discrete Mathematics 50 (2015) 343–348. doi:10.1016/j.endm.2015.07.057

    work page doi:10.1016/j.endm.2015.07.057 2015

  32. [33]

    Ferone, P

    D. Ferone, P. Festa, M. Salani, Branch and bound and dynamic programming approaches for the path avoiding forbidden pairs problem, in: R. Cerulli, M. Dell’Amico, F. Guer- riero, D. Pacciarelli, A. Sforza (Eds.), Optimization and Decision Science: ODS, Virtual Conference, November 19, 2020, number 7 in AIRO Springer Series, Springer International Publishin...

    work page doi:10.1007/978-3-030-86841-3_19 2020

  33. [34]

    Darmann, U

    A. Darmann, U. Pferschy, J. Schauer, G. J. Woeginger, Paths, trees and matchings under disjunctive constraints, Discrete Applied Mathematics 159 (2011) 1726–1735. doi:10.1016/ j.dam.2010.12.016

    work page 2011

  34. [35]

    Aspvall, M

    B. Aspvall, M. F. Plass, R. E. Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters 8 (1979) 121–123. doi:https://doi.org/10.1016/0020-0190(79)90002-4

    work page doi:10.1016/0020-0190(79)90002-4 1979

  35. [36]

    S. A. Cook, The Complexity of Theorem-Proving Procedures, 1 ed., Association for Com- puting Machinery, 2023, p. 143–152. URL: https://dl.acm.org/doi/10.1145/3588287. 3588297

    work page doi:10.1145/3588287 2023

  36. [37]

    Dibbelt, Multimodal Route and Tour Planning in Urban Environments, Phd thesis, Karlsruher Institut f¨ ur Technologie, 2016

    J. Dibbelt, Multimodal Route and Tour Planning in Urban Environments, Phd thesis, Karlsruher Institut f¨ ur Technologie, 2016

    work page 2016

  37. [38]

    R. E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transac- tions on Computers 100 (1986) 677–691. doi: 10.1109/TC.1986.1676819

    work page doi:10.1109/tc.1986.1676819 1986

  38. [39]

    Desrochers, La fabrication d’horaires de travail pour les conducteurs d’autobus par une m´ ethode de g´ en´ eration de colonnes, Ph.D

    M. Desrochers, La fabrication d’horaires de travail pour les conducteurs d’autobus par une m´ ethode de g´ en´ eration de colonnes, Ph.D. thesis, Universit´ e de Montr´ eal, Centre de recherche sur les transports, 1986

    work page 1986

  39. [40]

    Irnich, G

    S. Irnich, G. Desaulniers, Shortest Path Problems with Resource Constraints, Springer US, 2005, pp. 33–65. doi: 10.1007/0-387-25486-2_2

    work page doi:10.1007/0-387-25486-2_2 2005

  40. [41]

    H. C. Joksch, The shortest route problem with constraints, Journal of Mathematical Analysis and Applications 14 (1966) 191–197. doi: 10.1016/0022-247X(66)90020-5

    work page doi:10.1016/0022-247x(66)90020-5 1966

  41. [42]

    Dumitrescu, N

    I. Dumitrescu, N. Boland, Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem, Networks 42 (2003) 135–153. doi: 10.1002/net. 10090

    work page doi:10.1002/net 2003

  42. [43]

    O. J. Smith, N. Boland, H. Waterer, Solving shortest path problems with a weight constraint and replenishment arcs, Computers & Operations Research 39 (2012) 964–984. doi: 10. 1016/j.cor.2011.07.017

    work page 2012

  43. [44]

    M. Baum, J. Dibbelt, A. Gemsa, D. Wagner, T. Z¨ undorf, Shortest feasible paths with charging stops for battery electric vehicles, Transportation Science 53 (2019) 1627–1655. doi:10.1287/trsc.2018.0889

    work page doi:10.1287/trsc.2018.0889 2019

  44. [45]

    Lozano, A

    L. Lozano, A. L. Medaglia, On an exact method for the constrained shortest path problem, Computers & Operations Research 40 (2013) 378–384. doi: https://doi.org/10.1016/j. cor.2012.07.008

    work page doi:10.1016/j 2013

  45. [46]

    B. W. Thomas, T. Calogiuri, M. Hewitt, An exact bidirectional A approach for solving resource-constrained shortest path problems, Networks 73 (2019) 187–205. doi: 10.1002/ net.21856

    work page 2019

  46. [47]

    Z. Ren, Z. B. Rubinstein, S. F. Smith, S. Rathinam, H. Choset, ERCA: A new approach for the resource constrained shortest path problem, IEEE Transactions on Intelligent Trans- portation Systems 24 (2023) 14994–15005. doi: 10.1109/TITS.2023.3293039

    work page doi:10.1109/tits.2023.3293039 2023

  47. [48]

    Ahmadi, G

    S. Ahmadi, G. Tack, D. Harabor, P. Kilby, Weight constrained path finding with bidirec- tional A*, Proceedings of the International Symposium on Combinatorial Search 15 (2022) 2–10. doi:10.1609/socs.v15i1.21746. 29 R. Euler, P. Maristany, R. Bornd¨ orfer LCSP for Flight Planning

    work page doi:10.1609/socs.v15i1.21746 2022

  48. [49]

    Ahmadi, G

    S. Ahmadi, G. Tack, D. Harabor, P. Kilby, M. Jalili, Enhanced methods for the weight constrained shortest path problem, Networks 84 (2024) 3–30. doi: 10.1002/net.22210

    work page doi:10.1002/net.22210 2024

  49. [50]

    Ahmadi, A

    S. Ahmadi, A. Raith, M. Jalili, Resource constrained pathfinding with A* and negative weights, 2025. doi:10.48550/arXiv.2503.11037. arXiv:2503.11037, arXiv preprint

    work page doi:10.48550/arxiv.2503.11037 2025

  50. [51]

    J. E. Beasley, N. Christofides, An algorithm for the resource constrained shortest path problem, Networks 19 (1989) 379–394. doi: 10.1002/net.3230190402

    work page doi:10.1002/net.3230190402 1989

  51. [52]

    Bornd¨ orfer, M

    R. Bornd¨ orfer, M. Gr¨ otschel, A. L¨ obel, Scheduling Duties by Adaptive Column Genera- tion, ZIB Report 01-02, Zuse Institute Berlin, 2001. URL: https://webdoc.sub.gwdg.de/ ebook/e/2003/zib_2/reports/ZR-01-02.pdf

    work page 2001

  52. [53]

    L. D. P. Pugliese, F. Guerriero, A survey of resource constrained shortest path problems: Exact solution approaches, Networks 62 (2013) 183–200. doi: 10.1002/net.21511

    work page doi:10.1002/net.21511 2013

  53. [54]

    Festa, Constrained shortest path problems: State-of-the-art and recent advances, in: 2015 17th International Conference on Transparent Optical Networks (ICTON), 2015, pp

    P. Festa, Constrained shortest path problems: State-of-the-art and recent advances, in: 2015 17th International Conference on Transparent Optical Networks (ICTON), 2015, pp. 1–17. doi:10.1109/ICTON.2015.7193456

    work page doi:10.1109/icton.2015.7193456 2015

  54. [55]

    Irnich, D

    S. Irnich, D. Villeneuve, The shortest-path problem with resource constraints and k-cycle elimination for k ≥3, INFORMS Journal on Computing 18 (2006) 391–406. doi: 10.1287/ ijoc.1040.0117

    work page arXiv 2006

  55. [56]

    Villeneuve, G

    D. Villeneuve, G. Desaulniers, The shortest path problem with forbidden paths, European Journal of Operational Research 165 (2005) 97–107. doi: 10.1016/j.ejor.2004.01.032

    work page doi:10.1016/j.ejor.2004.01.032 2005

  56. [57]

    Eppstein, Finding the k shortest paths, SIAM Journal on Computing 28 (1998) 652–673

    D. Eppstein, Finding the k shortest paths, SIAM Journal on Computing 28 (1998) 652–673. doi:10.1137/S0097539795290477

    work page doi:10.1137/s0097539795290477 1998

  57. [58]

    Champarnaud, J.-E

    J.-M. Champarnaud, J.-E. Pin, A maxmin problem on finite automata, Discrete Applied Mathematics 23 (1989) 91–96. doi: 10.1016/0166-218X(89)90037-1

    work page doi:10.1016/0166-218x(89)90037-1 1989

  58. [59]

    Blanco, Optimization Algorithms for the Flight Planning Problem, Ph.D

    M. Blanco, Optimization Algorithms for the Flight Planning Problem, Ph.D. thesis, Freie Universit¨ at Berlin, 2023. doi:10.17169/refubium-40665

    work page doi:10.17169/refubium-40665 2023

  59. [60]

    Bornd¨ orfer, F

    R. Bornd¨ orfer, F. Danecker, M. Weiser, A discrete-continuous algorithm for globally optimal free flight trajectory optimization, in: M. D’Emidio, N. Lindner (Eds.), 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, number 106 in Open Access Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum...

    work page doi:10.4230/oasics.atmos.2022.2 2022

  60. [61]

    Bornd¨ orfer, F

    R. Bornd¨ orfer, F. Danecker, M. Weiser, A discrete-continuous algorithm for free flight planning, Algorithms 14 (2020). doi: 10.3390/a14010004

    work page doi:10.3390/a14010004 2020

  61. [62]

    Bornd¨ orfer, F

    R. Bornd¨ orfer, F. Danecker, M. Weiser, Error bounds for discrete-continuous free flight trajectory optimization, Journal of Optimization Theory and Applications 198 (2023) 830–

    work page 2023

  62. [63]

    doi:10.1007/s10957-023-02264-7

    work page doi:10.1007/s10957-023-02264-7

  63. [64]

    Bornd¨ orfer, F

    R. Bornd¨ orfer, F. Danecker, M. Weiser, Newton’s method for global free flight trajectory optimization, Operations Research Forum 4 (2023). doi: 10.1007/s43069-023-00238-z

    work page doi:10.1007/s43069-023-00238-z 2023

  64. [65]

    Jocas, Global Free Flight Optimization by a Hamilton-Jacobi-Bellman Approach, Mas- ter’s thesis, Technische Universit¨ at Berlin, 2024

    A. Jocas, Global Free Flight Optimization by a Hamilton-Jacobi-Bellman Approach, Mas- ter’s thesis, Technische Universit¨ at Berlin, 2024. 30 R. Euler, P. Maristany, R. Bornd¨ orfer LCSP for Flight Planning

    work page 2024

  65. [66]

    Kehlet Jensen, M

    C. Kehlet Jensen, M. Chiarandini, K. Larsen, Flight planning in free route airspaces, in: G. D’Angelo, T. Dollevoet (Eds.), 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, OpenAccess Series in Informat- ics (OASIcs), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017, pp. 14:1–14:14. doi:10.4230/OASIcs.A...

    work page doi:10.4230/oasics.atmos.2017.14 2017

  66. [67]

    Danecker, A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajec- tory Optimization, Ph.D

    F. Danecker, A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajec- tory Optimization, Ph.D. thesis, Freie Universit¨ at Berlin, 2023. URL:https://refubium. fu-berlin.de/handle/fub188/43811

    work page 2023

  67. [68]

    G. S. Tseitin, On the complexity of derivation in propositional calculus, in: J. H. Siekmann, G. Wrightson (Eds.), Automation of Reasoning 2: Classical Papers on Computational Logic 1967–1970, Springer, 1983, pp. 466–483. doi: 10.1007/978-3-642-81955-1_28

    work page doi:10.1007/978-3-642-81955-1_28 1967

  68. [69]

    Biere, A

    A. Biere, A. Fr¨ ohlich, Evaluating CDCL variable scoring schemes, in: M. Heule, S. Weaver (Eds.), Theory and Applications of Satisfiability Testing – SAT 2015, number 9340 in Lecture Notes in Computer Science, Springer International Publishing, 2015, pp. 405–422. doi:10.1007/978-3-319-24318-4\_29

    work page doi:10.1007/978-3-319-24318-4 2015

  69. [70]

    Davis, G

    M. Davis, G. Logemann, D. W. Loveland, A machine program for theorem-proving, Com- munications of the ACM 5 (1962) 394–397. doi: 10.1145/368273.368557

    work page doi:10.1145/368273.368557 1962

  70. [71]

    J. P. Marques-Silva, K. A. Sakallah, GRASP-a new search algorithm for satisfiability, in: Proceedings of International Conference on Computer Aided Design, 1996, pp. 220–227. doi:10.1109/ICCAD.1996.569607

    work page doi:10.1109/iccad.1996.569607 1996

  71. [72]

    M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, S. Malik, Chaff: engineering an efficient SAT solver, in: Proceedings of the 38th Annual Design Automation Conference, Association for Computing Machinery, 2001, p. 530–535. doi: 10.1145/378239.379017

    work page doi:10.1145/378239.379017 2001

  72. [73]

    Ryan, Efficient Algorithms for Clause-Learning SAT Solvers, Master’s thesis, Si- mon Fraser University, 2004

    L. Ryan, Efficient Algorithms for Clause-Learning SAT Solvers, Master’s thesis, Si- mon Fraser University, 2004. URL: https://summit.sfu.ca/_flysystem/fedora/sfu_ migrate/2725/b35038871.pdf

    work page 2004

  73. [74]

    Biere, M

    A. Biere, M. Heule, H. van Maaren, T. Walsh (Eds.), Handbook of Satisfiability, number 336 in Frontiers in Artificial Intelligence and Applications, 2 ed., IOS Press, 2021. doi: 10. 3233/FAIA336

    work page 2021

  74. [75]

    D. W. Loveland, A linear format for resolution, in: M. Laudet, D. Lacombe, L. Nolin, M. Sch¨ utzenberger (Eds.), Symposium on Automatic Demonstration, Springer, 1970, pp. 147–162. doi:10.1007/BFb0060630

    work page doi:10.1007/bfb0060630 1970

  75. [76]

    A. B. Kahn, Topological sorting of large networks, Communications of the ACM 5 (1962) 558–562. doi:10.1145/368996.369025

    work page doi:10.1145/368996.369025 1962

  76. [77]

    E´ en, N

    N. E´ en, N. S¨ orensson, An extensible SAT-solver, in: International conference on theory and applications of satisfiability testing, number 2919 in Lecture Notes in Computer Science, Springer, 2003, pp. 502–518. doi: 10.1007/978-3-540-24605-3_37

    work page doi:10.1007/978-3-540-24605-3_37 2003

  77. [78]

    J. P. Marques-Silva, I. Lynce, S. Malik, Conflict-driven clause learning SAT solvers, in: [73], 2021, pp. 133 –182. doi: 10.3233/FAIA336

    work page doi:10.3233/faia336 2021

  78. [79]

    Achterberg, Constraint Integer Programming, Ph.D

    T. Achterberg, Constraint Integer Programming, Ph.D. thesis, Technische Universit¨ at Berlin, 2007. doi: 10.14279/depositonce-1634. 31 R. Euler, P. Maristany, R. Bornd¨ orfer LCSP for Flight Planning

    work page doi:10.14279/depositonce-1634 2007

  79. [80]

    R. J. Dakin, A Tree-Search Algorithm for Mixed Integer Programming Problems, The Computer Journal 8 (1965) 250–255. doi: 10.1093/comjnl/8.3.250

    work page doi:10.1093/comjnl/8.3.250 1965

  80. [81]

    J. T. Linderoth, M. W. P. Savelsbergh, A computational study of search strategies for mixed integer programming, INFORMS Journal on Computing 11 (1999) 173–187. doi: 10. 1287/ijoc.11.2.173

    work page 1999

Showing first 80 references.