The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program (P) \sup { | Ax \leq_K b} in the absence of any constraint qualification. The facial reduction algorithm solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana’s dual … Read more
Abstract This paper presents a novel formulation for the Traveling Salesman Problem (TSP), utilizing a binary list data-structure allocating cities to its leaves to form sequentially the tour of the problem. The structure allows the elimination of subtours from the formulation and at the same time reducing the number of binary variables to ${\cal O}(N\log_{2}N)$. … Read more
In this paper, we consider relocating facilities, where we have demand changes in the network. Relocations are performed by closing some of the existing facilities from low demand areas and opening new ones in newly emerging areas. However, the actual changes of demand are not known in advance. Therefore, di erent scenarios with known probabilities are … Read more
As resources become scarce and expensive, it has become increasingly important for players in a decentralised supply chain to collaborate. One of the main challenges in collaboration is to find close to globally optimal solutions without sharing individual player’s private data. Taking a decentralised resource constrained scheduling problem as an example we present a methodology … Read more
We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates … Read more
We study the generalization of split, k-branch split, and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Nonlinear Programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise … Read more
In this paper, we consider an interior point method for nonlinear semidefinite programming. Yamashita, Yabe and Harada presented a primal-dual interior point method in which a nondifferentiable merit function was used. By using shifted barrier KKT conditions, we propose a differentiable primal-dual merit function within the framework of the line search strategy, and prove the … Read more
We present a new algorithm for the solution of Generalized Nash Equilibrium Problems. This hybrid method combines the robustness of a potential reduction algorithm and the local quadratic convergence rate of the LP-Newton method. We base our local convergence theory on an error bound and provide a new sufficient condition for it to hold that … Read more
It is well known that the conjugate gradient method and a quasi-Newton method, using any well-defined update matrix from the one-parameter Broyden family of updates, produce identical iterates on a quadratic problem with positive-definite Hessian. This equivalence does not hold for any quasi-Newton method. We define precisely the conditions on the update matrix in the … Read more
We consider two linear relaxations of the asymmetric traveling salesman problem (TSP), the Held-Karp relaxation of the TSP’s arc-based formulation, and a particular approximate linear programming (ALP) relaxation obtained by restricting the dual of the TSP’s shortest path formulation. We show that the two formulations produce equal lower bounds for the TSP’s optimal cost regardless … Read more