Polyhedral approaches to capacitated fixed-charge network flow problems.

摘要

Capacitated fixed-charge network flow problems arise in many practical settings, such as logistics, production planning, supply chain management and communication networks. In this thesis, we consider mixed-integer programming formulations of capacitated fixed-charge networks and their relaxations to simpler and more fundamental substructures. We study the associated polyhedra in order to derive valid inequalities for these problems and implement them in branch-and-cut algorithms.; In the first part of the thesis, we consider a capacitated fixed-charge network arising in production planning applications: the lot-sizing problem with inventory bounds and fixed charges. We propose strong cutting planes that are very effective in solving this problem when incorporated into a branch-and-cut algorithm. We also give a linear programming formulation of the problem when the order and inventory variable costs satisfy the Wagner-Whitin nonspeculative property. Extensive computational results show that the proposed method solves this problem in a short time while exploring very few branch-and-bound nodes under different problem settings and sizes. Our computations also illustrate that our method outperforms branch-and-cut algorithms that use previously known inequalities for related problems.; In the second part of the thesis, we first consider path-set relaxations of fixed-charge networks. Here, we explore path substructures in the network to derive strong valid inequalities and efficient separation algorithms that can be used in a branch-and-cut algorithm. These substructures are generalizations of capacitated lot-sizing polyhedra in that each node along the path has supply or demand and an arbitrary number of incoming and outgoing arcs. In addition, we consider three-partition relaxations and obtain new inequalities that are useful in closing the initial integrality gap.; Finally, we consider network flow problems in which the arc costs are piecewise linear concave, reflecting economies-of-scale or several technological alternatives. We consider cut-set relaxations of this problem and propose strong cutting planes. We give a linear programming formulation based on the proposed inequalities for an important special case of equal arc capacities with potentially different breakpoints on the arc costs. Our computational experiments demonstrate the effectiveness of the proposed inequalities within a branch-and-cut framework.