Optimization and Analysis of Large-Scale Networks

Project Leader Markus Leitner (University of Vienna)
Collaborators Matteo Fischetti (University of Padua)
Ivana Ljubic (ESSEC Business School)
Michele Monaci (University of Padua)
Mario Ruthmair (University of Vienna)
Funding Body Vienna Science and Technology Fund (WWTF)
WWTF
Project Number ICT15-014
Duration 2015-2019
Abstract
Networks are a ubiquitous tool to model the growing amount of data collected in science and business. In areas such as telecommunications, location theory, or social networks analysis (SNA), the size of the resulting networks and application data is ever increasing and analysis methods for large-scale data are crucial to deal with them in a meaningful way. Typically there are also inherent uncertainties associated with the input data and the implied optimization problems often face multiple objectives. These three aspects (large-scale data, uncertainty and multiple objectives) limit the applicability of available optimization algorithms that are capable to deal with at most one (if any) of these aspects. Following our recent “thinning out” modeling approach, we aim to develop novel mathematical models and algorithmic solutions for solving highly relevant problems from operations management, telecommunications, and SNA at the large scale. We plan to exploit parallelization techniques, sparse mathematical models and general purpose heuristics, to reconsider decomposition approaches, and apply them in the context of high performance computing. The obtained results will enable the consideration of uncertain input data and / or multiple objectives at the large scale. To this end, various robust optimization concepts and their applicability in multi-objective settings will be analyzed. Results will be used to derive high-performance solution methods aiming to solve realistic, large-scale problem instances. These approaches will be based on mixed-integer (non-linear) optimization, heuristics and parallelization methods.
 
Publications and Technical Reports (submitted for publication)
Please consult the websites of the individual authors for preprints!
  • M. Kahr, M. Leitner, M. Ruthmair, and M. Sinnl. Benders decomposition for competitive influence maximization in (social) networks. Technical Report, University of Vienna, 2020.
    [Bibtex]
    @techreport{Kahr2020,
    author = {Kahr, M. and Leitner, M. and Ruthmair, M. and Sinnl, M.},
    title = {Benders decomposition for competitive influence maximization in (social) networks},
    institution = {University of Vienna},
    year = {2020},
    }
  • M. Leitner, I. Ljubic, M. Riedler, and M. Ruthmair. Exact approaches for the directed network design problem with relays. Omega, 91, 2020.
    [Bibtex]
    @article{Leitner2020DNDPR,
    author = {Leitner, M. and Ljubic, I. and Riedler, M. and Ruthmair, M.},
    title = {Exact approaches for the directed network design problem with relays},
    journal = {Omega},
    volume = {91},
    year = {2020},
    }
  • M. Fischetti and M. Monaci. A branch-and-cut algorithm for Mixed-Integer Bilinear Programming. European Journal of Operational Research, 282(2):506–514, 2020.
    [Bibtex]
    @article{Fischetti2020,
    author = {Fischetti, M. and Monaci, M.},
    year = {2020},
    title = {A branch-and-cut algorithm for Mixed-Integer Bilinear Programming},
    journal = {European Journal of Operational Research},
    volume = {282},
    number = {2},
    pages = {506--514},
    }
  • M. Fischetti, M. Monaci, and M. Sinnl. Intersection cuts from bilinear disjunctions. European Journal of Operational Research, 2020. accepted, to appear
    [Bibtex]
    @article{Fischetti2019IntersectionCuts,
    author = {Fischetti, M. and Monaci, M. and Sinnl, M.},
    title = {Intersection cuts from bilinear disjunctions},
    journal = {European Journal of Operational Research},
    year = {2020},
    note = {accepted, to appear},
    }
  • F. Furini, I. Ljubic, S. Martin, and P. {San Segundo}. The maximum clique interdiction problem. European Journal of Operational Research, 277(1):112–127, 2019.
    [Bibtex]
    @article{Furini2019,
    author = {Furini, F. and Ljubic, I. and Martin, S. and {San Segundo}, P.},
    title = {The maximum clique interdiction problem},
    journal = {European Journal of Operational Research},
    volume = {277},
    number = {1},
    pages = {112--127},
    year = {2019},
    }
  • I. Bomze, M. Kahr, and M. Leitner. Trust your data or not – StQP remains StQP: community detection via robust standard quadratic optimization. Mathematics of Operations Research, 2019. accepted, to appear
    [Bibtex]
    @article{Bomze2019,
    author = {Bomze, I. and Kahr, M. and Leitner, M.},
    title = {Trust your data or not - StQP remains StQP: community detection via robust standard quadratic optimization},
    journal = {Mathematics of Operations Research},
    year = {2019},
    note = {accepted, to appear},
    }
  • M. Leitner, I. Ljubic, M. Riedler, and M. Ruthmair. Exact Approaches for Network Design Problems with Relays. INFORMS Journal on Computing, 31(1):171–192, 2019.
    [Bibtex]
    @article{Leitner2019NDPR,
    author = {Leitner, M. and Ljubic, I. and Riedler, M. and Ruthmair, M.},
    title = {Exact Approaches for Network Design Problems with Relays},
    journal = {{INFORMS} Journal on Computing},
    volume = {31},
    number = {1},
    pages = {171--192},
    year = {2019},
    }
  • J. -F. Cordeau, F. Furini, and I. Ljubic. Benders decomposition for very large scale partial set covering and maximal covering location problems. European Journal of Operational Research, 275(3):882–896, 2019.
    [Bibtex]
    @article{Cordeau2019,
    author = {Cordeau, J.-F. and Furini, F. and Ljubic, I.},
    title = {Benders decomposition for very large scale partial set covering and maximal covering location problems},
    journal = {European Journal of Operational Research},
    volume = {275},
    number = {3},
    pages = {882--896},
    year = {2019},
    }
  • G. Brandstätter, M. Leitner, and I. Ljubic. Location of charging stations in electric car sharing systems. Transportation Science, 2019. accepted, to appear
    [Bibtex]
    @article{Brandstaetter2019e4share,
    author = {Brandst\"atter, G. and Leitner, M. and Ljubic, I.},
    title = {Location of charging stations in electric car sharing systems},
    journal = {Transportation Science},
    year = {2019},
    note = {accepted, to appear},
    }
  • M. Fischetti, I. Ljubic, M. Monaci, and M. Sinnl. Interdiction Games and Monotonicity, with Application to Knapsack Problems. INFORMS Journal on Computing, 31(2):390–410, 2019.
    [Bibtex]
    @article{Fischetti2019IG,
    author = {Fischetti, M. and Ljubic, I. and Monaci, M. and Sinnl, M.},
    title = {Interdiction Games and Monotonicity, with Application to Knapsack Problems},
    journal = {{INFORMS} Journal on Computing},
    volume = {31},
    number = {2},
    pages = {390--410},
    year = {2019},
    }
  • E. Güney, M. Leitner, M. Ruthmair, and M. Sinnl. Large-scale Influence Maximization via Maximal Covering Location. Technical Report, 2019.
    [Bibtex]
    @techreport{Guney2019,
    author = {G\"uney, E. and Leitner, M. and Ruthmair, M. and Sinnl, M.},
    title = {Large-scale Influence Maximization via Maximal Covering Location},
    year = {2019},
    }
  • E. Fernández, M. Leitner, I. Ljubic, and M. Ruthmair. Arc Routing with Electric Vehicles. Technical Report, 2019.
    [Bibtex]
    @techreport{Fernandez2019,
    author = {Fern\'andez, E. and Leitner, M. and Ljubic, I. and Ruthmair, M.},
    title = {Arc Routing with Electric Vehicles},
    year = {2019},
    }
  • L. Gouveia, M. Leitner, and M. Ruthmair. Layered graph approaches for combinatorial optimization problems. Computers & Operations Research, 102:22–38, 2019.
    [Bibtex]
    @article{Gouveia2019LG,
    author = {Gouveia, L. and Leitner, M. and Ruthmair, M.},
    title = {Layered graph approaches for combinatorial optimization problems},
    journal = {Computers \& Operations Research},
    volume = {102},
    pages = {22--38},
    year = {2019},
    }
  • M. Fischetti, M. Kahr, M. Leitner, M. Monaci, and M. Ruthmair. Least cost influence propagation in (social) networks. Mathematical Programming, 170(1):293–325, 2018.
    [Bibtex]
    @article{Fischetti2018GLCI,
    author = {Fischetti, M. and Kahr, M. and Leitner, M. and Monaci, M. and Ruthmair, M.},
    title = {Least cost influence propagation in (social) networks},
    journal = {Mathematical Programming},
    volume = {170},
    number = {1},
    pages = {293--325},
    year = {2018},
    }
  • M. Riedler, G. R. Raidl, and M. Ruthmair. Strategies for Iteratively Refining Layered Graph Models. In Proceedings of the 11th International Workshop on Hybrid Metaheuristics, Lecture Notes in Computer Science. Springer, 2018.
    [Bibtex]
    @inproceedings{Riedler2018,
    author = {Riedler, M. and Raidl, G.R. and Ruthmair, M.},
    title = {Strategies for Iteratively Refining Layered Graph Models},
    booktitle = {Proceedings of the 11th International Workshop on Hybrid Metaheuristics},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer},
    year = {2018},
    }
  • M. Fischetti and J. Jo. Deep neural networks and mixed integer linear optimization. Constraints, 23(3):296–309, 2018.
    [Bibtex]
    @article{Fischetti2018DNN,
    author = {Fischetti, M. and Jo, J.},
    title = {Deep neural networks and mixed integer linear optimization},
    journal = {Constraints},
    volume = {23},
    number = {3},
    pages = {296--309},
    year = {2018},
    }
  • M. Fischetti, M. Monaci, and D. Salvagnin. SelfSplit parallelization for mixed-integer linear programming. Computers & Operations Research, 93:101–112, 2018.
    [Bibtex]
    @article{Fischetti2018SelfSplit,
    author = {Fischetti, M. and Monaci, M. and Salvagnin, D.},
    title = {SelfSplit parallelization for mixed-integer linear programming},
    journal = {Computers \& Operations Research},
    volume = {93},
    pages = {101--112},
    year = {2018},
    }
  • M. Fischetti, I. Ljubic, M. Monaci, and M. Sinnl. On the use of intersection cuts for bilevel optimization. Mathematical Programming, 172(1-2):77–103, 2018.
    [Bibtex]
    @article{Fischetti2018Intersection,
    author = {Fischetti, M. and Ljubic, I. and Monaci, M. and Sinnl, M.},
    title = {On the use of intersection cuts for bilevel optimization},
    journal = {Mathematical Programming},
    volume = {172},
    number = {1-2},
    pages = {77--103},
    year = {2018},
    }
  • L. Gouveia, M. Joyce-Moniz, and M. Leitner. Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints. Computers & Operations Research, 91:190–208, 2018.
    [Bibtex]
    @article{Gouveia2018NDPVRC,
    author = {Gouveia, L. and Joyce-Moniz, M. and Leitner, M.},
    title = {Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints},
    journal = {Computers \& Operations Research},
    volume = {91},
    pages ={190--208},
    year = {2018},
    }
  • L. Gouveia, P. Pesneau, M. Ruthmair, and D. Santos. Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem. Networks, 71(4):451–465, 2018.
    [Bibtex]
    @article{Gouveia2018PCATSP,
    author = {Gouveia, L. and Pesneau, P. and Ruthmair, M. and Santos, D.},
    title = {Combining and projecting flow models for the (precedence
    constrained) asymmetric traveling salesman problem},
    journal = {Networks},
    volume = {71},
    number = {4},
    pages = {451--465},
    year = {2018},
    }
  • M. Fischetti, M. Monaci, and M. Sinnl. A dynamic reformulation heuristic for Generalized Interdiction Problems. European Journal of Operational Research, 267(1):40–51, 2018.
    [Bibtex]
    @article{Fischetti2018Interdiction,
    author = {Fischetti, M. and Monaci, M. and Sinnl, M.},
    title = {A dynamic reformulation heuristic for Generalized Interdiction Problems},
    journal = {European Journal of Operational Research},
    volume = {267},
    number = {1},
    pages = {40--51},
    year = {2018},
    }
  • M. Leitner, I. Ljubic, M. Luipersbeck, and M. Sinnl. A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems. INFORMS Journal on Computing, 30(2):402–420, 2018.
    [Bibtex]
    @article{Leitner2018DAPCSTP,
    author = {Leitner, M. and Ljubic, I. and Luipersbeck, M. and Sinnl, M.},
    title = {A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting {S}teiner Tree and Related Problems},
    journal = {{INFORMS} Journal on Computing},
    volume = {30},
    number = {2},
    pages = {402--420},
    year = {2018},
    }
  • M. Leitner, I. Ljubic, J. -J. Salazar-González, and M. Sinnl. The connected facility location polytope. Discrete Applied Mathematics, 234:151–167, 2018.
    [Bibtex]
    @article{Leitner2018ConFLP,
    author = {Leitner, M. and Ljubic, I. and Salazar-Gonz\'alez, J.-J. and Sinnl, M.},
    title = {The connected facility location polytope},
    journal = {Discrete Applied Mathematics},
    volume = {234},
    pages = {151--167},
    year = {2018},
    }
  • M. Leitner, I. Ljubic, M. Luipersbeck, and M. Sinnl. Decomposition methods for the two-stage stochastic Steiner tree problem. Computational Optimization and Applications, 69(3):713–752, 2017.
    [Bibtex]
    @article{Leitner2017SSTP,
    author = {Leitner, M. and Ljubic, I. and Luipersbeck, M. and Sinnl, M.},
    title = {Decomposition methods for the two-stage stochastic {S}teiner tree problem},
    journal = {Computational Optimization and Applications},
    volume = {69},
    number = {3},
    pages = {713--752},
    year = {2017},
    }
  • M. Fischetti and M. Monaci. Using a general-purpose Mixed-Integer Linear Programming solver for the practical solution of real-time train rescheduling. European Journal of Operational Research, 263(1):258–264, 2017.
    [Bibtex]
    @article{Fischetti2017Train,
    author = {Fischetti, M. and Monaci, M.},
    title = {Using a general-purpose Mixed-Integer Linear Programming solver for the practical solution of
    real-time train rescheduling},
    journal = {European Journal of Operational Research},
    volume = {263},
    number = {1},
    pages = {258--264},
    year = {2017},
    }
  • P. Matl, P. C. Nolz, U. Ritzinger, M. Ruthmair, and F. Tricoire. Bi-objective orienteering for personal activity scheduling. Computers & Operations Research, 82:69-82, 2017.
    [Bibtex]
    @article{Matl2017,
    author = {Matl, P. and Nolz, P.C. and Ritzinger, U. and Ruthmair, M. and Tricoire, F.},
    title = {Bi-objective orienteering for personal activity scheduling},
    journal = {Computers \& Operations Research},
    volume = {82},
    pages = {69-82},
    year = {2017},
    }
  • H. Calik, M. Leitner, and M. Luipersbeck. A Benders decomposition based framework for solving cable trench problems. Computers & Operations Research, 81:128–140, 2017.
    [Bibtex]
    @article{Calik2017,
    author = {Calik, H. and Leitner, M. and Luipersbeck, M.},
    title = {A {B}enders decomposition based framework for solving cable trench problems},
    journal = {Computers \& Operations Research},
    volume = {81},
    pages = {128--140},
    year = {2017},
    }
  • L. Gouveia, M. Leitner, and M. Ruthmair. Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem. European Journal of Operational Research, 262(3):908–928, 2017.
    [Bibtex]
    @article{Gouveia2017BWTSP,
    author = {Gouveia, L. and Leitner, M. and Ruthmair, M.},
    title = {Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem},
    journal = {European Journal of Operational Research},
    volume = {262},
    number = {3},
    pages = {908--928},
    year = {2017},
    }
  • L. Gouveia and M. Leitner. Design of survivable networks with vulnerability constraints. European Journal of Operational Research, 258(1):89–103, 2017.
    [Bibtex]
    @article{Gouveia2017SNDP,
    author = {Gouveia, L. and Leitner, M.},
    title = {Design of survivable networks with vulnerability constraints},
    journal = {European Journal of Operational Research},
    volume = {258},
    number = {1},
    pages = {89--103},
    year = {2017},
    }
  • M. Fischetti, I. Ljubic, M. Monaci, and M. Sinnl. A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs. Operations Research, 65(6):1615–1637, 2017.
    [Bibtex]
    @article{Fischetti2017BL,
    author = {Fischetti, M. and Ljubic, I. and Monaci, M. and Sinnl, M.},
    title = {A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs},
    journal = {Operations Research},
    volume = {65},
    number = {6},
    pages = {1615--1637},
    year = {2017},
    }
  • M. Fischetti, I. Ljubic, and M. Sinnl. Redesigning Benders Decomposition for Large-Scale Facility Location. Management Science, 63(7):2146–2162, 2017.
    [Bibtex]
    @article{Fischetti2017FL,
    author = {Fischetti, M. and Ljubic, I. and Sinnl, M.},
    title = {Redesigning {B}enders Decomposition for Large-Scale Facility Location},
    journal = {Management Science},
    volume = {63},
    number = {7},
    pages = {2146--2162},
    year = {2017},
    }
  • M. Fischetti, I. Ljubic, and M. Sinnl. Benders decomposition without separability: A computational study for capacitated facility location problems. European Journal of Operational Research, 253(3):557–569, 2016.
    [Bibtex]
    @article{Fischetti2016FL,
    author = {Fischetti, M. and Ljubic, I. and Sinnl, M.},
    title = {Benders decomposition without separability: A computational study for capacitated facility location problems},
    journal = {European Journal of Operational Research},
    volume = {253},
    number = {3},
    pages = {557--569},
    year = {2016},
    }
  • M. Fischetti, I. Ljubic, M. Monaci, and M. Sinnl. Intersection cuts for bilevel optimization. In M. Skutella and others, editors, Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, volume 9682 of Lecture Notes in Computer Science, page 77–88. Springer, 2016.
    [Bibtex]
    @inproceedings{Fischetti2016BL,
    author = {Fischetti, M. and Ljubic, I. and Monaci, M. and Sinnl, M.},
    title = {Intersection cuts for bilevel optimization},
    booktitle = {Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016},
    series = {Lecture Notes in Computer Science},
    volume = {9682},
    pages = {77--88},
    year = {2016},
    publisher = {Springer},
    editor = {Skutella, M. and others},
    }