A Cutting Plane Method for the Fixed Cost Problem.
MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER
Pagination or Media Count:
The fixed cost linear programming problem FCLP refers to a linear programming problem in which each variable incurs a fixed cost or charge, in addition to its linear cost, whenever the variable takes a strictly positive value. The study is devoted to the development of a cutting plane method and its role in the perspective of a general framework essentially a branch-and-bound for FCLP algorithms. Analysis of the structure and properties of the problem reveals that algorithms which seek local minimum points minimum with respect to neighborhood are almost certain to be non-effective because of the proliferation of these local minima. The cutting plane method developed here the FCLP cut comes as the generalization, for the non-convex case, of outer linearization methods used for convex problems. The FCLP cut is developed from a linear under approximation of the FCLP objective function. Convergence properties of the method are studied in depth and sufficient conditions for convergence to a global optimal solution are identified. The most interesting fact is the constructive similarity demonstrated between the Benders and FCLP cuts they differ only by the space in which they are derived.
- Operations Research