This paper introduces a generalized isotonic optimization framework over an arborescence graph, where each node incurs state-dependent convex costs and a fixed cost upon strict increases. We begin with the special case in which the arborescence is a path and develop a dynamic programming (DP) algorithm with an initial complexity of $O(n^3)$, which we improve … Read more
In wholesale electricity markets, electricity producers and the \emph{independent system operator} (ISO) play a central role. The ISO is responsible for minimizing production costs while satisfying supply–demand balance and capacity constraints. In this paper, we study a continuous-time problem in which the ISO seeks to minimize the joint cost of operation and investment in an … Read more
Stochastic Dual Dynamic Programming (SDDP) is widely recognized as the predominant methodology for solving large-scale multistage stochastic linear programming (MSLP) problems. This paper aims to contribute to the extant literature by conducting a comprehensive survey of the literature on SDDP within the realm of practical applications. We systematically identify and analyze the various domains where … Read more
We consider a dynamic lot sizing model in which end products to satisfy demands are obtained by remanufacturing m core types of differing quality, where m ≥ 1, or manufacturing from raw materials. In the model, we have separate setup costs associated with manufacturing and remanufacturing. As is widely known, remanufacturing is an environmental preferable … Read more
The Lovasz theta function is a semidefinite programming (SDP) relaxation for the maximum weighted stable set problem, which is tight for perfect graphs. However, even for perfect graphs, there is no known rounding method guaranteed to extract a maximum weighted stable set from the SDP solution. In this paper, we develop a novel rounding scheme … Read more
We investigate a multi-stage version of the selection problem where the variation between solutions in consecutive stages is either penalized in the objective function or bounded by hard constraints. While the former problem turns out to be tractable, the complexity of the latter problem depends on the type of bounds imposed: When bounding the number … Read more
The representation of a function in a higher-dimensional space is often referred to as lifting. Liftings can be used to reduce complexity. We are interested in the question of how liftings affect the local convergence of Newton’s method. We propose algorithms to construct liftings that potentially reduce the number of iterations via analysis of local … Read more
ArticleDownload View PDF
In this note, we polynomially reduce an instance of the partition problem to a dynamic lot sizing problem, and show that solving the latter problem solves the former problem. By solving the dynamic program formulation of the dynamic lot sizing problem, we show that the instance of the partition problem can be solved with pseudo-polynomial … Read more
In this paper, we introduce an approach for obtaining probabilistically guaranteed upper and lower bounds on the true optimal value of stopping problems. Bounds of existing simulation-and-regression approaches, such as those based on least squares Monte Carlo and information relaxation, are stochastic in nature and therefore do not come with a finite sample guarantee. Our … Read more