Several Mixed Integer Linear Programming problems present a formulation based on a great number of knapsack constraints. Problems widely addressed in literature with this structure are, among others, Generalized Assignment, Multiple Knapsack, Bin Packing, Capacitated P-median and Single Source Capacitated Facility Location. In general knapsack constraints make these problems very hard to solve. The state of the art on these problems requires to use approaches besed on Lagrangean Relaxation or decomposition approaches like Dantzig-Wolfe and Column Generation tenchniques. In this paper, we present an approach based on the generation of general cutting planes of the polyhedron associated with each knapsack constraints. This approach yelds a lower bound for the LP-relaxation that is the same obtained by the Dantzig-Wolfe decomposition and henceforth stronger than the LP-relaxation. We use this aproach in the solution of the Single Source Capacitated Facility Location problem (SSCFLP) using a Branch-and-Cut algorithm. Computational experience is reported on a large set of test instances available in literature.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Branch-and-Cut algorithm for the Single Source Capacitated Facility Location problem


    Contributors:


    Publication date :

    2013-05-01


    Size :

    1080240 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English