Cluster Events
NEXT SEMINAR 2024/2025
In this section, you will find the information (Speaker/Guest, abstract, date & time slot , location, online registration link..) about the upcoming seminar during the year. The seminar registrations will be on Eventbrite and everyone is welcome, from within ESSEC as well as from outside.
Immanuel Bomze - University of Vienna (funded by Ivana's budget)
Friday, December 6th 2024 from 12pm to 1pm
Room : A.034 - New signage
Zoom meeting : https://essec.zoom.us/j/91453966093
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.
Here is the registration link .
For any information about OMOR events, please send an e-mail to matta@essec.edu.
***
Onur Ozturk - University of Ottawa
Tuesday, November 12th 2024 from 12pm to 1pm
Room : A.131 - New signage
Zoom meeting : https://essec.zoom.us/j/93578211447
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.
Here is the registration link .
For any information about OMOR events, please send an e-mail to matta@essec.edu.
***
Eduardo UCHOA - Universidade Federal Fluminense, Brasil
Tuesday, November 19th 2024 from 12pm to 1pm
Room : G.121 - New signage
Zoom meeting : https://essec.zoom.us/j/95812563172
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/.
Here is the registration link .
For any information about OMOR events, please send an e-mail to matta@essec.edu.