[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Worst-case analysis of maximal dual feasible functions

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Dual feasible functions have been used to compute fast lower bounds and valid inequalities for integer linear problems. In this paper, we analyze the worst-case performance of the lower bounds provided by some of the best functions proposed in the literature. We describe some worst-case examples for these functions, and we report on new results concerning the best parameter choice for one of these functions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Burdett C.A., Johnson E.L.: A subadditive approach to solve linear integer programs. Ann. Discrete Math. 1, 117–144 (1977)

    Article  Google Scholar 

  2. Carlier J., Clautiaux F., Moukrim A.: New reduction procedures and lower bounds for the two-dimensional bin-packing problem with fixed orientation. Comput. Oper. Res. 34, 2223–2250 (2007)

    Article  MATH  Google Scholar 

  3. Clautiaux F., Alves C., Valério de Carvalho J.: A survey of dual-feasible and superadditive functions. Ann. Oper. Res. 179, 317–342 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dash S., Günlük O.: Valid inequalities based on simple mixed-integer sets. Math. Program. 105, 29–53 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  5. Fekete S., Schepers J.: New classes of fast lower bounds for bin packing problems. Math. Program. 91, 11–31 (2001)

    MathSciNet  MATH  Google Scholar 

  6. Gilmore P., Gomory R.: A linear programming approach to the cutting stock problem (part I). Oper. Res. 9, 849–859 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  7. Johnson, D.S.: Near optimal bin packing algorithms. Dissertation, Massachussetts Institute of Technology, Cambridge, Massachussetts (1973)

  8. Letchford A.N., Lodi A.: Strengthening Chvával-Gomory cuts and Gomory fractional cuts. Oper. Res. Lett. 30, 74–82 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. Martello S., Toth P.: Knapsack Problems—Algorithms and Computer Implementation. Wiley, Chichester (1990)

    Google Scholar 

  10. Mitchell J.: Integer programming: cutting plane algorithms. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization, pp. 1650–1657. Springer, Berlin (2009)

    Chapter  Google Scholar 

  11. Pardalos, P., Resende, M. (eds): Handbook of Applied Optimization. Oxford University Press, New York (2002)

    MATH  Google Scholar 

  12. Prékopa A., Fábián C.: Cutting-stock problem. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization, pp. 594–595. Springer, Berlin (2009)

    Chapter  Google Scholar 

  13. Rietz J., Alves C., Valério de Carvalho J.: Theoretical investigations on maximal dual feasible functions. Oper. Res. Lett. 38, 174–178 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Vanderbeck F.: Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem. Oper. Res. 46(6), 915–926 (2000)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. Produção e Sistemas, Centro de Investigação Algoritmi da Universidade do Minho, Escola de Engenharia, Universidade do Minho, 4710-057, Braga, Portugal

    Jürgen Rietz, Cláudio Alves & J. M. Valério de Carvalho

Authors
  1. Jürgen Rietz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cláudio Alves
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. M. Valério de Carvalho
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cláudio Alves.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rietz, J., Alves, C. & de Carvalho, J.M.V. Worst-case analysis of maximal dual feasible functions. Optim Lett 6, 1687–1705 (2012). https://doi.org/10.1007/s11590-011-0359-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-011-0359-2

Keywords

Search

Navigation