A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints

DOI10.1016/j.disopt.2019.05.001zbMath1506.90108OpenAlexW2947392384MaRDI QIDQ2010923

Nora Touati, Stefania Pan, Lucas Létocart, Mahuna Akplogan, Roberto Wolfler Calvo

Publication date: 28 November 2019

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

Lagrangian relaxationsubgradient methoddual ascent heuristicgeneralized set partitioning

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (1)

A branch-and-price algorithm for the minimum sum coloring problem

Cites Work

• Unnamed Item
• Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce
• A set-covering based heuristic algorithm for the periodic vehicle routing problem
• An exact approach for the vertex coloring problem
• Railway track allocation: Models and methods
• An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
• A dual ascent procedure for the set partitioning problem
• An exact solution framework for a broad class of vehicle routing problems
• The train driver recovery problem-a set partitioning based model and solution method
• An extension of set partitioning with application to scheduling problems
• Crew pairing at Air France
• A Lagrangian-based heuristic for large-scale set covering problems
• On some difficult linear programs coming from set partitioning
• A method for the cutting stock problem with different qualities
• Staff scheduling and rostering: a review of applications, methods and models.
• Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms
• ILP models and column generation for the minimum sum coloring problem
• Survey, categorization, and comparison of recent tour scheduling literature
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Column generation approaches to ship scheduling with flexible cargo sizes
• An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation
• Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems
• An Exact Algorithm for the Period Routing Problem
• An Exact Algorithm for the Pickup and Delivery Problem with Time Windows
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Set Partitioning: A survey
• A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering
• Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
• A set covering based matheuristic for a real‐world city logistics problem
• A Primer in Column Generation
• Combining Column Generation and Lagrangian Relaxation
• Implementing Mixed Integer Column Generation
• A set packing model for the ground holding problem in congested networks
• Benchmarking optimization software with performance profiles.

This page was built for publication: A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints