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
In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. … Read more
The solver DICOPT is based on an outer-approximation algorithm used for solving mixed- integer nonlinear programming (MINLP) problems. This algorithm is very effective for solving some types of convex MINLPs. However, there are certain problems that are dicult to solve with this algorithm. One of these problems is when the nonlinear constraints are so restrictive … Read more