2024-2025

***

Claudia O. Lopez Soto

Tuesday, January 14th, 2025 from 12:10pm to 1:10 pm

Title : Beam Search to Minimise Cutting Patterns with Maximum Utilisation 

Abstract :  In many cutting and packing problems the sole objective is to maximise the utilisation of the cutting board, while satisfying the demand of pieces to be cut. When one focuses on optimising the use of raw material, it is very likely that for each board we will have to enter different cutting coordinates. In operations that involve a large number of pieces, many boards will be required, so the cutting process can be highly affected when changing boards. When dealing with a heterogeneous mix of pieces, this problem cannot be avoided. However, when the set of pieces to be cut presents large repetitions of the same pieces, it would seem reasonable to pay attention to the number of changes in the machine settings, reducing the cutting process time. In this problem, we introduce a new objective in the classic two-dimensional bin packing problem, where on top of maximising the total utilisation, we are also interested in minimising the number of different patterns needed to complete the demand. For this work, a pattern is defined as the coordinates of a set of pieces that will be cut from a bin. Minimising the number of patterns, will result in less changes on the settings of the cutting machine among bins, with a reduction on total cutting times. This variant of the problem has not been widely studied and so far we have only found the work by Song & Bennell (2014) which uses a column generation model to solve this problem. To start tackling this problem, we expand the initial work in Bennell et al. (2018) and work with a similar setting based on the glass industry, with irregular pieces that can be freely rotated and reflected. We also start by considering the restriction of separating each piece by means of a guillotine cut, which reduces the solution space and somehow limits the placement of each piece. Bennell et al. (2018) present a beam search strategy where each node represents a complete bin, thus the branch with minimum depth is the one with fewer bins, or maximum utilization. The same idea applies in this problem, interpreting the branch depth as the number of changes in machine settings. We introduce some novelty approaches in terms of the sorting of pieces, considering not just the largest ones as the first ones to place, but also taking into consideration the number of repetitions of each piece. The fact that pieces are separated by guillotine cuts, translates into irregular shapes where to place pieces after a guillotine cut is performed, thus we also look at the similarity between the angles of the pieces and the angles of each section of the bin to decide which piece to place next. Preliminary tests will be shown to demonstrate the efficiency of these new criteria for sorting pieces. We also provide our results, which confirm that the strategy of dealing with both objectives simultaneously is more effective than using existing heuristics that are mainly designed for heterogeneous mix of pieces. 

For any information about OMOR events, please send an e-mail to matta@essec.edu.  

***

GEMMA BERENGUER FALGUERA - Universidad Carlos III de Madrid 

Wednesday, January 29th 2025 from 12pm to 1pm

Title : Diversity-wishing in the supply chain: a cross-cultural study

Abstract : In this talk, I will describe the state of supplier diversity efforts by corporations from an international perspective using two different datasets. First, we examine data for the companies in the 2020 and 2022 Fortune Global 500 and find that corporate definitions of diversity are dynamic and vary across regions. Furthermore, while supplier diversity efforts are not yet widespread, these initiatives are increasingly common, especially in the form of references to diversity in companies’ supplier codes of conduct (SCC). Companies in North America and in certain economic sectors, such as the financial and healthcare sectors, are more likely to have such efforts in place. Based on our data, companies that report on their internal diversity and have other forms of supplier sustainability initiatives are also more likely to have supplier diversity initiatives.

In the second study, we expand our company data to include almost ten thousand organizations. We employ fully automated processes for collecting and analyzing SCCs, utilizing Natural Language Processing (NLP) techniques. We also design an innovative method for tone classification to efficiently and accurately extract, classify, and assess the assertiveness of enforcement language related to the SCCs of these companies. This unique data shows that larger and more profitable organizations are likelier to have detailed and more assertive enforcement diversity language. However, the relationships between regional variations and industry sectors and more assertive language are less consistent in this data. 

For any information about OMOR events, please send an e-mail to matta@essec.edu.  

***

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.