A branch-cut-and-price algorithm for the ...
Document type :
Article dans une revue scientifique: Article original
Title :
A branch-cut-and-price algorithm for the piecewise linear transportation problem
Author(s) :
Christensen, Tue [Auteur]
Department of Economics and Business Economics [Aarhus]
Labbé, Martine [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Integrated Optimization with Complex Structure [INOCS]
Department of Economics and Business Economics [Aarhus]
Labbé, Martine [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Integrated Optimization with Complex Structure [INOCS]
Journal title :
European Journal of Operational Research
Pages :
645-655
Publisher :
Elsevier
Publication date :
2015-09-16
ISSN :
0377-2217
English keyword(s) :
Transportation problem
Piecewise linear
Branch-cut-and-price
Piecewise linear
Branch-cut-and-price
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
English abstract : [en]
In this paper we present an exact solution method for the transportation problem with piecewise linear costs. This problem is fundamental within supply chain management and is a straightforward extension of the <i>fixed-charge ...
Show more >In this paper we present an exact solution method for the transportation problem with piecewise linear costs. This problem is fundamental within supply chain management and is a straightforward extension of the <i>fixed-charge transportation problem</i>. We consider two Dantzig–Wolfe reformulations and investigate their relative strength with respect to the linear programming (LP) relaxation, both theoretical and practical, through tests on a number of instances. Based on one of the proposed formulations we derive an exact method by branching and adding generalized upper bound constraints from violated cover inequalities. The proposed solution method is tested on a set of randomly generated instances and compares favorably to solving the model using a standard formulation solved by a state-of-the-art commercial solver.Show less >
Show more >In this paper we present an exact solution method for the transportation problem with piecewise linear costs. This problem is fundamental within supply chain management and is a straightforward extension of the <i>fixed-charge transportation problem</i>. We consider two Dantzig–Wolfe reformulations and investigate their relative strength with respect to the linear programming (LP) relaxation, both theoretical and practical, through tests on a number of instances. Based on one of the proposed formulations we derive an exact method by branching and adding generalized upper bound constraints from violated cover inequalities. The proposed solution method is tested on a set of randomly generated instances and compares favorably to solving the model using a standard formulation solved by a state-of-the-art commercial solver.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Comment :
SCOPUS: ar.j
Collections :
Source :