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
We consider the stability of a class of parameterized nonlinear semidefinite programming problems whose objective function and constraint mapping all have second partial derivatives only with respect to the decision variable which are jointly continuous. We show that when the Karush-Kuhn-Tucker (KKT) condition, the constraint nondegeneracy condition, the strict complementary condition and the second order … 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
In this paper, we develop a general regularization-based continuous optimization framework for the maximum clique problem. In particular, we consider a broad class of regularization terms that can be included in the classic Motzkin-Strauss formulation and we develop conditions that guarantee the equivalence between the continuous regularized problem and the original one in both a … 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
Online bipartite matching (OBM) is a fundamental model underpinning many important applications, including search engine advertisement, website banner and pop-up ads, and ride-hailing. We study the i.i.d. OBM problem, where one side of the bipartition is fixed and known in advance, while nodes from the other side appear sequentially as i.i.d. realizations of an underlying … Read more
In the present paper, we prove that the augmented Lagrangian method converges to KKT points under the quasinormality constraint qualification, which is associated with the external penalty theory. For this purpose, a new sequential optimality condition for smooth constrained optimization, called PAKKT, is defined. The new condition takes into account the sign of the dual … Read more
We introduce a new generalization of the classical planar maximum coverage location problem (PMCLP) in which demand zones and service zone of each facility are represented by spatial objects such as circles, polygons, etc., and are allowed to be located anywhere in a continuous plane. In addition, we allow partial coverage in its true sense, … Read more