Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex k-cut problem consists in finding a vertex … Read more
The assortment of products carried by a store has a crucial impact on its success. However, finding the right mix of products to attract a large portion of the customers is a challenging task. Several mathematical models have been proposed to optimize assortments. In particular, rank-based choice models have been acknowledged for representing well high-dimensional … Read more
In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more
In the analysis of networks, one often searches for tightly knit clusters. One property of a “good” cluster is a small diameter (say, bounded by $k$), which leads to the concept of a $k$-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or … Read more
Feasibility pump is one of the successful heuristic solution approaches developed almost a decade ago for computing high-quality feasible solutions of single-objective integer linear programs, and it is implemented in exact commercial solvers such as CPLEX and Gurobi. In this study, we present the first Feasibility Pump Based Heuristic (FPBH) approach for approximately generating nondominated … Read more
The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies … Read more
We present a new branch-and-bound type search method for mixed integer linear optimization problems based on the concept of offshoots (introduced in this paper). While similar to a classic branch-and-bound method, it allows for changing the order of the variables in a dive (shaping) and removing unnecessary branching variables from a dive (trimming). The regular … Read more
The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a prohibitive number of valid inequalities and integer variables. In this … Read more
Given an existing Mobile Edge Cloud (MEC) network including virtualization facilities of limited capacity, and a set of mobile Access Points (AP) whose data traffic demand changes over time, we aim at finding plans for assigning APs traffic to MEC facilities so that the demand of each AP is satisfied and MEC facility capacities are … Read more
The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two stage stochastic linear programming. Structural properties and approximations of SIR … Read more