Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron

• 成果类型: Article
• 署名作者: Agarwal, Yogesh; Aneja, Yash
• 署名单位: Indian Institute of Management (IIM System); Indian Institute of Management Lucknow; University of Windsor
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1041
• 发表日期: 2012
• 页码: 638-654
• 关键词: valid inequalities; branch; REFORMULATION; penalties; polytope

摘要

In this paper we consider the well-known fixed-charge transportation problem. To send any flow from source si to destination t(j), we incur a unit variable shipping cost of c(ij) and a fixed cost f(ij). Here we study the structure of the projection polyhedron of this problem, in the space of 0-1 variables associated with fixed charges, and we develop several classes of valid inequalities and derive conditions under which they are facet defining. In some cases, if the conditions are not satisfied, we show how they can be lifted to define facets. Several heuristics for generating and adding these facets are presented. Using these results, we develop a computationally effective algorithm for solving the problem. The computational results clearly indicate the usefulness of this approach.