| Full text | |
| Author(s): |
de Lima, VInicius L.
;
Iori, Manuel
;
Miyazawa, Flavio K.
;
Singh, M
;
Williamson, DP
Total Authors: 5
|
| Document type: | Journal article |
| Source: | INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2021; v. 12707, p. 15-pg., 2021-01-01. |
| Abstract | |
We propose a number of solution techniques for general network flow formulations derived from Dantzig-Wolfe decompositions. We present an arc selection method to derive reduced network flow models that may potentially provide good feasible solutions. This method is explored as a variable selection rule for branching. With the aim of improving reduced-cost variable-fixing, we also propose a method to produce different dual solutions of network flow models and provide conditions that guarantee the correctness of the method. We embed the proposed techniques in an innovative branch-and-price method for network flow formulations, and test it on the cutting stock problem. In our computational experiments, 162 out of 237 open benchmark instances are solved to proven optimality within a reasonable computational time, consistently improving previous results in the literature. (AU) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 17/11831-1 - Algorithms and models for cutting and packing problems |
| Grantee: | Vinícius Loti de Lima |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |
| FAPESP's process: | 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings |
| Grantee: | Reinaldo Morabito Neto |
| Support Opportunities: | Research Projects - Thematic Grants |