IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i1p57-73.html
   My bibliography  Save this article

Filtering Algorithms for Biobjective Mixed Binary Linear Optimization Problems with a Multiple-Choice Constraint

Author

Listed:
  • Daniel Jornada

    (Global Data, Insights & Analytics, Ford Motor Company, Dearborn, Michigan 48124;)

  • V. Jorge Leon

    (Department of Engineering Technology and Industrial Distribution, Texas A&M University, College Station, Texas 77843-3367; Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843-3367)

Abstract

This paper deals with a class of biobjective mixed binary linear programs having a multiple-choice constraint, which are found in applications such as Pareto set–reduction problems, single-supplier selection, and investment decisions, among others. Two objective space–search algorithms are presented. The first algorithm, termed line search and linear programming filtering, is a two-phase procedure. Phase 1 searches for supported Pareto outcomes using the parametric weighted sum method, and Phase 2 searches for unsupported Pareto outcomes by solving a sequence of auxiliary mixed binary linear programs. An effective linear programming filtering procedure excludes any previous outcomes found to be dominated. The second algorithm, termed linear programming decomposition and filtering, decomposes the mixed binary problem by iteratively fixing binary variables and uses the linear programming filtering procedure to prune out any dominated outcomes. Computational experiments show the effectiveness of the linear programming filtering and suggest that both algorithms run faster than existing general-purpose objective space–search procedures.

Suggested Citation

  • Daniel Jornada & V. Jorge Leon, 2020. "Filtering Algorithms for Biobjective Mixed Binary Linear Optimization Problems with a Multiple-Choice Constraint," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 57-73, January.
    • Handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:57-73
    DOI: 10.1287/ijoc.2019.0891
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0891
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0891?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Serpil Sayin, 2003. "A Procedure to Find Discrete Representations of the Efficient Set with Specified Coverage Errors," Operations Research, INFORMS, vol. 51(3), pages 427-436, June.
    2. Rong, Aiying & Figueira, José Rui & Lahdelma, Risto, 2015. "A two phase approach for the bi-objective non-convex combined heat and power production planning problem," European Journal of Operational Research, Elsevier, vol. 245(1), pages 296-308.
    3. Soylu, Banu, 2015. "Heuristic approaches for biobjective mixed 0–1 integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 245(3), pages 690-703.
    4. Serpil Sayin, 2000. "Optimizing Over the Efficient Set Using a Top-Down Search of Faces," Operations Research, INFORMS, vol. 48(1), pages 65-72, February.
    5. Harold P. Benson & Serpil Sayin, 1993. "A face search heuristic algorithm for optimizing over the efficient set," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(1), pages 103-116, February.
    6. Jorge, Jesús M., 2009. "An algorithm for optimizing a linear function over an integer efficient set," European Journal of Operational Research, Elsevier, vol. 195(1), pages 98-103, May.
    7. Michael Masin & Yossi Bukchin, 2008. "Diversity Maximization Approach for Multiobjective Optimization," Operations Research, INFORMS, vol. 56(2), pages 411-424, April.
    8. Hela Masri & Saoussen Krichen & Adel Guitouni, 2012. "Generating efficient faces for multiobjective linear programming problems," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 15(1), pages 1-15.
    9. Benson, Harold P. & Sun, Erjiang, 2002. "A weight set decomposition algorithm for finding all efficient extreme points in the outcome set of a multiple objective linear program," European Journal of Operational Research, Elsevier, vol. 139(1), pages 26-41, May.
    10. Thomas Stidsen & Kim Allan Andersen & Bernd Dammann, 2014. "A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs," Management Science, INFORMS, vol. 60(4), pages 1009-1032, April.
    11. Mavrotas, G. & Diakoulaki, D., 1998. "A branch and bound algorithm for mixed zero-one multiple objective linear programming," European Journal of Operational Research, Elsevier, vol. 107(3), pages 530-541, June.
    12. Przybylski, Anthony & Gandibleux, Xavier & Ehrgott, Matthias, 2008. "Two phase algorithms for the bi-objective assignment problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 509-533, March.
    13. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 735-754, November.
    14. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 597-618, November.
    15. H. P. Benson & E. Sun, 2000. "Outcome Space Partition of the Weight Set in Multiobjective Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 105(1), pages 17-36, April.
    16. H. Isermann, 1974. "Technical Note—Proper Efficiency and the Linear Vector Maximum Problem," Operations Research, INFORMS, vol. 22(1), pages 189-191, February.
    17. Juan P. Ruiz & Ignacio E. Grossmann, 2017. "Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques," Journal of Global Optimization, Springer, vol. 67(1), pages 43-58, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. David Bergman & Merve Bodur & Carlos Cardonha & Andre A. Cire, 2022. "Network Models for Multiobjective Discrete Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 990-1005, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Soylu, Banu, 2018. "The search-and-remove algorithm for biobjective mixed-integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 268(1), pages 281-299.
    2. Cacchiani, Valentina & D’Ambrosio, Claudia, 2017. "A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs," European Journal of Operational Research, Elsevier, vol. 260(3), pages 920-933.
    3. Konur, Dinçer & Campbell, James F. & Monfared, Sepideh A., 2017. "Economic and environmental considerations in a stochastic inventory control model with order splitting under different delivery schedules among suppliers," Omega, Elsevier, vol. 71(C), pages 46-65.
    4. Yıldız, Gazi Bilal & Soylu, Banu, 2019. "A multiobjective post-sales guarantee and repair services network design problem," International Journal of Production Economics, Elsevier, vol. 216(C), pages 305-320.
    5. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    6. Anthony Przybylski & Xavier Gandibleux & Matthias Ehrgott, 2010. "A Recursive Algorithm for Finding All Nondominated Extreme Points in the Outcome Set of a Multiobjective Integer Programme," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 371-386, August.
    7. De Santis, Marianna & Grani, Giorgio & Palagi, Laura, 2020. "Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming," European Journal of Operational Research, Elsevier, vol. 283(1), pages 57-69.
    8. Seyyed Amir Babak Rasmi & Ali Fattahi & Metin Türkay, 2021. "SASS: slicing with adaptive steps search method for finding the non-dominated points of tri-objective mixed-integer linear programming problems," Annals of Operations Research, Springer, vol. 296(1), pages 841-876, January.
    9. Hongming Li & Xintao Li, 2022. "A Branch-and-Bound Algorithm for the Bi-Objective Quay Crane Scheduling Problem Based on Efficiency and Energy," Mathematics, MDPI, vol. 10(24), pages 1-20, December.
    10. Guillermo Cabrera-Guerrero & Matthias Ehrgott & Andrew J. Mason & Andrea Raith, 2022. "Bi-objective optimisation over a set of convex sub-problems," Annals of Operations Research, Springer, vol. 319(2), pages 1507-1532, December.
    11. Esmaeili, Somayeh & Bashiri, Mahdi & Amiri, Amirhossein, 2023. "An exact criterion space search algorithm for a bi-objective blood collection problem," European Journal of Operational Research, Elsevier, vol. 311(1), pages 210-232.
    12. Melih Ozlen & Benjamin A. Burton & Cameron A. G. MacRae, 2014. "Multi-Objective Integer Programming: An Improved Recursive Algorithm," Journal of Optimization Theory and Applications, Springer, vol. 160(2), pages 470-482, February.
    13. Julius Bauß & Michael Stiglmayr, 2024. "Augmenting bi-objective branch and bound by scalarization-based information," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 85-121, August.
    14. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2017. "The Quadrant Shrinking Method: A simple and efficient algorithm for solving tri-objective integer programs," European Journal of Operational Research, Elsevier, vol. 260(3), pages 873-885.
    15. Atashpaz Gargari, Masoud & Sahraeian, Rashed, 2023. "An exact criterion space search method for a bi-objective nursing home location and allocation problem," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 206(C), pages 166-180.
    16. Fattahi, Ali & Turkay, Metin, 2018. "A one direction search method to find the exact nondominated frontier of biobjective mixed-binary linear programming problems," European Journal of Operational Research, Elsevier, vol. 266(2), pages 415-425.
    17. Masar Al-Rabeeah & Santosh Kumar & Ali Al-Hasani & Elias Munapo & Andrew Eberhard, 2019. "Bi-objective integer programming analysis based on the characteristic equation," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 10(5), pages 937-944, October.
    18. Soylu, Banu & Katip, Hatice, 2019. "A multiobjective hub-airport location problem for an airline network design," European Journal of Operational Research, Elsevier, vol. 277(2), pages 412-425.
    19. David Bergman & Merve Bodur & Carlos Cardonha & Andre A. Cire, 2022. "Network Models for Multiobjective Discrete Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 990-1005, March.
    20. Stacey Faulkenberg & Margaret Wiecek, 2012. "Generating equidistant representations in biobjective programming," Computational Optimization and Applications, Springer, vol. 51(3), pages 1173-1210, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:57-73. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.