Search Results

Documents authored by Lodi, Andrea

Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2023.17
Optimizing Fairness over Time with Homogeneous Workers (Short Paper)

Authors: Bart van Rossum, Rui Chen, and Andrea Lodi

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
There is growing interest in including fairness in optimization models. In particular, the concept of fairness over time, or, long-term fairness, is gaining attention. In this paper, we focus on fairness over time in online optimization problems involving the assignment of work to multiple homogeneous workers. This encompasses many real-life problems, including variants of the vehicle routing problem and the crew scheduling problem. The online assignment problem with fairness over time is formally defined. We propose a simple and interpretable assignment policy with some desirable properties. In addition, we perform a case study on the capacitated vehicle routing problem. Empirically, we show that the most cost-efficient solution usually results in unfair assignments while much more fair solutions can be attained with minor efficiency loss using our policy.
Cite as

Bart van Rossum, Rui Chen, and Andrea Lodi. Optimizing Fairness over Time with Homogeneous Workers (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanrossum_et_al:OASIcs.ATMOS.2023.17,
  author =	{van Rossum, Bart and Chen, Rui and Lodi, Andrea},
  title =	{{Optimizing Fairness over Time with Homogeneous Workers}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{17:1--17:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.17},
  URN =		{urn:nbn:de:0030-drops-187784},
  doi =		{10.4230/OASIcs.ATMOS.2023.17},
  annote =	{Keywords: Fairness, Online Optimization, Combinatorial Optimization, Vehicle Routing}
}
Document
DOI: 10.4230/DagRep.12.10.166
Data-Driven Combinatorial Optimisation (Dagstuhl Seminar 22431)

Authors: Emma Frejinger, Andrea Lodi, Michele Lombardi, and Neil Yorke-Smith

Published in: Dagstuhl Reports, Volume 12, Issue 10 (2023)

Abstract
Machine learning’s impressive achievements in the last decade have urged many scientific communities to ask if and how the techniques developed in that field to leverage data could be used to advance research in others. The combinatorial optimisation community is one of those, and the area of data-driven combinatorial optimisation has emerged. The motivation of the seminar and its design and development have followed the idea of making researchers both in academia and industry belonging to different communities - from operations research to constraint programming, from artificial intelligence to machine learning - communicate, establish a shared language, and ultimately (try to) set the roadmap for the development of the field.
Cite as

Emma Frejinger, Andrea Lodi, Michele Lombardi, and Neil Yorke-Smith. Data-Driven Combinatorial Optimisation (Dagstuhl Seminar 22431). In Dagstuhl Reports, Volume 12, Issue 10, pp. 166-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{frejinger_et_al:DagRep.12.10.166,
  author =	{Frejinger, Emma and Lodi, Andrea and Lombardi, Michele and Yorke-Smith, Neil},
  title =	{{Data-Driven Combinatorial Optimisation (Dagstuhl Seminar 22431)}},
  pages =	{166--174},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{10},
  editor =	{Frejinger, Emma and Lodi, Andrea and Lombardi, Michele and Yorke-Smith, Neil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.10.166},
  URN =		{urn:nbn:de:0030-drops-178257},
  doi =		{10.4230/DagRep.12.10.166},
  annote =	{Keywords: combinatorial optimisation, constraint programming, machine learning, Mixed integer programming, operations research, Reinforcement learning}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2021.3
Learning in Local Branching (Invited Talk)

Authors: Defeng Liu and Andrea Lodi

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Although state-of-the-art solvers for Mixed-Integer Programming (MIP) experienced a dramatic performance improvement over the past decades, the resolution of some MIPs is still challenging, requiring hours of computations while, in practice, high-quality solutions are often required to be computed within a very restricted time frame. In such cases, it might be preferable to provide anytime solutions, i.e., a first reasonable solution should be generated as early as possible, then better ones produced in the subsequent computation with the user deciding where to stop. In this respect, the local branching (LB) heuristic [Fischetti and Lodi, 2003] was proposed to improve an incumbent solution either at very early stages of the computation within a general MIP framework or as a stand-alone algorithmic framework. Roughly speaking, given a feasible solution, the method iterates by first defining a solution neighborhood through the so-called local branching cut, then by exploring it by calling a black-box MIP solver. In the local branching algorithm, the choice of the neighborhood size is crucial to performance. In principle, it is desirable to have neighborhoods to be relatively small for efficient computation but still large enough to contain improving solutions. In [Fischetti and Lodi, 2003], the size of the neighborhood is mostly initialized by a fixed constant value, then adjusted at run time. Nonetheless, it is reasonable to believe that there is no a priori single best neighborhood size and the choice of the value should depend on the characteristics of the problem. Furthermore, it is worth noting that, in many applications, instances of the same problem are solved repeatedly. Real-world problems have a rich structure: while more and more data points are collected, patterns and regularities appear. Therefore, problem-specific and task-specific knowledge can be learned from data and applied to adapting the corresponding optimization scenario. This motives a broader paradigm of sizing the solution neighborhoods in local branching. Following the line of work analyzed and surveyed in [Bengio et al., 2021] on the use of Machine Learning (ML) for combinatorial optimization, in this work, we aim to guide the (local) search of the local branching heuristic by ML techniques. In particular, given a problem instance and a time limit for (heuristically) solving it, we exploit ML tools to predict reasonable good values of the neighborhood size, in order to maximize the performance of the local branching algorithm. We computationally show that the neighborhood size can indeed be learnt leading to improved performances and that the overall algorithm generalizes well both with respect to the instance size and, more surprisingly, across instances.
Cite as

Defeng Liu and Andrea Lodi. Learning in Local Branching (Invited Talk). In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.CP.2021.3,
  author =	{Liu, Defeng and Lodi, Andrea},
  title =	{{Learning in Local Branching}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{3:1--3:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.3},
  URN =		{urn:nbn:de:0030-drops-152948},
  doi =		{10.4230/LIPIcs.CP.2021.3},
  annote =	{Keywords: Local search, learning, mixed-integer programming}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact