We analyze a version of the Mizuno-Todd-Ye predictor-corrector interior point algorithm for the P_*(\kappa)-matrix linear complementarity problem (LCP). We assume the existence of a strictly positive feasible solution. Our version of the Mizuno-Todd-Ye predictor-corrector algorithm is a generalization of Potra’s (2002) conclusions on the LCP with P_*(\kappa)-matrices. To derive a formulation of the complexity for … Read more
In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formulation by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation … Read more
We consider the problem of installing a two-level telecommunication network. Terminal nodes communicate with each other through hubs. Hubs can be installed on terminal nodes and they are interconnected by a complete network. Each terminal is connected to a hub node by direct links. The aim is to minimize the cost of installing hubs and … Read more
We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift … Read more
It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. Such a conjecture exists for the … Read more
Using a moment interpretation of recent results on sum-of-squares decompositions of non-negative polynomial matrices, we propose a hierarchy of convex linear matrix inequality (LMI) relaxations to solve non-convex polynomial matrix inequality (PMI) optimization problems, including bilinear matrix inequality (BMI) problems. This hierarchy of LMI relaxations generates a monotone sequence of lower bounds that converges to … Read more
We present a primal-dual interior-point algorithm for second-order conic optimization problems based on a specific class of kernel functions. This class has been investigated earlier for the case of linear optimization problems. In this paper we derive the complexity bounds $O(\sqrt{N})(\log N)\log\frac{N}{\epsilon})$ for large- and $O(\sqrt{N})\log\frac{N}{\epsilon}$ for small- update methods, respectively. Here $N$ denotes the … Read more
We consider an optimization problem of minimization of a linear function subject to chance constraints. In the multidimensional case this problem is, generically, a problem of minimizing under a nonconvex and difficult to compute constraints and as such is computationally intractable. We investigate the potential of conceptually simple scenario approximation of the chance constraints. The … Read more
In this paper, we first develop “economical” representations for positive semidefinitness of well-structured sparse symmetric matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT … Read more
This paper presents a new data classification method based on mixed-integer programming. Traditional approaches that are based on partitioning the data sets into two groups perform poorly for multi-class data classification problems. The proposed approach is based on the use of hyper-boxes for defining boundaries of the classes that include all or some of the … Read more