Go to JKU Homepage
Institute of Production and Logistics Management
What's that?

Institutes, schools, other departments, and programs create their own web content and menus.

To help you better navigate the site, see here where you are at the moment.

Search
Go to JKU Homepage

FWF-Project-MOMIP

MOMIP: Multi-objective (mixed) integer programming

3-year research project funded by the Austrian Science Fund (FWF) within the Matching Funds Program.

We live in a world full of trade-offs and quite often we only know comparably little about them. In almost every problem situation we encounter it is difficult to define the one and only goal to aim for, especially whenever more than one decision maker or stakeholder is involved. Thus, many if not all practical problems involve several and often conflicting objectives. Prominent examples are environmental concerns versus cost or customer satisfaction versus profitability. 

Our research is mainly rooted in the fields of transportation, logistics, and supply chain management and many relevant problems arising in these fields can be modeled as mixed integer linear programs. This means that there exist only rather simple, linear relationships between input parameters and decision variables and some variables may assume only integer values, e.g., the decision whether a distribution center should be built or not can only be 1 (yes) or 0 (no) but not 0.2. 

Despite the fact that these problems are often comparably easy to formulate they are quite often very difficult to solve. In addition, whenever multiple conflicting objectives are of concern, it is usually not possible to identify one best solution with respect to all of the considered goals. Rather, a set of optimal compromise solutions exists which are “better” than the other possible solutions and incomparable among each other. Each such solution represents a possible trade-off.

The computation of this set of optimal trade-off solutions is a complex task. All currently available exact methods have limitations. Either they are only applicable to problems with at most two objectives or they cannot describe the complete set of trade-off solutions. The kernel of this project is the development of efficient generic algorithms, using the branch-and-bound idea in a way that allows to exploit the multi-objective nature of the considered problems, and thus to close this gap for mixed integer linear programs with up to three objectives.

In order to illustrate the applicability of our algorithms, we will use them to solve practical problems arising in sustainable supply chain management, disaster relief distribution planning and green vehicle routing. Decision makers will thus receive additional information on the trade-off relationship between the considered goals. They will be given the possibility to compare different solutions and to finally choose the most suitable solution out of the set ofall optimal compromise solutions.

Research Project

MOMIP: Multi-objective (mixed) integer programming

Funding Agency

Austrian Science Fund (FWF)

Duration

October 1, 2018 - September 30, 2021, extended to September 30, 2022

Project leader

Sophie N. Parragh

Contact

sophie.parragh@jku.at

Project collaborators

Duleabom An, Miriam Enzi, Markus Sinnl, Oryan Rampon.

News

Presentations

  • Rampon, O., Parragh S.N., Tricoire, F. "Branch-and-bound for bi-objective mixed integer programming", OR 2022, Karlsruhe, Germany, Sep 6-9, 2022.
  • Nazemi, N, Parragh, S.N., Gutjahr, W.J., "Bi-objective risk-averse facility location using a subset-based representation of the conditional value-at-risk". 11th International Conference on Operations Research and Enterprise Systems - ICORES, Feb 2022, online.
  • Parragh, S.N. "Branch-and-Bound for Multiobjective Integer Linear Programming", Webinar, SystemX, Paris, France, Jan 12, 2022.
  • Parragh, S.N. "Towards multi-objective mixed integer linear programming", RAMOO, Keynote Talk, Wuppertal, Germany, Sep 2021, online.
  • Parragh, S.N. "Branch-and-Bound for Multi-Objective Integer Programming", Webinar, Universidade Federal da Paraíba, Brasil, Nov 12, 2021.
  • Parragh, S.N. "Branch-and-bound for multi-objective (mixed) integer linear programming: key ingredients, challenges, and motivating applications", OR 2021, Semi-Plenary Talk, Bern/online, Sep 2, 2021,
  • An, D., Sinnl, M., Tricoire F., Parragh, S.N.  "A LP relaxation based matheuristic for multi-objective optimization", 10th International Conference on Operations Research and Enterprise Systems, ICORES, Feb 2021, online.
  • Parragh, S.N. “Branch-and-cut based bi-objective optimization: from stochastic facility location to multimodal car sharing”, SCM Research Seminar, WU Wien, Jan 11, 2021, online.
  • Parragh, S.N., "Integrated logistics planning: a bi-objective optimization perspective", Invited Talk, ISM, Hagenberg, Austria, Nov 25, 2020, online.
  • Nazemi, N, Parragh, S.N., Gutjahr, W.J., "Bi-objective facility location in the presence of uncertainty", RAMOO - Recent Advances in Multi-Objective Optimization, Linz, Austria, Sep 17, 2020, online.
  • Sinnl, M., Parragh, S.N., Tricoire, F. "On an outer approximation algorithm for multiobjective integer programming", RAMOO - Recent Advances in Multi-Objective Optimization, Linz, Austria, Sep 17, 2020, online.
  • Parragh, S.N. “Branch-and-Benders-cut for bi-objective stochastic facility location”, Invited Talk, Optimization Workshop, Dec 12, 2019, Mainz, Germany.
  • Parragh, S.N. “On integrating data uncertainty and multi-objective optimization: application to problems in disaster relief logistics'', Invited Talk, ATHEA Workshop, Vienna, Austria, Oct 25, 2019, 
  • Parragh, S.N., Tricoire, F., Gutjahr, W.J. "Branch-and-Benders-cut for bi-objective integer programming: application to a stochastic facility location problem". RAMOO - Recent Advances in Multi-Objective Optimization, Aarhus, Denmark, Sep 26, 2019.
  • Parragh, S.N., Enzi, M., Puchinger, J. "Solving the bi-objective multimodal car-sharing problem including time-dependent user preferences". OR 2019, Dresden, Germany, Sep 3-6, 2019.
  • An, D., Sinnl, M., Tricoire F., Parragh, S.N.  "A comparison of lower bound set algorithms for multi-objective branch-and-bound", OR 2019, Dresden, Germany, Sep 3-6, 2019.

Publications

Gutjahr, M., Parragh, S.N., Tricoire, F. (2023). Adaptive Large Neighborhood Search for a personnel task scheduling problem with task selection and parallel task assignments. (submitted)  https://arxiv.org/abs/2302.04494, opens an external URL in a new window 

Forget, N., Parragh, S.N. (2022). Enhancing Branch-and-Bound for Multi-Objective 0-1 Programming. (submitted) https://arxiv.org/abs/2210.05385, opens an external URL in a new window 

Bökler, F., Parragh, S.N., Sinnl, M., Tricoire, F. (2022). An outer approximation algorithm for
multi-objective mixed-integer linear and non-linear programming (submitted) https://arxiv.org/abs/2103.16647, opens an external URL in a new window

An, B., Parragh, S.N., Sinnl, M., Tricoire, F. (2022). A matheuristic for tri-objective binary integer programming  (submitted) http://arxiv.org/abs/2205.03386, opens an external URL in a new window

Nazemi, N., Parragh, S.N., Gutjahr, W. (2022). Bi-objective risk-averse facility location using a subset-based representation of the conditional value-at-risk. In Proceedings of the 11th International Conference on Operations Research and Enterprise Systems - ICORES, ISBN 978-989-758-548-7, pages 77-85. 10.5220/0010914900003117, opens an external URL in a new window [Best Student Paper Award]

Nazemi, N., Parragh, S. N., Gutjahr, W. J. (2022). Bi-objective facility location under uncertainty with an application in last-mile disaster relief. Annals of Operations Research, 319, 1689-1716. https://doi.org/10.1007/s10479-021-04422-4, opens an external URL in a new window

Parragh, S.N., Tricoire, F., Gutjahr, W.J. (2022). A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem. OR Spectrum, 44, 419-459. https://doi.org/10.1007/s00291-020-00616-7, opens an external URL in a new window Preprint: https://arxiv.org/abs/2004.11248, opens an external URL in a new window

Enzi, M., Parragh, S.N., Puchinger, J. (2022). The bi-objective multimodal car-sharing problem. OR Spectrum, 44, 307–348. https://doi.org/10.1007/s00291-021-00631-2, opens an external URL in a new window Preprint: http://arxiv.org/abs/2010.10344, opens an external URL in a new window

Enzi, M., Parragh, S.N., Pisinger, D., Prandtstetter, M. (2021). Modeling and solving the multimodal car- and ride-sharing problem. European Journal of Operational Research, 293(1), 290-303. https://doi.org/10.1016/j.ejor.2020.11.046, opens an external URL in a new window, Preprint: https://arxiv.org/abs/2001.05490, opens an external URL in a new window

An D., Parragh S., Sinnl M. and Tricoire F. (2021). A LP Relaxation based Matheuristic for Multi-objective Integer Programming. In Proceedings of the 10th International Conference on Operations Research and Enterprise Systems: ICORES, ISBN 978-989-758-485-5, pages 88-98. DOI: 10.5220/0010347000880098, opens an external URL in a new window, Preprint: https://arxiv.org/abs/2102.03582, opens an external URL in a new window

Gutjahr, M., Kellerer, H., Parragh, S.N. (2021). Heuristic approaches for scheduling jobs and vehicles in a cyclic flexible manufacturing system. Procedia Computer Science 180, 825-832. https://doi.org/10.1016/j.procs.2021.01.332, opens an external URL in a new window

Alvarez-Miranda, E., Goycoolea, M., Ljubic, I., Sinnl, M. (2021) The Generalized Reserve Set Covering Problem with Connectivity and Buffer Requirements. European Journal of Operational Research, 289(3), 1013-1029. https://doi.org/10.1016/j.ejor.2019.07.017, opens an external URL in a new window
Preprint: https://arxiv.org/abs/1909.04473, opens an external URL in a new window

Enzi, M., Parragh, S. N., & Pisinger, D. (2020). Modeling and solving a vehicle-sharing problem. arXiv preprint arXiv:2003.08207. https://arxiv.org/abs/2003.08207, opens an external URL in a new window (submitted for publication)

 

Go to JKU Homepage

Johannes Kepler University Linz

Altenberger Straße 69

4040 Linz, Austria

Telephone +43 732 2468 0
Fax +43 732 2468 4929
Contact