We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more
This paper studies dynamic stochastic optimization problems parametrized by a random variable. Such problems arise in many applications in operations research and mathematical finance. We give sufficient conditions for the existence of solutions and the absence of a duality gap. Our proof uses extended dynamic programming equations, whose validity is established under new relaxed conditions … Read more
We consider the problem of dynamic portfolio optimization in a discrete-time, finite-horizon setting. Our general model considers risk aversion, portfolio constraints (e.g., no short positions), return predictability, and transaction costs. This problem is naturally formulated as a stochastic dynamic program. Unfortunately, with non-zero transaction costs, the dimension of the state space is at least as … Read more
In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more
This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … Read more
This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … Read more
In this paper, we present an Uzawa-based heuristic that is adapted to some type of stochastic optimal control problems. More precisely, we consider dynamical systems that can be divided into small-scale independent subsystems, though linked through a static almost sure coupling constraint at each time step. This type of problem is common in production/portfolio management … Read more
In this paper we discuss time consistency of multi-stage risk averse stochastic programming problems. We approach the concept of time consistency from an optimization point of view. That is, at each state of the system optimality of a decision policy should not involve states which cannot happen in the future. We also discuss a relation … Read more
Assigning products to and retrieving them from proper storage locations in a unit-load warehouse are crucial in minimizing its operating cost. The problem becomes intractable when the warehouse faces uncertain demand in a dynamic setting. We assume a factor-based demand model in which demand for each product in each period is affinely dependent on some … Read more
In this paper we present some new, practical, geometric optimization techniques for computing polygon partitions, 1D and 2D point, interval, square and rectangle covers, as well as 1D and 2D interval and rectangle K-centers. All the techniques we present have immediate applications to several cost optimization and facility location problems which are quite common in … Read more