This paper is devoted to the approximate resolution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical … Read more
This paper is devoted to the study of a resource-constrained scheduling problem which arises in relation to the operability of certain high availability real-time distributed systems. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the … Read more
This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process … Read more
This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP) while incorporating techniques from … Read more
Sparse PCA seeks approximate sparse “eigenvectors” whose projections capture the maximal variance of data. As a cardinality-constrained and non-convex optimization problem, it is NP-hard and yet it is encountered in a wide range of applied fields, from bio-informatics to finance. Recent progress has focused mainly on continuous approximation and convex relaxation of the hard cardinality … Read more
This paper studies a distribution system consisting of multiple retail locations with transshipment operations among the retailers. Due to the difficulty in computing the optimal solution imposed by the transshipment operations and in estimating shortage cost from a practical perspective, we propose a robust optimization framework for analyzing the impact of transshipment operations on such … Read more
The Network Interdiction Problem involves interrupting an adversary’s ability to maximize flow through a capacitated network by destroying portions of the network. A budget constraint limits the amount of the network that can be destroyed. In this paper, we study a stochastic version of the network interdiction problem in which the successful destruction of an … Read more
We present a robust optimization approach to the problem of pricing a capacitated product over a finite time horizon in the presence of demand uncertainty. This technique does not require the knowledge of the underlying probability distributions, which in practice are difficult to estimate accurately, and instead models random variables as uncertain parameters belonging to … Read more
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
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