Operations Research 2025
Abstract Submission

2370. Friends, Not Enemies: Exploring Synergy Types Between Complementary MIP Models for Large-Scale Instances with an Application to RCPSP

Invited abstract in session FA-2: Scheduling & Packing, stream Discrete and Combinatorial Optimization.

Friday, 8:45-10:15
Room: H4

Authors (first author is the speaker)

1. Mohamed Ibrahim
Business Information and Operations Research, Martin-Luther-University Halle-Wittenberg
2. Taieb Mellouli
Business Information Systems and Operations Research, Martin-Luther-University Halle-Wittenberg

Abstract

Mixed integer programming (MIP) is a powerful framework for solving complex optimization problems. One such problem is the Resource Constraint Project Scheduling Problem (RCPSP) which schedules activities in a project while respecting the precedence relations and resources limitations. Multiple MIP formulations have been proposed for RCPSP, including the Continuous Flow (CF) formulation, which models resource usage as a continuous flow between activities, and the Discrete Time (DT) formulation, which uses time-indexed variables to represent activity start times and resource usage directly. One model excels at representing the resource consumption while the other excels at representing the time relations. However, each model alone performs poorly in comparison to heuristic and other excat methods like constraint programming.
In this work, we explore how we can find synergy between different MIP models to achieve a performance not achieved by individual models. We show how solution properties obtained by the CF model can be used to infer more fine grained properties, and how those properties can be passed to the DT model to prune and model and improve it significantly. We then show how experimental results on standard data instances demonstrate the gains in solving time. We conclude by analysis of this approach and discuss how it may be generalized to other classes of combinatorial optimization problems.

Keywords

Status: accepted

Back to the list of papers