Skip to main content
SpringerLink
Log in

An improved algorithm for solving biobjective integer programs

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

Abstract

A parametric algorithm for identifying the Pareto set of a biobjective integer program is proposed. The algorithm is based on the weighted Chebyshev (Tchebycheff) scalarization, and its running time is asymptotically optimal. A number of extensions are described, including: a technique for handling weakly dominated outcomes, a Pareto set approximation scheme, and an interactive version that provides access to all Pareto outcomes. Extensive computational tests on instances of the biobjective knapsack problem and a capacitated network routing problem are presented.

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

  • Aksoy, Y. (1990). “An Interactive Branch-and-Bound Algorithm for Bicriterion Nonconvex/Mixed Integer Programming.” Naval Research Logistics, 37(3), 403–417.

    Google Scholar 

  • Alves, M.J. and J. Climaco. (1999). “Using Cutting Planes in An Interactive Reference Point Approach for Multiobjective Integer Linear Programming Problems.” European Journal of Operational Research, 117, 565–577.

    Article  Google Scholar 

  • Alves, M.J. and J. Climaco. (2000). “An Interactive Reference Point Approach for Multiobjective Mixed-Integer Programming Using Branch-and-Bound.” European Journal of Operational Research, 124, 478–494.

    Article  Google Scholar 

  • Bhaskar, K. (1979). “A Multiple Objective Approach to Capital Budgeting.” Accounting and Business Research, 9, 25–46.

    Google Scholar 

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

    Article  Google Scholar 

  • Bitran, G.R. (1979). “Theory and Algorithms for Linear Multiple Objective Programs with Zero-One Variables.” Mathematical Programming, 17, 362–390.

    Article  Google Scholar 

  • Bowman, V.J. (1976). “On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multiple-Criteria Objectives.” In H. Thieriez (ed.), Multiple Criteria Decision Making, Springer, Berlin, pp. 248–258.

    Google Scholar 

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

    Article  Google Scholar 

  • Climaco, J., C. Ferreira, and M.E. Captivo. (1997). “Multicriteria Integer Programming: An Overview of Different Algorithmic Approaches.” In J. Climaco (ed.), Multicriteria Analysis, Springer, Berlin, pp. 248–258.

    Google Scholar 

  • COIN-OR Foundation. (2006) Computational infrastructure for operations research. http://www.coin-or.org.

  • Ehrgott, M. and X. Gandibleux. (2000). “A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization.” OR Spektrum, 22, 425–460.

    Google Scholar 

  • Ehrgott, M. and X. Gandibleux. (2002). “Multiobjective Combinatorial Optimization—Theory, Methodology and Applications.” In M. Ehrgott and X. Gandibleux (eds.), Multiple Criteria Optimization—State of the Art Annotated Bibliographic Surveys, Kluwer Academic Publishers, Boston, MA, pp. 369–444.

    Google Scholar 

  • Ehrgott, M. and M.M. Wiecek. (2005). “Multiobjective Programming.” In M. Ehrgott, J. Figueira, and S. Greco (eds.), Multiple Criteria Decision Analysis: State of the Art Surveys, Springer, Berlin, Germany, pp. 667–722.

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  • Ferreira, C., J. Climaco, and J. Paixão. (1994). “The Location-Covering Problem: A Bicriterion Interactive Approach.” Investigación Operativa, 4(2), 119–139.

    Google Scholar 

  • Gandibleaux, X. (2006). “MCDM Numerical Instances Library.” http://www.univ-valenciennes.fr/ROAD/MCDM/ListMOKP.html.

  • Geoffrion, A.M. (1968). “Proper Efficiency and the Theory of Vector Maximization.” Journal of Mathematical Analysis and Applications, 22, 618–630.

    Article  Google Scholar 

  • Hultberg, T.H. (2003). “A Presentation of FlopC+ < eqid1 > +. http://projects.coin-or.org/FlopC++.

  • Kaliszewski, I. (2000). “Uisng Tradeoff Information in Decision-Making Algorithms.” Computers and Operations Research, 27, 161–182.

    Article  Google Scholar 

  • Kaliszewski, I. (2003). “Dynamic Parametric Bounds on Efficient Outcomes in Interactive Multiple Criteria Decision Making Problems.” European Journal of Operational Research, 147, 94–107.

    Article  Google Scholar 

  • Kaliszewski, I. and W. Michalowski. (1997). “Efficient Solutions and Nounds on Tradeoffs.” Journal of Optimization Theory and Applications, 94(2), 381–394.

    Article  Google Scholar 

  • Karaivanova, J., P. Korhonen, S. Narula, J. Wallenius, and V. Vassilev. (1995). “A Reference Direction Approach to Multiple Objective Integer Linear Programming.” European Journal of Operational Research, 81, 176–187.

    Article  Google Scholar 

  • Karaivanova, J., S. Narula, and V. Vassilev. (1993). “An Interactive Procedure for Multiple Objective Integer Linear Programming Problems.” European Journal of Operational Research, 68(3), 344–351.

    Article  Google Scholar 

  • Karaskal, K. and M. Köksalan. (2001). “Generating a Representative Subset of the Efficient Frontier in Multiple Criteria Decision Analysis.” Working Paper 01-20, Faculty of Administration, University of Ottawa.

  • Kere, P. and J. Koski. (2002). “Multicriterion Optimization of Composite Laminates for Maximum Failure Margins with an Interactive Descent Algorithm.” Structural and Multidisciplinary Optimization, 23(6), 436–447.

    Article  Google Scholar 

  • Klamroth, K., J. Tind, and M.M. Wiecek. (2002). “Unbiased Approximation in Multicriteria Optimization.” Mathematical Methods of Operations Research, 56, 413–437.

    Google Scholar 

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

    Article  Google Scholar 

  • Kostreva, M.M., Q. Zheng, and D. Zhuang. (1995). “A Method for Approximating Solutions of Multicriteria Nonlinear Optimization Problems.” Optimization Methods and Software, 5, 209–226.

    Article  Google Scholar 

  • Ladányi, L., et al. (2006). Coin-Or Utility Library. http://projects.coin-or.org/CoinUtils.

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

    Article  Google Scholar 

  • Lougeee-Heimer, R., et al. (2006). Cut Generation Library. http://projects.coin-or.org/Cgl.

  • Makhorin, A. (2004) “Introduction to GLPK.” http://www.gnu.org/software/glpk.

  • Mavrotas, G. and D. Diakoulaki. (1998). “A Branch and Bound Algorithm for Mixed Zero-One Multiple Objective Linear Programming.” European Journal of Operational Research, 107(3), 530–541.

    Article  Google Scholar 

  • Narula, S.C. and V. Vassilev. (1994). “An Interactive Algorithm for Solving Multiple Objective Integer Linear Programming Problems.” European Journal of Operational Research, 79(3), 443–450.

    Article  Google Scholar 

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

    Google Scholar 

  • Pasternak, H. and U. Passy. (1973). “Bicriterion Mathematical Programs with Boolean Variables.” In J.L. Cochrane and M. Zeleny (eds.), Multiple Criteria Decision Making, University of South Carolina Press, pp. 327–348.

  • Ralphs, T.K. Library of vehicle routing problem instances. www.BranchAndCut.org/VRP/data.

  • Ralphs, T.K. (2004). “SYMPHONY Version 5.0 User’s Manual.” Technical Report 04T-011, Lehigh University Industrial and Systems Engineering.

  • Ralphs, T.K. and J.C. Hartman. (2001). “Capacitated Network Routing (A Preliminary Progress Report).” Technical Report 01W-009, Lehigh University Industrial and Systems Engineering.

  • Ralphs, T.K. and M. Guzelsoy. (2005). “The SYMPHONY Callable Library for Mixed-Integer Linear Programming.” In Proceedings of the Ninth INFORMS Computing Society Conference, pp. 61–76.

  • Ramesh, R., M.H. Karwan, and S. Zionts. (1989). “Preference Structure Representation Using Convex Cones in Multicriteria Integer Programming.” Management Science, 35(9), 1092–1105.

    Article  Google Scholar 

  • Ramesh, R., M.H. Karwan, and S. Zionts. (1990). “An Interactive Method for Bicriteria Integer Programming.” IEEE Transcations on Systems, Man, and Cybernetics, 20(2), 395–403.

    Article  Google Scholar 

  • Ramesh, R., M.H. Karwan, and S. Zionts. (1991). “Interactive Bicriteria Integer Programming: A Performance Analysis.” In M. Fedrizzi, J. Kacprzyk, and M. Roubens (eds.), Interactive Fuzzy Optimization and Mathematical Programming, volume 368 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, pp. 92–100.

  • Ruzika, S. and M.M. Wiecek. (2005). “Survey Paper: Approximation Methods in Multiobjective Programming.” Journal of Optimization Theory and Applications, 126(3), 473–501.

    Google Scholar 

  • Saltzman, M., et al. (2006). Open Solver Interface. http://projects.coin-or.org/Osi.

  • Schandl, B., K. Klamroth, and M.M. Wiecek. (2001). “Norm-Based Approximation in Bicriteria Programming.” Computational Optimization and Applications, 20(1), 23–42.

    Article  Google Scholar 

  • Sedeño Noda, A. and C. González-Martín. (2001). “An Algorithm for the Biobjective Integer Minimum Cost Flow Porblem.” Computers and Operations Research, 28, 139–156.

    Article  Google Scholar 

  • Shin, W.S. and D.B. Allen. (1994). “An Interactive Paired-Comparison Method for Bicriterion Integer Programming.” Naval Research Logistics, 41(3), 423–434.

    Article  Google Scholar 

  • Solanki, R. (1991). “Generating the Noninferior Set in Mixed Integer Biobjective Linear Programs: An Application to a Location Problem.” Computers and Operations Research, 18, 1–15.

    Article  Google Scholar 

  • Steuer, R.E. (1986). Multiple Criteria Optimization: Theory, Computation and Application. John Wiley & Sons, New York.

    Google Scholar 

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

    Article  Google Scholar 

  • Vasko, F.J., R.S. Barbieri, B.Q. Rieksts, K.L. Reitmeyer, and K.L. Stott, Jr. (2002). “The Cable Trench Problem: Combining the Shortest Path and Minimum Spanning Tree Problems.” Comput. Oper. Res., 29(5), 441–458.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Villarreal, B. and M.H. Karwan. (1982) “Multicriteria Dynamic Programming with An Application to the Integer Case.” Journal of Mathematical Analysis and Applications, 38, 43–69.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA

    Ted K. Ralphs

  2. Department of Mathematical Sciences, Clemson University, Clemson, SC, USA

    Matthew J. Saltzman & Margaret M. Wiecek

Authors
  1. Ted K. Ralphs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthew J. Saltzman
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Margaret M. Wiecek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ted K. Ralphs.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ralphs, T.K., Saltzman, M.J. & Wiecek, M.M. An improved algorithm for solving biobjective integer programs. Ann Oper Res 147, 43–70 (2006). https://doi.org/10.1007/s10479-006-0058-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-006-0058-z

Keywords

Search

Navigation