2024-2025

Immanuel Bomze - University of Vienna 

Friday, December 6th 2024 from 12pm to 1pm

Title: Community Detection in (Social) Networks Under Uncertainty

(joint work with M.Kahr, M.Leitner, F.Rinaldi and D.Zeffiro)

Abstract: During the last decades the importance of considering data uncertainty in optimization problems has become increasingly apparent, since small
fluctuations of input data may lead to comparably bad decisions in many practical problems when uncertainty is ignored. If the probability
distribution of the uncertain data is not known (or cannot be estimated with sufficient precision), a common technique is to estimate bounds on the uncertain data
and to identify optimal solutions that are robust against data fluctuations within these bounds. This approach leads to the robust optimization paradigm that allows to consider uncertain objectives and constraints [1].

Optimization problems where only the objective is uncertain arise, for instance, prominently in the analysis of social networks. This stems from the fact that the strength of social ties (i.e., the amount of influence individuals exert on each other) or the willingness of individuals to adopt and share information can, for example, only be roughly estimated based on observations. A fundamental problem arising in social network analysis regards the identification of communities (e.g., work groups, interest groups), which can be modeled as a Dominant Set Clustering Problem [5,6,7] which in turn leads to a Standard Quadratic Optimization Problems (StQP); see [2]. Here the link strengths enter the objective while the constraints are familiar probability constraints, so that they can be considered certain.

Hence we investigate data uncertainty in the objective function of StQPs, considering different uncertainty sets, and derive implications for the complexity of robust variants of the corresponding deterministic counterparts. We can show that considering data uncertainty in a StQP results in another StQP of the same complexity if ellipsoidal, spherical or boxed uncertainty sets are assumed [4]. Moreover we discuss implications when considering polyhedral uncertainty sets, and derive rigorous bounds for this case, based upon copositive optimization [3].

If we switch to discrete models where decision on ties are binary (edge present or not), i.e., concentrate on the classic adjacency description of undirected graphs,
a different robustness seems more appropriate which is closer to the budgeted uncertainty robustness. The key notion here is that of an s-defective clique, a subgraph which
would be complete if at most s edges are added. We investigate a continuous cubic optimization model [8] of the combinatorial problem to find large s-defective cliques, where advanced first-order methods seem to be most efficient, and report on significant speed-up compared to earlier attempts [9] with the same quality.

Keywords. Graph clustering, community detection, dominant set, s-defective cliques, robust optimization, polynomial optimization.

References

[1] Ben-Tal A, El Ghaoui L, Nemirovski AS (2009) Robust optimization. Princeton Series in Applied Mathematics
(Princeton NJ: Princeton University Press).

[2] Bomze IM (1998) On standard quadratic optimization problems. Journal of Global Optimization
13(4):369–387.

[3] Bomze IM (2012) Copositive optimization – Recent developments and applications. European Journal
of Operational Research 216(3):509–520.

[4] Bomze IM, Kahr M, Leitner M (2021) Trust your data or not - StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization.
Mathematics of Operations Research}  46:301-316.

[5] Pavan M, Pelillo M (2007) Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis
and Machine Intelligence 29(1):167–172.

[6] Rota Bulò S, Pelillo M (2017) Dominant-set clustering: A review. European Journal of Operational
Research 262(1):1–13.

[7] Rota Bulò S, Pelillo M, Bomze IM (2011) Graph-based quadratic optimization: A fast evolutionary
approach. Computer Vision and Image Understanding 115(7):984–995.

[8] Bomze IM, Rinaldi F, Zeffiro D (2022) Fast cluster detection in networks by first order
optimization. SIAM J. Math. Data Sci. 4: 285-305.

[9] Stozhkov V, Buchanan A, Butenko S, Boginski V (2022). Continuous cubic formulations
for cluster detection problems in networks. Math.Progr. 196: 279-307.

***

Onur Ozturk  -  University of Ottawa

Tuesday, November 12th 2024 from 12pm to 1pm

Title : Exact and heuristic solution methods in the context of parallel batch scheduling

Abstract  : Parallel batching (p-batch) operations consist of processing multiple jobs at the same time using the same resource. p-batch can be encountered in diverse industries and contexts such as semi-conductor manufacturing, steel production, truck loading with heterogenous items, etc. Multiple objective functions can be considered such as the minimization of the total flow time to decrease work-in-progress levels, or weighted earliness/tardiness in accordance with a just-in-time production philosophy. It is possible to present p-batch problems as (mixed) integer linear programming models. Yet, the inefficiency of these models for large size instances requires other solution approaches such as column generation, branch and bound or heuristics. Thus, we will present how a time indexed set-partitioning formulation of the problem can be efficiently solved by column generation. Given the final solution is not always integer, we will also present how exact and heuristic solutions can be obtained through semi-binary branching in a tree search.

About the speaker

Onur Ozturk is an associate professor in the field of business analytics/operations management at the Telfer School of Management of the University of Ottawa. He has received his PhD from Grenoble Institute of Technology. Dr. Ozturk’s particular areas of research interest includes large scale optimization applied to production management, transportation and staff/patient scheduling in healthcare settings. He has published in international journals such as POM, EJOR, OMEGA, IJPR, ANOR, etc.

***

Eduardo UCHOA -  Universidade Federal Fluminense, Brasil

Tuesday, November 19th 2024 from 12pm to 1pm

Title : Optimizing with Column Generation

Abstract : This talk provides an overview of the Column Generation (CG) technique, including its role in Integer Programming through Branch-and-Price and Branch-Cut-and-Price algorithms. The central question explored is: under what circumstances are CG-based algorithms likely to outperform other existing methods? The discussion draws on material from the recent book "Optimizing with Column Generation: advanced Branch-Cut-and-Price Algorithms (Part I)" available at https://optimizingwithcolumngeneration.github.io/.

***

Willem-Jan VAN HOEVE - Carnegie Mellon University 

Tuesday, October 1 2024 from 12pm to 1pm

Title: Decision Diagrams for Discrete Optimization

Abstract: Over the last decade, decision diagram-based optimization has emerged as a competitive novel paradigm for solving combinatorial optimization problems.  This presentation will provide an overview of this new methodology and its applications.  We start with describing a generic branch-and-bound framework based on decision diagrams: working from a state-based formulation (e.g., a dynamic program), relaxed decision diagrams provide dual bounds, restricted decision diagrams provide primal bounds, and an exact search is defined based on the nodes of the diagrams.  We demonstrate that this approach outperforms or is competitive with state of the art solvers on various problem domains including the maximum independent set problem and single-machine scheduling.  We will also discuss how an extension of this method called 'column elimination' can be integrated with a linear programming solver to obtain strong dual bounds for large-scale integer programming problems, including vehicle routing applications.