A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
From MaRDI portal
Publication:5643805
DOI10.1287/mnsc.18.7.401zbMath0234.90050OpenAlexW1984407615WikidataQ57253946 ScholiaQ57253946MaRDI QIDQ5643805
Publication date: 1972
Published in: Management Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/mnsc.18.7.401
Programming involving graphs or networks (90C35) Integer programming (90C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach, Fast computation of bounds for two-terminal network reliability, Algorithms for finding k-best perfect matchings, \(k\)-shortest routing of trains on shunting yards, Computing and listing \(st\)-paths in public transportation networks, On the hardness of bribery variants in voting with CP-nets, A Catalog of Formulations for the Network Pricing Problem, A note on \(K\) best network flows, Multiple-path selection for new highway alignments using discrete algorithms, Combinatorial algorithms for DNA sequence assembly, k-Best constrained bases of a matroid, On the bicriterion - minimal cost/minimal label - spanning tree problem, On discrete optimization with ordering, k-optimal solution sets for some polynomially solvable scheduling problems, On variations of the subset sum problem, Optimization over Degree Sequences, Enumerating \(K\) best paths in length order in DAGs, Evaluation and Enumeration Problems for Regular Path Queries, Efficiently Listing Bounded Length st-Paths, Polynomial-delay and polynomial-space enumeration of large maximal matchings, Solution Enumeration by Optimality in Answer Set Programming, An anytime algorithm for constrained stochastic shortest path problems with deterministic policies, Ranking arborescences in O(Km log n) time, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, Obtaining approximately optimal and diverse solutions via dispersion, Bilevel Programming: The Montreal School, A Trichotomy for Regular Trail Queries, A fuzzy model for NMT word alignment using quasi-perfect matching, Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs, An efficient time and space \(K\) point-to-point shortest simple paths algorithm, Assessing the reliability and the expected performance of a network under disaster risk, A bicriterion shortest path algorithm, Generalized dynamic programming methods in integer programming, Randomised enumeration of small witnesses using a decision oracle, On the \(K\)th best base of a matroid, An exact method for the double TSP with multiple stacks, A quantitative Doignon-Bell-Scarf theorem, Finding a given number of solutions to a system of fuzzy constraints, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits, On the spanning trees of weighted graphs, Ordered weighted average optimization in multiobjective spanning tree problem, On the spanning trees of weighted graphs, Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, An algorithm for ranking assignments using reoptimization, Algorithms to solve the knapsack constrained maximum spanning tree problem, Multiple Routing Strategies in a Labelled Network, Computing and Listing st-Paths in Public Transportation Networks, Finding the \(K\) shortest hyperpaths, Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems, Using shortest paths in some transshipment problems with concave costs, An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem, Suboptimal cuts: Their enumeration, weight and number, Traffic assignment model with fuzzy level of travel demand: An efficient algorithm based on quasi-logit formulas, The shortest path problem with forbidden paths, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, The interval subset sum problem, Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles, An algorithm for ranking paths that may contain cycles, An Experimental Study on Approximating k Shortest Simple Paths, Evaluating the demand for supergauge trucks-on-trains sevices in Western Europe, An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment, Distance confined path problem and separable integer programming, The school bus routing problem: a review, On the \(K\) shortest path trees problem, Finding the k Shortest Paths, Flows with unit path capacities and related packing and covering problems, Improved exact method for the double TSP with multiple stacks, Two-best solutions under distance constraints: The model and exemplary results for matroids, An O(K.n**4) algorithm for finding the K best cuts in a network, A theoretical and computational equilibria analysis of a multi-player kidney exchange program, Transducing Markov sequences, Flows with Unit Path Capacities and Related Packing and Covering Problems, Ranking One Million Simple Paths in Road Networks, Memetic algorithms, Forbidden Vertices, Structural tractability of enumerating CSP solutions, Generating the best \(K\) sequences in relocation problems, Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions, Solving some lexicographic multi-objective combinatorial problems, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs
