On the Branch and Cut Method for Multidimentional Mixed Integer Knapsack Problem

  • Authors

    • Mostafa Khorramizadeh Shiraz University of Technology
    • Zahra Rakhshandehroo Shiraz University of Technology
    2014-09-24
    https://doi.org/10.14419/ijamr.v3i4.3378

  • Abstract

    In this paper, we examine the effect of the feasibility pump (FP) method on the branch and cut method for solving the multidimentional mixed integer knapsack problem. The feasibility pump is a heuristic method, trying to compute a feasible solution for mixed integer pro- gramming problems. Moreover, we consider two efficient strategies for using the feasibility pump in a branch and cut method and present some tables of numerical results, concerning the application and comparison of using these strategies in the branch and cut method for solving the multidimentional mixed integer knapsack problem. The numerical re- sults indicate that for the majority of the test problems, by using the FP or the imroved version of the FP we can improve the efficiency of the branch and cut method for solving the multidimentional mixed integer knapsack problem.

    Keywords: Feasibility pump method, Branch and cut method, multidimentional mixed integer knapsack problem.

  • References

    1. A. Atamturk, On the facets of the mixed–integer knapsack polyhedron, Mathematical Programming Serries B, 98: 145–175, 2003.
    2. Boland N. L., Eberhard A.C., Engineer F. and Tsoukalas A, Improving the feasibility pump. Discrete Optimization, 4(1):77-86, 2007.
    3. Bertacco L. Fischetti M. and Lodi A, A feasibility pump heuristic for general Mixed-Integer Problems. Discrete Optimization, 4(1):63-76, 2007.
    4. M. Elf, C. Gutwenger, M. Junger and G. Rinaldi, branch and cut Algorithm for combinatorial optimization and their implementation in ABACUS,Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions., Lecture Notes in Computer Science. 2241 Springer 2001, pp. 157-222.
    5. H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problems, Springer-Verlag, Berlin, 2004.
    6. R. Weismantel, On the 0/1 knapsack polytope. Mathematical Programming, 77:49–68, 1997.
    7. L. A. Wolsey, Integer Programming, John Wiley and Sons, New York, 1998.

  • Downloads

  • How to Cite

    Khorramizadeh, M., & Rakhshandehroo, Z. (2014). On the Branch and Cut Method for Multidimentional Mixed Integer Knapsack Problem. International Journal of Applied Mathematical Research, 3(4), 422-431. https://doi.org/10.14419/ijamr.v3i4.3378

    Received date: 2014-08-15

    Accepted date: 2014-09-14

    Published date: 2014-09-24