In this paper we go one step further in the automatic generation of FPTASes for multi-stage stochastic dynamic programs with scalar state and action spaces, in where the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is … Read more
We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problems finds applications in the area of optimal planning under uncertainty, and can be thought of as … Read more
Common approaches to solve a robust optimization problem decompose the problem into a master problem (MP) and adversarial separation problems (APs). MP contains the original robust constraints, however written only for finite numbers of scenarios. Additional scenarios are generated on the fly by solving the APs. We consider in this work the budgeted uncertainty polytope … Read more
Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a choice model. In this paper, we … Read more
We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more