Jüttner, Alpár and Madarasi, Péter (2017) A Primal-Dual Approach for Large Scale Integer Problems. In: 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017. május 22-25, Budapest.
|
Text
juttner-madarasi--primal-dual-approach.pdf Download (183kB) | Preview |
Abstract
This paper presents a refined approach to using column generation to solve specific type of large integer problems. A primal-dual approach is presented to solve the Restricted Master problem belonging to the original optimization task. Firstly, this approach allows a faster convergence to the optimum of the LP relaxation of the problem. Secondly, the existence of both an upper and lower bound of the LP optimum at each iteration allows a faster searching of the Branch-and-Bound tree. To achieve this an early termination approach is presented. The technique is demonstrated on the Generalized Assignment problem and Parallel Machine Scheduling problem as two reference applications.
| Item Type: | Conference or Workshop Item (Lecture) |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA76 Computer software / programozás |
| Depositing User: | Alpár Jüttner |
| Date Deposited: | 02 Oct 2017 20:18 |
| Last Modified: | 05 Apr 2023 06:46 |
| URI: | http://real.mtak.hu/id/eprint/64980 |
Actions (login required)
 |
Edit Item |
