Name
Title | ||
|---|---|---|
A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints |
Abstract | ||
|---|---|---|
In this paper we propose a dual ascent heuristic for solving the linear relaxation of the generalized set partitioning problem with convexity constraints, which often models the master problem of a column generation approach. The generalized set partitioning problem contains at the same time set covering, set packing and set partitioning constraints. The proposed dual ascent heuristic is based on a reformulation and it uses Lagrangian relaxation and subgradient method. It is inspired by the dual ascent procedure already proposed in literature, but it is able to deal with right hand side greater than one, together with under and over coverage. To prove its validity, it has been applied to the minimum sum coloring problem, the multi-activity tour scheduling problem, and some newly generated instances. The reported computational results show the effectiveness of the proposed method. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.disopt.2019.05.001 | Discrete Optimization |
Keywords | Field | DocType |
90-02,90C10 | Column generation,Mathematical optimization,Heuristic,Convexity,Job shop scheduling,Subgradient method,Upper and lower bounds,Set packing,Lagrangian relaxation,Mathematics | Journal |
Volume | ISSN | Citations |
33 | 1572-5286 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefania Pan | 1 | 0 | 0.68 |
| Roberto Wolfler Calvo | 2 | 823 | 48.28 |
| Mahuna Akplogan | 3 | 0 | 0.34 |
| Lucas Létocart | 4 | 115 | 12.37 |
| Nora Touati Moungla | 5 | 10 | 2.93 |