GRASP with path-relinking for network migration scheduling

Network migration scheduling is the problem where inter-nodal traffic from an outdated telecommunications network is to be migrated to a new network. Nodes are migrated, one at each time period, from the old to the new network. All traffic originating or terminating at given node in the old network is moved to a specific node … Read more

What Multistage Stochastic Programming Can Do for Network Revenue Management

Airlines must dynamically choose how to allocate their flight capacity to incoming travel demand. Because some passengers take connecting flights, the decisions for all network flights must be made simultaneously. To simplify the decision making process, most practitioners assume demand is deterministic and equal to average demand. We propose a multistage stochastic programming approach that … Read more

Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps

In this paper we apply the semidefinite programming approach developed by the authors to obtain new upper bounds for codes in spherical caps. We compute new upper bounds for the one-sided kissing number in several dimensions where we in particular get a new tight bound in dimension 8. Furthermore we show how to use the … Read more

A Matrix-lifting Semidefinite Relaxation for the Quadratic Assignment Problem

The quadratic assignment problem (\QAP) is arguably one of the hardest of the NP-hard discrete optimization problems. Problems of dimension greater than 20 are considered to be large scale. Current successful solution techniques depend on branch and bound methods. However, it is difficult to get \emph{strong and inexpensive} bounds. In this paper we introduce a … Read more

Using Simplex Gradients of Nonsmooth Functions in Direct Search Methods

It has been shown recently that the efficiency of direct search methods that use opportunistic polling in positive spanning directions can be improved significantly by reordering the poll directions according to descent indicators built from simplex gradients. The purpose of this paper is twofold. First, we analyze the properties of simplex gradients of nonsmooth functions … Read more

Global Convergence of General Derivative-Free Trust-Region Algorithms to First and Second Order Critical Points

In this paper we prove global convergence for first and second-order stationarity points of a class of derivative-free trust-region methods for unconstrained optimization. These methods are based on the sequential minimization of linear or quadratic models built from evaluating the objective function at sample sets. The derivative-free models are required to satisfy Taylor-type bounds but, … Read more

An integer programming approach to the OSPF weight setting problem

Under the Open Shortest Path First (OSPF) protocol, traffic flow in an Internet Protocol (IP) network is routed on the shortest paths between each source and destination. The shortest path is calculated based on pre-assigned weights on the network links. The OSPF weight setting problem is to determine a set of weights such that, if … Read more

Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem

Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it … Read more

Consistency of robust portfolio estimators

It is a matter of common knowledge that traditional Markowitz optimization based on sample means and covariances performs poorly in practice. For this reason, diverse attempts were made to improve performance of portfolio optimization. In this paper, we investigate three popular portfolio selection models built upon classical mean-variance theory. The first model is an extension … Read more

On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs

We establish that any nonconvex quadratic program having a mix of binary and continuous variables over a bounded feasible set can be represented as a linear program over the dual of the cone of copositive matrices. This result can be viewed as an extension of earlier separate results, which have established the copositive representation of … Read more