The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more
In this paper, we establish new bounds for restricted isometry constants (RIC) in low-rank matrix recovery. Let $\A$ be a linear transformation from $\R^{m \times n}$ into $\R^p$, and $r$ the rank of recovered matrix $X\in \R^{m \times n}$. Our main result is that if the condition on RIC satisfies $\delta_{2r+k}+2(\frac{r}{k})^{1/2}\delta_{\max\{r+\frac{3}{2}k,2k\}}
The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, … Read more
The Distance Geometry Problem in three dimensions consists in finding an embedding in R^3 of a given nonnegatively weighted simple undirected graph such that edge weights are equal to the corresponding Euclidean distances in the embedding. This is a continuous search problem that can be discretized under some assumptions on the minimum degree of the … Read more
Combinatorial and logic constraints arising in a number of challenging optimization applications can be formulated as vanishing constraints. Quadratic programs with vanishing constraints (QPVCs) then arise as subproblems during the numerical solution of such problems using algorithms of the Sequential Quadratic Programming type. QPVCs are nonconvex problems violating standard constraint qualifications. In this paper, we … Read more
In 1979, L. Lovasz defined the theta number, a spectral/semidefinite upper bound on the stability number of a graph, which has several remarkable properties (e.g. it is exact for perfect graphs). The definition of Lovasz’s theta number relies on the notion of orthonormal representation of the graph, and, dually, can be obtained by optimizing over … Read more
The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … Read more
This paper surveys several applications of biased random-key genetic algorithms (BRKGA) in optimization problems that arise in telecommunications. We first review the basic concepts of BRKGA. This is followed by a description of BRKGA-based heuristics for routing in IP networks, design of survivable IP networks, redundant server location for content distribution, regenerator location in optical … Read more
The set multicovering or set K-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least K times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set K-covering problem, … Read more
We provide a complete characterization of all polytopes P ⊆ [0,1]^n with empty integer hull whose Gomory-Chvátal rank is n (and, therefore, maximal). In particular, we show that the first Gomory- Chvátal closure of all these polytopes is identical. Article Download View Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank