nach oben

4OR

Erschienen in:

25.06.2021 | Research Paper

Measures of balance in combinatorial optimization

verfasst von: Philippe Olivier, Andrea Lodi, Gilles Pesant

Erschienen in: 4OR | Ausgabe 3/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The concept of balance plays an important role in many combinatorial optimization problems. Yet there exist various ways of expressing balance, and it is not always obvious how best to achieve it. In this methodology-focused paper, we study three cases where its integration is deficient and analyze the causes of these inadequacies. We examine the characteristics and performance of the measures of balance used in these cases, and provide general guidelines regarding the choice of a measure.

Vorheriger Artikel Home health care routing and scheduling problems: a literature review

Nächster Artikel Optimality conditions and Mond–Weir duality for a class of differentiable semi-infinite multiobjective programming problems with vanishing constraints

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Balancing with \(L_{2}\)-deviation rather than \(L_{1}\)-deviation turns an IP model into a (Mixed-)Integer Nonlinear Programming one (MINLP). Although impressive advances in solving MINLPs have been made in the last 15 years (D’Ambrosio and Lodi 2013), MINLPs are still, in general, significantly more difficult to solve than ILPs.

In this paper, the models presented in “Appendices B, C, and D” were solved via CP.

In this paper, we call an outlier any value equal to one of the two extremal values of the dispersion interval.

A complete model for the BACP can be found in “Appendix B”.

Guidelines to generate equivalent instances to those used can be found in Monette et al. (2007).

Our dataset can be found at https://github.com/PhilippeOlivier/mobico.

A complete model for the NPAP can be found in “Appendix C”.

Our dataset can be found at https://github.com/PhilippeOlivier/mobico.

A complete model for the BBSS problem can be found in “Appendix D”.

In contrast with the BACP and the NPAP, in the following objectives the mean is implicitly taken into account, since it is always 0.

Our dataset can be found at https://github.com/PhilippeOlivier/mobico.

We are forced to keep the problem size small in order to solve all instances to optimality in a reasonable amount of time, for illustrative purposes.

When constrained, the capacity is set to 5, which is half the maximum demand of a station. When constrained, the route length is set to 100, which is roughly half the length of an optimal TSP tour of the stations.

The complexity stems from the fact that an under-mean value and an over-mean value may have distinct fractional parts, and that we do not know beforehand how many values will be under the mean, and how many will be over the mean.

Here, we are assuming that \(\mu - \ell \le u - \mu \). If instead \(\mu - \ell > u - \mu \), the logic would be reversed.

In the interest of simplicity, we have left aside the staffing part of the NPAP as it is not particularly meaningful for our purposes. The reader may refer to the cited paper for details.

Brams SJ, Jones MA, Klamler C (2006) Better ways to cut a cake. Not Am Math Soc 53(11):1314–1321

Castro C, Manzano S (2001) Variable and value ordering when solving balanced academic curriculum problems. In: Proceedings of 6th workshop of the ERCIM WG on constraints (Prague, June 2001)

Ceschia S, Di Gaspero L, Schaerf A (2014) The generalized balanced academic curriculum problem with heterogeneous classes. Ann Oper Res 218(1):147–163CrossRef

Chemla D, Meunier F, Wolfler Calvo R (2013) Bike sharing systems: solving the static rebalancing problem. Discrete Optim 10(2):120–146CrossRef

Chiarandini M, Di Gaspero L, Gualandi S, Schaerf A (2012) The balanced academic curriculum problem revisited. J Heuristics 18(1):119–148CrossRef

Contardo C, Morency C, Rousseau LM (2012) Balancing a dynamic public bike-sharing system. Technical report, CIRRELT

Corbett-Davies S, Pierson E, Feller A, Goel S, Huq A (2017) Algorithmic decision making and the cost of fairness. CoRR abs/1701.08230

D’Ambrosio C, Lodi A (2013) Mixed integer nonlinear programming tools: an updated practical overview. Ann Oper Res 204(1):301–320CrossRef

Di Gaspero L, Rendl A, Urli T (2013a) A hybrid ACO+CP for balancing bicycle sharing systems. In: Blesa MJ, Blum C, Festa P, Roli A, Sampels M (eds) Hybrid Metaheuristics. Springer, Berlin, pp 198–212

Di Gaspero L, Rendl A, Urli T (2013b) Constraint-based approaches for balancing bike sharing systems. In: Schulte C (ed) Principles and practice of constraint programming. Springer, Berlin, pp 758–773

Di Gaspero L, Rendl A, Urli T (2016) Balancing bike sharing systems with constraint programming. Constraints 21(2):318–348CrossRef

Dong X, Cai Y (2019) A novel genetic algorithm for large scale colored balanced traveling salesman problem. Future Gener Comput Syst 95:727–742CrossRef

Everitt BS, Skrondal A (2010) The Cambridge dictionary of statistics, vol 4. Cambridge University Press, CambridgeCrossRef

Gaudioso M, Legato P (1991) Linear programming models for load balancing. Comput Oper Res 18(1):59–64CrossRef

Hemmati H, Arcuri A, Briand L (2013) Achieving scalable model-based testing through test case diversity. ACM Trans Softw Eng Methodol 22(1):1–42CrossRef

Hnich B, Kiziltan Z, Walsh T (2002) Modelling a balanced academic curriculum problem. In Jussien N, Laburthe F (eds) Proceedings of the fourth international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimisation problems (CP-AI-OR’02), Le Croisic, France. pp 121–131

Hnich B, Kiziltan Z, Miguel I, Walsh T (2004) Hybrid modelling for robust solving. Ann Oper Res 130(1):19–39CrossRef

Larusic J, Punnen AP (2011) The balanced traveling salesman problem. Comput Oper Res 38(5):868–875CrossRef

Levina E, Bickel P (2001) The earth mover’s distance is the mallows distance: some insights from statistics. In: Proceedings eighth IEEE international conference on computer vision. ICCV 2001, vol 2. pp 251–256

Lodi A (2010) Mixed integer programming computation. In: Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (eds) 50 Years of integer programming 1958–2008. Springer, Berlin, pp 619–645CrossRef

Marsh MT, Schilling DA (1994) Equity measurement in facility location analysis: a review and framework. Eur J Oper Res 74(1):1–17CrossRef

Monette JN, Schaus P, Zampelli S, Deville Y, Dupont P (2007) A CP approach to the balanced academic curriculum problem. In: Symcon’07, the seventh international workshop on symmetry and constraint satisfaction problems

Mullinax C, Lawley M (2002) Assigning patients to nurses in neonatal intensive care. J Oper Res Soc 53(1):25–35CrossRef

Nash J (1953) Two-person cooperative games. Econometrica 21(1):128–140CrossRef

Ogryczak W (2000) Inequality measures and equitable approaches to location problems. Eur J Oper Res 122(2):374–391CrossRef

Olivier P, Lodi A, Pesant G. The quadratic multiknapsack problem with conflicts and balance constraints. INFORMS J Comput (to appear)

Pattanaik PK (2017) Social welfare function. Palgrave Macmillan UK, London, pp 1–7

Pesant G (2015) Achieving domain consistency and counting solutions for dispersion constraints. INFORMS J Comput 27(4):690–703CrossRef

Pesant G (2016) Balancing nursing workload by constraint programming. Springer International Publishing, Cham, pp 294–302

Pesant G, Régin JC (2005) SPREAD: a balancing constraint based on statistics. Springer, Berlin, pp 460–474

Rainer-Harbach M, Papazek P, Hu B, Raidl GR (2013) Balancing bicycle sharing systems: a variable neighborhood search approach. In: Middendorf M, Blum C (eds) Evolutionary computation in combinatorial optimization. Springer, Berlin, pp 121–132CrossRef

Rainer-Harbach M, Papazek P, Raidl GR, Hu B, Kloimüllner C (2015) PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems. J Global Optim 63(3):597–629CrossRef

Raviv T, Tzur M, Forma IA (2013) Static repositioning in a bike-sharing system: models and solution approaches. EURO J Transp Logist 2(3):187–229

Rossi F, van Beek P, Walsh T (eds) (2006) Handbook of constraint programming. Volume 2 of foundations of artificial intelligence. Elsevier

Schaus P, Van Hentenryck P, Régin JC (2009) Scalable load balancing in nurse to patient assignment problems. In: van Hoeve WJ, Hooker JN (eds) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. Springer, Berlin, pp 248–262CrossRef

Schaus P, Deville Y, Dupont P, Régin JC (2007) The deviation constraint. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems 260–274

Schuijbroek J, Hampshire R, van Hoeve WJ (2017) Inventory rebalancing and vehicle routing in bike sharing systems. Eur J Oper Res 257(3):992–1004CrossRef

Sen A (1974) Rawls versus Bentham: an axiomatic examination of the pure distribution problem. Theor Decis 4(3):301–309CrossRef

Walla J, Ruthmair M, Raidl GR (2009) Solving a video-server load re-balancing problem by mixed integer programming and hybrid variable neighborhood search. In: Blesa MJ, Blum C, Di Gaspero L, Roli A, Sampels M, Schaerf A (eds) Hybrid metaheuristics. Springer, Heidelberg, pp 84–99CrossRef

Weng MX, Ventura JA (1994) A quadratic integer programming method for minimizing the mean squared deviation of completion times. Oper Res Lett 15(4):205–211CrossRef

Whiteacre KW (2006) Testing the level of service inventory-revised (LSI-R) for racial/ethnic bias. Crim Justice Policy Rev 17(3):330–342CrossRef

Titel: Measures of balance in combinatorial optimization
verfasst von: Philippe Olivier
Andrea Lodi
Gilles Pesant
Publikationsdatum: 25.06.2021
Verlag: Springer Berlin Heidelberg
Erschienen in: 4OR / Ausgabe 3/2022
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI: https://doi.org/10.1007/s10288-021-00486-x

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2022

A note on ELECTRE TRI-nB with few limiting profiles

Optimality conditions and Mond–Weir duality for a class of differentiable semi-infinite multiobjective programming problems with vanishing constraints

Home health care routing and scheduling problems: a literature review

Partition-based distributionally robust optimization via optimal transport with order cone constraints

Multi-period distribution network problems with minimum commitment contracts

Simple ranking method using reference profiles: incremental elicitation of the preference parameters

Premium Partner

Marktübersichten