Alternating Local Search Based VNS for Linear Classification
CitationThis paper is published in Annals of Operations Research, Springer
Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming
Mehrotra and Ozevin computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the barrier decomposition proposed and analyzed in Zhao, and Mehrotra and Ozevin. This paper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA). Although the worst case analysis of the WBDA achieves a first-stage iteration complexity bound that is … Read more
GRASP and path relinking for the max-min diversity problem
The Max-Min Diversity Problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and … Read more
A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs
Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more
An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem
Given ${\cal A} := \{a^1,\ldots,a^m\} \subset \R^n$ with corresponding positive weights ${\cal W} := \{\omega_1,\ldots,\omega_m\}$, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point $c_{\cal A} \in \R^n$ that minimizes the maximum weighted Euclidean distance from $c_{\cal A}$ to each point in ${\cal … Read more
A Two Stage Stochastic Equilibrium Model for Electricity Markets with Two Way Contracts
This paper investigates generators’ strategic behaviors in contract signing in the forward market and power transaction in the electricity spot market. A stochastic equilibrium program with equilibrium constraints (SEPEC) model is proposed to characterize the interaction of generators’ competition in the two markets. The model is an extension of a similar model proposed by Gans, … Read more
Pricing with uncertain customer valuations
Uncertain demand in pricing problems is often modeled using the sum of a linear price-response function and a zero-mean random variable. In this paper, we argue that the presence of uncertainty motivates the introduction of nonlinearities in the demand as a function of price, both in the risk-neutral and risk-sensitive models. We motivate our analysis … Read more
Convergent Network Approximation for the Continuous Euclidean Length Constrained Minimum Cost Path Problem
In many path planning situations we would like to find a path of constrained Euclidean length in 2D that minimises a line integral. We call this the Continuous Length-Constrained Minimum Cost Path Problem (C-LCMCPP). Generally, this will be a non-convex optimization problem, for which continuous approaches only ensure locally optimal solutions. However, network discretisations yield … Read more
Simultaneous Solution of Lagrangean Dual Problems Interleaved with Preprocessing for the Weight Constrained Shortest Path Problem
Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and … Read more
Trust-region and other regularisations of linear least-squares problems
We consider methods for regularising the least-squares solution of the linear system Ax = b. In particular, we propose iterative methods for solving large problems in which a trust-region bound ||x||