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
We extend the target map, together with the weighted barriers and the notions of weighted analytic centers, from linear programming to general convex conic programming. This extension is obtained from a novel geometrical perspective of the weighted barriers, that views a weighted barrier as a weighted sum of barriers for a strictly decreasing sequence of … Read more
We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, … 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
In this paper we consider the adjustable robust approach to multistage optimization, for which we derive dynamic programming equations. We also discuss this from a point of view of risk averse stochastic programming. As an example we consider a robust formulation of the classical inventory model and show that, similar to the risk neutral case, … Read more
We present a decomposition heuristic for a large class of job shop scheduling problems. This heuristic utilizes information from the linear programming formulation of the associated optimal timing problem to solve subproblems, can be used for any objective function whose associated optimal timing problem can be expressed as a linear program (LP), and is particularly … Read more
Structural optimization of non-conservative systems with respect to stability criteria is a research area with important applications in fluid-structure interactions, friction-induced instabilities, and civil engineering. In contrast to optimization of conservative systems where rigorously proven optimal solutions in buckling problems have been found, for non-conservative optimization problems only numerically optimized designs were reported. The proof … Read more
We introduce the notion of inexact first-order oracle and analyze the behaviour of several first-order methods of smooth convex optimization used with such an oracle. This notion of inexact oracle naturally appears in the context of smoothing techniques, Moreau-Yosida regularization, Augmented Lagrangians and many other situations. We derive complexity estimates for primal, dual and fast … Read more