期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2000
卷号：2000
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：We present a branch-and-cut algorithm to solve the single commodity uncapacitated
fixed charge network flow problem, which includes the Steiner tree problem, uncapaci-
tated lot-sizing problems, and the fixed charge transportation problem as special cases.
The cuts used are simple dicut inequalities and their variants. A crucial problem when
separating these inequalities is to find the right cut set on which to generate the in-
equalities. The prototype branch-and-cut system, bc-nd includes a separation heuristic
for the dicut inequalities, and problem specific primal heuristics, branching and pruning
rules. Computational results show that bc-nd is competitive compared to a variety of
special purpose algorithms for problems with explicit flow costs.
We also examine how general purpose MIP systems perform on such problems when
provided with formulations that have been tightened a priori with dicut inequalities.
