This paper considers how to optimally set the basestock level for a single buffer when demand is uncertain, in a robust framework. We present a family of algorithms based on decomposition that scale well to problems with hundreds of time periods, and theoretical results on more general models. CitationCORC report TR-2005-09, Columbia University, November 2005ArticleDownload … Read more
This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … Read more
We identify the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling by sorting through various options that involve the primal simplex, dual simplex, and barrier methods for linear programming, the network simplex method for network flow problems, and Dantzig-Wolfe decomposition and column generation. CitationSubmitted for publication.ArticleDownload View PDF
The paper describes various combinatorial and algorithmic applications of hyperbolic (multivariate) polynomials . Section 2.2 introduces a new class of polynomials , which include as hyperbolic polynomials as well volume polynomials $Vol(x_1C_1+…+x_nC_n)$ , where $C_i$ are convex compact subsets of $R^n$. This extension leads to randomized poly-time algorithm to approximate $M(C_1,…,C_n)$ (the mixed volume) within … Read more
Suppose that for a given optimisation problem (which might be multicriteria problem or a single-criteron problem), an additional objective function is introduced. How does the the set of solutions, i.~e.\ the set of efficient points change when instead of the old problem the new multicriteria problem is considered? How does the set of properly efficient … Read more
We show that linear programs (LPs) admit regularizations that either contract the original (primal) solution set or leave it unchanged. Any regularization function that is convex and has compact level sets is allowed–differentiability is not required. This is an extension of the result first described by Mangasarian and Meyer (SIAM J. Control Optim., 17(6), pp. … Read more
We use robust optimization techniques to formulate an IMRT treatment planning problem in which the dose matrices are uncertain, due to both dose calculation errors and inter-fraction positional uncertainty of tumor and organs. When the uncertainty is taken into account, the original linear programming formulation becomes a second-order cone program. We describe a novel and … Read more
We study the behavior of the conjugate-gradient method for solving a set of linear equations, where the matrix is symmetric and positive definite with one set of eigenvalues that are large and the remaining are small. We characterize the behavior of the residuals associated with the large eigenvalues throughout the iterations, and also characterize the … Read more
In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet. We then present two different constructions that yield … Read more
We study a bilevel noncooperative game-theoretic model of restructured electricity markets, with locational marginal prices. Each player in this game faces a bilevel optimization problem that we remodel as a mathematical program with equilibrium constraints, MPEC. The corresponding game is an example of an EPEC, equilibrium problem with equilibrium constraints. We establish sufficient conditions for … Read more