We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations: in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron–a problem that often arises in combinatorial optimization–has supermodular optimal costs. In addition, we examine the computational complexity of the least core … Read more
In the paper, we focus primarily on the problem of recovering a linear form g’*x of unknown “signal” x known to belong to a given convex compact set X in R^n from N independent realizations of a random variable taking values in a finite set, the distribution p of the variable being affinely parameterized by … Read more
In engineering design, an optimized solution often turns out to be suboptimal, when implementation errors are encountered. While the theory of robust convex optimization has taken significant strides over the past decade, all approaches fail if the underlying cost function is not explicitly given; it is even worse if the cost function is nonconvex. In … Read more
We present a general metaheuristic for joint chance-constrained stochastic programs with discretely distributed parameters. We give a reformulation of the problem that allows us to define a finite solution space. We then formulate a novel neighborhood for the problem and give methods for efficiently searching this neighborhood for solutions that are likely to be improving. … Read more
We present a strong duality theory for optimization problems over symmetric cones without assuming any constraint qualification. We show important complexity implications of the result to semidefinite and second order conic optimization. The result is an application of Borwein and Wolkowicz’s facial reduction procedure to express the minimal cone. We use Pataki’s simplified analysis and … Read more
In this paper, we propose lifting techniques for generating strong cuts for nonlinear programs that are globally-valid. The theory is geometric and provides intuition into lifting-based cut generation procedures. As a special case, we find short proofs of earlier results on lifting techniques for mixed-integer programs. Using convex extensions, we obtain conditions that allow sequence-independent … Read more
A finite test set for an integer maximization problem enables us to verify whether a feasible point attains the global maximum. We establish in this paper several general results that apply to integer maximization problems with nonlinear objective functions. CitationOperations Research Letters 36 (2008) 439–443ArticleDownload View PDF
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints … Read more
In this paper, simple linear programming procedure is proposed for generating all efficient extreme points and all efficient extreme rays of a multiple objective linear programming problem (V P). As an application we solve the linear multiplicative programming associated with the problem (VP). CitationsubmittedArticleDownload View PDF
We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the … Read more