REAL

A Primal-Dual Approach for Large Scale Integer Problems

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.

[img]
Preview
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: 02 Oct 2017 20:18
URI: http://real.mtak.hu/id/eprint/64980

Actions (login required)

Edit Item Edit Item