Filtering algorithms for biobjective mixed binary linear optimization problems with a multiple-choice constraint. (English) Zbl 07284453

Summary: 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.
The online supplements are available at https://doi.org/10.1287/ijoc.2019.0891.


90Cxx Mathematical programming


Full Text: DOI


[1] Balas E (1979) Disjunctive programming. Ann. Discrete Math. 5:3-51.Crossref, Google Scholar · Zbl 0409.90061
[2] Belotti P, Soylu B, Wiecek MM (2013) A branch-and-bound algorithm for biobjective mixed-integer programs. Optimization Online. Accessed November 15, 2018, http://www.optimization-online.org/DB_FILE/2013/01/3719.pdf.Google Scholar
[3] Benson HP (1984) Optimization over the efficient set. J. Math. Anal. Appl. 98(2):562-580.Crossref, Google Scholar · Zbl 0534.90077
[4] Benson HP (1998) An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Global Optim. 13(1):1-24.Crossref, Google Scholar · Zbl 0908.90223
[5] Benson HP, Sayin S (1993) A face search heuristic algorithm for optimizing over the efficient set. Naval Res. Logist. 40(1):103-116.Crossref, Google Scholar · Zbl 0780.90080
[6] Benson HP, Sun E (2000) Outcome space partition of the weight set in multiobjective linear programming. J. Optim. Theory Appl. 105(1):17-36.Crossref, Google Scholar · Zbl 1028.90051
[7] Benson HP, Sun E (2002) A weight set decomposition algorithm for finding all efficient extreme points in the outcome set of a multiple objective linear program. Eur. J. Oper. Res. 139(1):26-41.Crossref, Google Scholar · Zbl 1008.90027
[8] Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective mixed integer programming: The triangle splitting method. INFORMS J. Comput. 27(4):597-618.Link, Google Scholar · Zbl 1338.90364
[9] Carrillo VM, Taboada H (2012) A post-Pareto approach for multi-objective decision making using a non-uniform weight generator method. Procedia Comput. Sci. 12:116-121.Crossref, Google Scholar
[10] Chang CT, Ku CY, Ho HP, Liao C (2010) A MCGP decision aid for homebuyers to make the best choice. Quality Quantity 45(4):969-983.Crossref, Google Scholar
[11] Das I (1999) A preference ordering among various Pareto optimal alternatives. Structural Multidisciplinary Optim. 18(1):30-35.Crossref, Google Scholar
[12] Das I, Dennis J (1997) A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems. Structural Optim. 14(1):63-69.Crossref, Google Scholar
[13] Deb K, Saxena D (2005) On finding pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. KanGAL Report Number 2005011, Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur Kanpur, India.Google Scholar
[14] Ehrgott M (2005) Multicriteria Optimization (Springer Science & Business Media, Berlin).Google Scholar
[15] Eusébio A, Figueira J, Ehrgott M (2014) On finding representative non-dominated points for bi-objective integer network flow problems. Comput. Oper. Res. 48:1-10.Crossref, Google Scholar · Zbl 1348.90154
[16] Fortuny-Amat J, McCarl B (1981) A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. 32(9):783-792.Crossref, Google Scholar · Zbl 0459.90067
[17] Fülöp J (1993) On the equivalence between a linear bilevel programming problem and linear optimization over the efficient set. Technical Report No. WP 93-1, Laboratory of Operations Research and Decision Systems, Hungarian Academy of Sciences, Budapest, Hungary.Google Scholar
[18] Hamel AH, Löhne A, Rudloff B (2013) Benson type algorithms for linear vector optimization and applications. J. Global Optim. 59(4):811-836.Crossref, Google Scholar · Zbl 1330.90099
[19] Horst R, Thoai NV (1999) Maximizing a concave function over the efficient or weakly-efficient set. Eur. J. Oper. Res. 117(2):239-252.Crossref, Google Scholar · Zbl 0998.90074
[20] Isermann H (1974) Proper efficiency and the linear vector maximum problem. Oper. Res. 22(1):189-191.Link, Google Scholar · Zbl 0274.90024
[21] Jorge JM (2009) An algorithm for optimizing a linear function over an integer efficient set. Eur. J. Oper. Res. 195(1):98-103.Crossref, Google Scholar · Zbl 1161.90443
[22] Jornada D, Leon VJ (2016a) Biobjective robust optimization over the efficient set for Pareto set reduction. Eur. J. Oper. Res. 252(2):573-586.Crossref, Google Scholar · Zbl 1346.90736
[23] Jornada D, Leon VJ (2016b) Robustness methodology to aid multiobjective decision making in the electricity generation capacity expansion problem to minimize cost and water withdrawal. Appl. Energy 162:1089-1108.Crossref, Google Scholar
[24] Krichen S, Masri H, Guitouni A (2012) Adjacency based method for generating maximal efficient faces in multiobjective linear programming. Appl. Math. Model. 36(12):6301-6311.Crossref, Google Scholar · Zbl 1349.90605
[25] Liao CN, Kao HP (2010) Supplier selection model using Taguchi loss function, analytical hierarchy process and multi-choice goal programming. Comput. Indust. Engrg. 58(4):571-577.Crossref, Google Scholar
[26] Masin M, Bukchin Y (2008) Diversity maximization approach for multiobjective optimization. Oper. Res. 56(2):411-424.Link, Google Scholar · Zbl 1167.90644
[27] Mavrotas G, Diakoulaki D (1998) A branch and bound algorithm for mixed zero-one multiple objective linear programming. Eur. J. Oper. Res. 107(3):530-541.Crossref, Google Scholar · Zbl 0943.90063
[28] Mavrotas G, Diakoulaki D (2005) Multi-criteria branch and bound: A vector maximization algorithm for mixed 0-1 multiple objective linear programming. Appl. Math. Comput. 171(1):53-71.Crossref, Google Scholar · Zbl 1084.65063
[29] Miettinen K (1999) Nonlinear Multiobjective Optimization, vol. 12 (Springer, New York).Google Scholar
[30] Morse JN (1980) Reducing the size of the nondominated set: Pruning by clustering. Comput. Oper. Res. 7(1):55-66.Crossref, Google Scholar
[31] Naccache P (1978) Connectedness of the set of nondominated outcomes in multicriteria optimization. J. Optim. Theory Appl. 25(3):459-467.Crossref, Google Scholar · Zbl 0363.90108
[32] Pourkarimi L, Yaghoobi M, Mashinchi M (2009) Determining maximal efficient faces in multiobjective linear programming problem. J. Math. Anal. Appl. 354(1):234-248.Crossref, Google Scholar · Zbl 1173.90536
[33] Przybylski A, Gandibleux X, Ehrgott M (2008) Two phase algorithms for the bi-objective assignment problem. Eur. J. Oper. Res. 185(2):509-533.Crossref, Google Scholar · Zbl 1137.90005
[34] Rong A, Figueira JR, Lahdelma R (2015) A two phase approach for the bi-objective non-convex combined heat and power production planning problem. Eur. J. Oper. Res. 245(1):296-308.Crossref, Google Scholar · Zbl 1346.90312
[35] Rosenman M, Gero J (1985) Reducing the Pareto optimal set in multicriteria optimization (with applications to Pareto optimal dynamic programming). Engrg. Optim. 8(3):189-206.Crossref, Google Scholar
[36] Ruiz JP, Grossmann IE (2017) Global optimization of non-convex generalized disjunctive programs: A review on reformulations and relaxation techniques. J. Global Optim. 67(1-2):43-58.Crossref, Google Scholar · Zbl 1359.90108
[37] Sayin S (1996) An algorithm based on facial decomposition for finding the efficient set in multiple objective linear programming. Oper. Res. Lett. 19(2):87-94.Crossref, Google Scholar · Zbl 0865.90112
[38] Sayin S (2000) Optimizing over the efficient set using a top-down search of faces. Oper. Res. 48(1):65-72.Link, Google Scholar · Zbl 1106.90376
[39] Sayin S (2003) A procedure to find discrete representations of the efficient set with specified coverage errors. Oper. Res. 51(3):427-436.Link, Google Scholar · Zbl 1163.90741
[40] Soylu B (2015) Heuristic approaches for biobjective mixed 0-1 integer linear programming problems. Eur. J. Oper. Res. 245(3):690-703.Crossref, Google Scholar · Zbl 1346.90619
[41] Soylu B, Yildiz GB (2016) An exact algorithm for biobjective mixed integer linear programming problems. Comput. Oper. Res. 72:204-213.Crossref, Google Scholar · Zbl 1349.90650
[42] Steiner S, Radzik T (2008) Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput. Oper. Res. 35(1):198-211.Crossref, Google Scholar · Zbl 1149.90403
[43] Steuer R (1986) Multiple Criteria Optimization: Theory, Computation, and Application (John Wiley & Sons, New York).Google Scholar
[44] Steuer RE (1994) Random problem generation and the computation of efficient extreme points in multiple objective linear programming. Comput. Optim. Appl. 3(4):333-347.Crossref, Google Scholar · Zbl 0819.90088
[45] Steuer RE, Harris FW (1980) Intra-set point generation and filtering in decision and criterion space. Comput. Oper. Res. 7(1):41-53.Crossref, Google Scholar
[46] Stidsen T, Andersen KA, Dammann B (2014) A branch and bound algorithm for a class of biobjective mixed integer programs. Management Sci. 60(4):1009-1032.Link, Google Scholar
[47] Taboada HA, Coit DW (2008) Multi-objective scheduling problems: Determination of pruned Pareto sets. IIE Trans. 40(5):552-564.Crossref, Google Scholar
[48] Thang T (2015) Outcome-based branch and bound algorithm for optimization over the efficient set and its application. Dang QA, Nguyen XH, Le HB, Nguyen VH, Bao VNQ, eds. Some Current Advanced Researches on Information and Computer Science in Vietnam, Advances in Intelligent Systems and Computing, vol. 341 (Springer International Publishing, Cham, Switzerland), 31-47.Crossref, Google Scholar
[49] Vafaeyan S, Thibault J (2009) Selection of Pareto-optimal solutions for process optimization using rough set method: A new approach. Comput. Chemical Engrg. 33(11):1814-1825.Crossref, Google Scholar
[50] Vaz D, Paquete L, Fonseca CM, Klamroth K, Stiglmayr M (2015) Representation of the non-dominated set in biobjective discrete optimization. Comput. Oper. Res. 63:172-186.Crossref, Google Scholar · Zbl 1349.90752
[51] Venkat V, Jacobson SH, Stori JA (2004) A post-optimality analysis algorithm for multi-objective optimization. Comput. Optim. Appl. 28(3):357-372.Crossref, Google Scholar · Zbl 1084.90040
[52] Vincent T, Seipp F, Ruzika S, Przybylski A, Gandibleux X (2013) Multiple objective branch and bound for mixed 0-1 linear programming: Corrections and improvements for the biobjective case. Comput. Oper. Res. 40(1):498-509.Crossref, Google Scholar · Zbl 1349.90006
[53] Visée M, Teghem J, Pirlot M, Ulungu E (1998) Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J. Global Optim. 12(2):139-155.Crossref, Google Scholar · Zbl 0908.90191
[54] Yamamoto Y (2002) Optimization over the efficient set: Overview. J. Global Optim. 22(1-4):285-317.Crossref, Google Scholar · Zbl 1045.90061
[55] Yu P, Zeleny M (1975) The set of all nondominated solutions in linear cases and a multicriteria simplex method. J. Math. Anal. Appl. 49(2):430-468.Crossref, Google Scholar · Zbl 0313.65047
[56] Zadeh L (1963) Optimality and non-scalar-valued performance criteria. IEEE Trans. Automatic Control 8(1):59-60.Crossref,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.