Skip to main content
SpringerLink
Log in

Algorithm robust for the bicriteria discrete optimization problem

Heuristic variations and computational evidence

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Averbakh, I. and V. Lebedev. (2004). “Interval Data Minmax Regret Network Optimization Problems.” Discrete Applied Mathematics, 138(3), 289–301.

    Article  Google Scholar 

  • Bitran, G. (1977). “Linear Multiple Objective Programs with Zero-One Variables.” Mathematical Programming, 13, 121–139.

    Article  Google Scholar 

  • Bowman, V. J. (1975). “On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multiple Criteria Objectives.” Lecture Notes in Economics and Mathematical Systems, 130, 76–85.

  • Captivo, M.E., J. Climaco, J. Figueira, E. Martins, and J.L. Santos. (2003). “Solving Bicriteria 0-1 Knapsack Problems Using a Labeling Algorithm.” Computers and Operations Research, 30(12), 1865–1886.

    Article  Google Scholar 

  • Chalmet, L., L. Lemonidis, and D. Elzinga. (1986). “An Algorithm for the Bi-Criterion Integer Programming Problem.” European Journal of Operational Research, 25, 292–300.

    Article  Google Scholar 

  • Climaco, J. and E. Martins. (1982). “A Bicriterion Shortest Path Algorithm.” European Journal of Operational Research, 11(4), 399–404.

    Article  Google Scholar 

  • CPLEX (2002). ILOG Cplex 8.0. ILOG Inc.

  • Ehrgott, M. (1997). Multiple Criteria Optimization: Classification and Methodology. Aaachen: Shaker Verlag.

  • Ehrgott, M. (2000). Multiple Criteria Optimization, Lecture Notes in Economics and Mathematical Systems. Berlin Heidelberg: Springer Verlag.

  • Ehrgott, M. and X. Gandibleux. (2000). “An Annotated Bibliography of Multi-Objective Combinatorial Optimization.” OR Spektrum, 22(4), 425–460.

    Google Scholar 

  • Ehrgott, M. and A. Skriver. (2003). “Solving Biobjective Combinatorial Max-Ordering Problems by Ranking Methods and a Two-Phases Approach.” European Journal of Operational Research, 147, 657–664.

    Article  Google Scholar 

  • Eswaran, P., A. Ravindran, and H. Moskowitz. (1989). “Algorithms for Nonlinear Integer Bicriterion Problems.” Journal of Optimization Theory and Applications, 63, 261–279.

    Article  Google Scholar 

  • Gupta, S.K. and J. Rosenhead. (1972). “Robustness in Sequential Investment Decisions.” Management Science, 15, 18–29.

    Google Scholar 

  • Henig, M.I. (1985). “The Shortest Path Problem with two Objective Functions.” European Journal of Operational Research, 25, 281–291.

    Article  Google Scholar 

  • Kaliszewski, I. (1987). “A Modified Weighted Tchebycheff Metric for Multiple Objective Programming.” Computers and Operations Research, 14, 315–323.

    Article  Google Scholar 

  • Kiziltan, G. and E. Yucaoglu. (1983). “An Algorithm for Multiobjective Zero-One Linear Programming.” Management Science, 29(12), 1444–1453.

    Google Scholar 

  • Klein, D. and E. Hannan. (1982). “An Algorithm for the Multiple Objective Integer Linear Programming Problem.” European Journal of Operational Research, 9, 378–385.

    Article  Google Scholar 

  • Klingman, D., A. Napier, and J. Stutz. (1974). “Netgen-a Program for Generating Large Scale (un) Capacitated Assignment, Transportation and Minimum Cost Network Flow Problems.” Management Science, 20, 814–822.

    Article  Google Scholar 

  • Kouvelis, P. and G. Yu. (1997). Robust Discrete Optimization and Its Applications. Kluwer.

  • Lee, H. and P.S. Pulat. (1993). “Bicriteria Network Flow Problems: Integer Case.” European Journal of Operational Research, 66, 148–157.

    Article  Google Scholar 

  • Neumayer, P. and D. Schweigert. (1994). “Three Algorithms for Bicriteria Integer Linear Programs.” OR Spektrum, 16, 267–276.

    Article  Google Scholar 

  • Rosenblatt, M.J. and H.L. Lee. (1987). “A Robustness Approach to Facilities Design.” International Journal of Production Research, 25, 479–486.

    Article  Google Scholar 

  • Sayin, S. (2000). “Measuring the Quality of Discrete Representations of Efficient Sets in Multiple Objective Mathematical Programming.” Mathematical Programming, 87, 543–560.

    Article  Google Scholar 

  • Sayin, S. and P. Kouvelis, (2005). “The Multiobjective Discrete Optimization Problem: A Weighted Min-Max Two Stage Optimization Approach and a Bicriteria Algorithm.” Management Science, 51, 1572–1581.

    Article  Google Scholar 

  • Sedeno-Noda, A. and C. Gonzalez-Martin. (2001). “An Algorithm for the Biobjective Integer Minimum Cost Flow Problem.” Computers and Operations Research, 28, 139–156.

    Article  Google Scholar 

  • Steuer, R. and E. Choo. (1983). “An Interactive Weighted Tchebycheff Procedure for Multiple Objective Programming.” Mathematical Programming, 26, 326–344.

    Article  Google Scholar 

  • Steuer, R.E. (1982). “On Sampling the Efficient Set Using Weighted Tchebycheff Metrics.” In Proceedings of the Task Force Meeting on Multiobjective and Stochastic Optimization, IIASA, Laxenburg, Austria, pp. 335–351.

  • Tuyttens, D., J. Teghem, P. Fortemps, and K.V. Nieuwenhuyze, (2000). “Performance of the Mosa Method for the Bicriteria Assignment Problem.” Journal of Heuristics, 6(3), 295–310.

    Article  Google Scholar 

  • Villareal, B. and B.H. Karwan. (1981). “Multicriteria Integer Programming: A (hybrid) Dynamic Programming Recursive Approach.” Mathematical Programming, 21, 204–223.

    Article  Google Scholar 

  • Visee, M., J. Teghem, M. Pirlot, and E.L. Ulungu. (1998). “Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem.” Journal of Global Optimization, 12, 139–155.

    Article  Google Scholar 

  • Yaman, H., O.E. Karasan, and M.C. Pinar. (2001). “The Robust Spanning Tree Problem with Interval Data.” Operations Research Letters, 29(1), 31–40.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Washington University, Olin School of Business, 1 Brookings Drive, St. Louis, MO, 63130, USA

    Panos Kouvelis

  2. Koç University, College of Administrative Sciences and Economics, İstanbul, Sarıyer, 34450, Turkey

    Serpil Sayın

Authors
  1. Panos Kouvelis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Serpil Sayın
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Serpil Sayın.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kouvelis, P., Sayın, S. Algorithm robust for the bicriteria discrete optimization problem. Ann Oper Res 147, 71–85 (2006). https://doi.org/10.1007/s10479-006-0062-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-006-0062-3

Keywords

Search

Navigation