The most successful approaches for the TSP use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder: What is the … Read more
Peak cost is a novel objective for flows over time that describes the amount of workforce necessary to run a system. We focus on minimising peak costs in the context of maximum temporally repeated flows and formulate the corresponding MPC-MTRF problem. First, we discuss the limitations that emerge when restricting the solution space to integral … Read more
Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications … Read more
Given a simple graph G = (V, E) with vertex set V and edge set E, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover … Read more
We introduce the class of SO-friendly neural networks, which include several models used in practice including networks with 2 layers of hidden weights where the number of inputs islarger than the number of outputs. SO-friendly networks have the property that performing a precise line search to set the step size on each iteration has the … Read more
We study the reliable (uncapacitated) facility location (RFL) problem in a data-driven environment where historical observations of random demands and disruptions are available. Owing to the combinatorial optimization nature of the RFL problem and the mixed-binary randomness of parameters therein, the state-of-the-art RFL models applied to the data-driven setting either suggest overly conservative solutions, or … Read more
Centrality metrics have become a popular concept in network science and optimization. Over the years, centrality has been used to assign importance and identify influential elements in various settings, including transportation, infrastructure, biological, and social networks, among others. That said, most of the literature has focused on nodal versions of centrality. Recently, group counterparts of … Read more
Arc routing problems are combinatorial optimization problems that have many real-world applications, such as mail delivery, snow plowing, and waste collection. Various variants of this problem are available, as well as algorithms intended to solve them heuristically or exactly. Presented here is a generic algorithmic framework that can be applied to a variety of arc … Read more
We study the continuous-time service network design problem (CTSNDP) under travel time uncertainty, aiming to design a transportation service network along a continuous-time planning horizon, with robust operational efficiency even in the presence of travel time deviations. Incorporating travel time uncertainty holds a great practical value. However, it poses a significant challenge in both problem … Read more
Given a set of jobs (or items), each of which being characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible schedule (i.e., a jobs-to-servers assignment) having minimum overall power-on time. Although being linked to the … Read more