EURO Advanced Tutorials on Operational Research Series Editors: M. Grazia Speranza · José Fernando Oliveira Carlos Henggeler Antunes Maria João Alves João Clímaco Multiobjective Linear and Integer Programming EURO Advanced Tutorials on Operational Research Series Editors M. Grazia Speranza, Brescia, Italy Jose´ Fernando Oliveira, Porto, Portugal More information about this series at http://www.springer.com/series/13840 ~ Carlos Henggeler Antunes (cid:129) Maria Joao Alves (cid:129) ~ Joao Cl´ımaco Multiobjective Linear and Integer Programming CarlosHenggelerAntunes MariaJo~aoAlves UniversityofCoimbra UniversityofCoimbra Coimbra,Portugal Coimbra,Portugal Jo~aoCl´ımaco INESCCoimbra Coimbra,Portugal ISSN2364-687X ISSN2364-6888 (electronic) EUROAdvancedTutorialsonOperationalResearch ISBN978-3-319-28744-7 ISBN978-3-319-28746-1 (eBook) DOI10.1007/978-3-319-28746-1 LibraryofCongressControlNumber:2016932386 ©SpringerInternationalPublishingSwitzerland2016 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilarmethodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthis book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained hereinorforanyerrorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAGSwitzerland Preface InclassicalOperationalResearch,thedecisionmaker’spreferencesaremodeleda priori; that is, all the values are aggregated in a single objective function (orcriterion),aimedatdeterminingtheoptimalsolutiontotheproblem.However, itiscurrentlyrecognizedthattheseapproachesaretooreductive,beinginadequate to address many real-world problems. In these problems, multiple perspectives should betaken into accountto evaluate the merits ofpotential solutions; i.e., the decision maker is generally interested not just in minimizing the cost but also in maximizing the system reliability, minimizing the environmental impacts, etc. Approaches that make an a priori aggregation of the multiple perspectives cannot duly capture the conflicting nature of the objective functions, which make opera- tionalevaluationaspectsofdistinctnatureandimpairtheexploitationoftrade-offs amongthem.Therefore,multiobjectiveoptimizationmodels,whichincludeexplic- itly the multiple evaluation aspects as distinct objective functions, enable to ade- quately capture the essential characteristics of real-world problems and improve their perceptionbydecisionmakers.The concept ofnondominated solutionis the keyconceptinmultiobjectiveoptimization:thatis,afeasiblesolutionforwhichno other feasible solution exists improving all objective function values simulta- neously. In this setting, the multiobjective optimization problem is defined as the choice, among the nondominated solution set, of a solution, or a reduced set of solutions for further screening, which reveals to be an acceptable compromise outcomeasaresultofthedecisionsupportprocesstakingintoaccountthedecision maker’s preferences. These preferences should not be understood as a preexisting andstableentityintheoperationalframeworkofsuchprocess,buttheyaresubject toevolveasnewinformationisgatheredaboutthecharacteristicsofnondominated solutions in different regions of the search space, which is determined by the mathematical model and the incorporation of additional elements derived from the preferences expressed. The decision support process using multiobjective optimization models is therefore based on interactive cycles of computation of nondominatedsolutions,evaluation,andpossiblechangeofpreferencesinfaceof newinformation. This informationresultsfromnewsolutionscomputedandtheir v vi Preface confrontation with information previously gathered, having in mind the “conver- gence”(notbasedonanytypeofaggregationfunctionspreviouslydeveloped)toa final solution that establishes an acceptable compromise between the competing objectivefunctions. This book aims at providing an entrance door into linear and integer multiobjective optimization, and it is primarily intended for undergraduate and graduatestudentsinengineering,management,economics,andappliedmathemat- ics. It starts (Chap. 1) by introducing the motivation and interest of explicitly considering multiple objective functions in optimization models. Problem formu- lation,definitions,andbasicconceptsarethenpresentedinChap.2,followedbythe exposition of techniques to compute nondominated solutions and the role of preference information in those scalarizing techniques (Chap. 3). Chapter 4 is devotedtointeractivemethods,inwhichsomemethodsrepresentativeofdifferent searchstrategiesarepresented.InChap.5,aguidedtouroftheiMOLPe—interac- tiveMOLPexplorersoftwareispresented,whichwasdevelopedbytheauthorsto deal with multiobjective linear programming problems. Chapter 6 deals with multiobjective integer and mixed-integer linear programming. It includes a litera- turereviewconcerningthemostrelevantapproaches,followedbythepresentation ofaninteractivereferencepointmethoddevelopedbytheauthors. Thisbookfocusesonmultiobjectivelinear,integer,andmixed-integerprogram- ming. These topics are adequate to get into multiobjective optimization, as they enabletoshedlightonboththeextensionofthetraditionalsingleobjectivelinear, integer, and mixed-integer programming models (broad topics usually studied in Operational Research courses) and the different paradigm that is at stake when multipleobjectivefunctionsareexplicitlyconsidered. Thisisatextbookrootedonourexperienceofmorethan25yearsofresearchand teaching of multiobjective optimization, and it results from our conviction of the increasingimportanceofthistopicinteachingOperationalResearchasascientific basistosupporttheprocessofmakingmoreinformedandbetterdecisions. Coimbra,Portugal CarlosHenggelerAntunes October2015 MariaJo~aoAlves Jo~aoCl´ımaco Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 FormulationsandDefinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 FundamentalConcepts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 ProposedExercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 SurrogateScalarFunctionsandScalarizingTechniques. . . . . . . . . 27 3.1 OptimizingOneoftheObjectiveFunctionsandTransformingthe Remainingp(cid:1)1intoConstraints. . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 OptimizingaWeighted-SumoftheObjectiveFunctions. . . . . . . . 31 3.2.1 IndifferenceRegionsontheWeightSpaceinMOLP. . . . . 33 3.3 MinimizingaDistance/AchievementFunctiontoaReference Point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.1 ABriefReviewofMetrics. . . . . . . . . . . . . . . . . . . . . . . . 41 3.4 ClassificationofMethodstoComputeNondominatedSolutions. . . 48 3.5 MethodsBasedontheOptimizationofanUtilityFunction. . . . . . 49 3.6 TheLexicographicMethod. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.7 GoalProgramming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.8 TheMultiobjectiveSimplexMethodforMOLP. . . . . . . . . . . . . . 50 3.9 ProposedExercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4 InteractiveMethodsinMultiobjectiveLinearProgramming. . . . . . 57 4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 STEMMethod. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2.1 GeneralDescription. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2.2 STEMAlgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2.3 FinalComments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.2.4 IllustrativeExampleoftheSTEMMethod. . . . . . . . . . . . 63 4.3 ZiontsandWalleniusMethod. . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 vii viii Contents 4.3.2 ZiontsandWalleniusAlgorithm. . . . . . . . . . . . . . . . . . . . 69 4.3.3 FinalComments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.3.4 IllustrativeExampleoftheZiontsandWallenius Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.4 TRIMAP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.4.1 MethodPresentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.4.2 TeachingMultiobjectiveLinearProgrammingUsing TRIMAP.. . . . . . . . .. . . . . . . .. . . . . . . . .. . . . . . . . .. 84 4.4.3 FinalComments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.4.4 IllustrativeExampleoftheTRIMAPmethod. . . . . . . . . . 87 4.5 IntervalCriterionWeightsMethod. . . . . . . . . . . . . . . . . . . . . . . 102 4.5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.2 ICW(IntervalCriterionWeights)Algorithm. . . . . . . . . . . 103 4.5.3 FinalComments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.5.4 IllustrativeExampleoftheIntervalCriterionWeights Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.6 ParetoRaceMethod. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.6.1 MethodDescription. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.6.2 FinalComments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.6.3 IllustrativeExampleoftheParetoRaceMethod. . . . . . . . 121 4.7 ProposedExercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5 AGuidedTourofiMOLPe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 5.2 iMOLPe:InteractiveMOLPExplorer. . . . . . . . . . . . . . . . . . . . . 138 5.2.1 Example1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.2.2 Example2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.2.3 Example3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.2.4 Example4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 5.2.5 FinalComments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 5.3 ProposedExercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6 MultiobjectiveIntegerandMixed-IntegerLinearProgramming. . . 161 6.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.2 GeneratingMethodsandScalarizingProcesses. . . . . . . . . . . . . . 162 6.3 InteractiveMethods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 6.3.1 Bi-objectiveInteractiveMethods. . . . . . . . . . . . . . . . . . . 174 6.3.2 MultiobjectiveInteractiveMethods. . . . . . . . . . . . . . . . . 175 6.4 AnInteractiveReferencePointMethodUsingBranch-And-Bound: PerformingDirectionalSearchesinMOMILP. . . . . . . . . . . . . . . 178 6.4.1 InteractiveAlgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 179 6.4.2 AnIllustrativeExample. . . . . . . . . . . . . . . . . . . . . . . . . . 188 6.4.3 GeneratingMethodforBi-ObjectiveProblems. . . . . . . . . 193 6.4.4 TheSoftware. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 6.5 ProposedExercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Chapter 1 Introduction Operational Research (OR) has developed as a scientific discipline during the decade of 1950, having created since then the (false) expectative that it would end up developing adequate methods and techniques for solving at least most decision problems faced at different levels, in industry and service sectors. In the beginning of the decade of 1970, the growing complexity of the economical and socialenvironmentandtheswiftcadenceoftechnologicalinnovation,particularly in the information and communication domains, made clear that the progress depended even more on the adoption of innovative planning and management procedures, narrowing the gap between the technological component and the methodological component of the production system. In these circumstances, the traditionalquantitativemethodsofORonlywerenotabletosuitthemselvestothe resolutionofmanyproblems. It was in this context that Geoffrion (1983) wrote an article entitled “Can Management Science/Operations Research evolve fast enough?”. May be there is not yet a definitive answer to this question. However, the accomplishments in severalfieldsofinterdisciplinarynatureallowustofacethefuturewithoptimism, with new increasingly stimulating intellectual challenges arising. OR, understood undertheperspectiveofthescienceandartofdecisionsupport,makesanappealfor the conjugated use of modern techniques of information systems, sophisticated human-computer interfaces, quantitative methods and algorithms, new modeling techniques, artificial intelligence techniques and certain disciplines usually includedintheso-calledhumanandsocialsciences,namelycognitivepsychology andsociologyoforganizations. In this context, the study of models with multiple, incommensurate and conflicting axes of evaluation of the merits of potential courses of action is a topic of utmost importance. In fact, real-world problems are intrinsically of multiobjectivenature,beingsingleobjectiveapproachesreductiveinmostcases. In this tutorial, we begin by making the bridge between single objective linear programming(LP)models,forwhichthecomputationoftheoptimumisa“mere” ©SpringerInternationalPublishingSwitzerland2016 1 C.HenggelerAntunesetal.,MultiobjectiveLinearandIntegerProgramming, EUROAdvancedTutorialsonOperationalResearch, DOI10.1007/978-3-319-28746-1_1