2024-2025
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.