A dual ascent procedure for the set partitioning problem
From MaRDI portal
Publication:955334
DOI10.1016/j.disopt.2008.06.001zbMath1179.90276OpenAlexW1969951702MaRDI QIDQ955334
Aristide Mingozzi, Salvatore Ricciardelli, Marco Antonio Boschetti
Publication date: 19 November 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2008.06.001
linear programmingLagrangean relaxationsubgradient optimizationdual heuristicslarge scale set partitioning
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
The matching relaxation for a class of generalized set partitioning problems, Matheuristics: survey and synthesis, Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs, Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation, Modelling transfer line design problem via a set partitioning problem, A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints, A Lagrangian Relaxation Algorithm for Modularity Maximization Problem, A set covering based matheuristic for a real‐world city logistics problem, OPTIMAL SET-PARTITIONING BASED ON GROUP QUALITY LIKELIHOOD USING PARTITION-GROWING ALGORITHM
Uses Software
Cites Work
- The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems
- On some difficult linear programs coming from set partitioning
- Graph theoretic relaxations of set covering and set partitioning problems
- The volume algorithm: Producing primal solutions with a subgradient method
- A parallel primal-dual simplex algorithm
- A concurrent processing framework for the set partitioning problem
- A practical algorithm for computing a subadditive dual function for set partitioning
- A least-squares primal-dual algorithm for solving linear programming problems
- An exact algorithm for the simplified multiple depot crew scheduling problem
- An algorithm for large scale 0-1 integer programming with application to airline crew scheduling
- A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations
- A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
- Computational results with a primal-dual subproblem simplex method
- Constraint handling in genetic algorithms: the set partitioning problem
- Branch-and-Price: Column Generation for Solving Huge Integer Programs
- 2-Path Cuts for the Vehicle Routing Problem with Time Windows
- A Parallel, Linear Programming-based Heuristic for Large-Scale Set Partitioning Problems
- A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem
- Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
- Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
- A Multiplier Adjustment Approach for the Set Partitioning Problem
- Set Partitioning: A survey
- Solving Airline Crew Scheduling Problems by Branch-and-Cut
- A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem
- On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows
- A Set Partitioning Approach to the Crew Scheduling Problem
- A set‐partitioning‐based exact algorithm for the vehicle routing problem
