Faster exact solution of sparse MaxCut and QUBO problems

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems-by using mathematical … Read more

The impact of passive social media viewers in influence maximization

A frequently studied problem in the context of digital marketing for online social networks is the influence maximization problem that seeks for an initial seed set of influencers to trigger an information propagation cascade (in terms of active message forwarders) of expected maximum impact. Previously studied problems typically neglect that the probability that individuals passively … Read more

The SCIP Optimization Suite 8.0

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more

A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty

Since its introduction in the early 2000s, robust optimization with budget uncertainty has received a lot of attention. This is due to the intuitive construction of the uncertainty sets and the existence of a compact robust reformulation for (mixed-integer) linear programs. However, despite its compactness, the reformulation performs poorly when solving robust integer problems due … Read more

A Theoretical and Computational Analysis of Full Strong-Branching

Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On … Read more

The multiphase course timetabling problem

This paper introduces the multiphase course timetabling problem and presents mathematical formulations and effective solution algorithms to solve it in a real case study. Consider a pool of lessons and a number of students who are required to take a subset of these lessons to graduate. Each lesson consists of a predetermined and consecutive sequence … Read more

On fault-tolerant low-diameter clusters in graphs

Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the $s$-club, which is a vertex subset that induces a subgraph of diameter at most $s$. This model has found use in a variety … Read more

Solving a Class of Cut-Generating Linear Programs via Machine Learning

Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. When incorporated inside branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. However, running the CGLPs at the nodes of the branch-and-bound tree is computationally cumbersome … Read more

A primal heuristic to compute an upper bound set for multi-objective 0-1 linear optimisation problems

This paper presents an algorithm aiming to compute an upper bound set for a multi-objective linear optimisation problem with binary variables (p-01LP). Inspired by the well known « Feasibility Pump » algorithm in single objective optimisation, it belongs to the class of primal heuristics. The proposed algorithm, named « Gravity Machine », aims to deal … Read more

A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems

Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more