On the complexity of the separation problem for rounded capacity inequalities

DOI10.1016/J.DISOPT.2017.02.003MaRDI QIDQ1751233zbMATH OpenOpenAlexFDO

Authors I. Diarrassouba

Publication date 24 May 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2017.02.003

zbMATH Keywords

branch-and-cutcapacitated vehicle routing problemcomputational complexitypolyhedral combinatorics

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The separation problem of rounded capacity inequalities: some polynomial cases
• The complexity of cover inequality separation
• Separation problems in the context of \(h\)-convexity
• On the complexity of separation from the knapsack polytope
• On the complexity of polyhedral separability
• Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
• Set separation, approximating multicones, and the Lipschitz maximum principle
• Separation of convex cones and extremal problems
• scientific article; zbMATH DE number 5044189
• On the separation of split cuts and related inequalities

Cites work

• A construction for binary matroids
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• Easy and difficult objective functions for max cut
• Handbooks in operations Research \& management science: Transportation
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• scientific article; zbMATH DE number 1749222 (Why is no real title available?)
• Odd Minimum Cut-Sets and b-Matchings
• On the capacitated vehicle routing problem
• Polyhedral study of the capacitated vehicle routing problem
• Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints
• Separating capacity constraints in the CVRP using tabu search
• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• The separation problem of rounded capacity inequalities: some polynomial cases
• The vehicle routing problem
• Two node-disjoint hop-constrained survivable network design and polyhedra
• Vehicle Routing

Cited in

(9)

• The separation problem of rounded capacity inequalities: some polynomial cases
• The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time
• A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
• Polynomial-time separation of enhanced reverse multistar inequalities
• A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics
• Improving the approximation ratio for capacitated vehicle routing
• Preprocessing to reduce vehicle capacity for routing problems
• Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem
• On the capacity inequalities for the heterogeneous vehicle routing problem

Describes a project that uses

Uses Software

• VRP
• CVRPSP

This page was built for publication: On the complexity of the separation problem for rounded capacity inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751233)