Online bipartite matching (OBM) is a fundamental model underpinning many important applications, including search engine advertisement, website banner and pop-up ads, and ride-hailing. We study the i.i.d. OBM problem, where one side of the bipartition is fixed and known in advance, while nodes from the other side appear sequentially as i.i.d. realizations of an underlying … Read more
We study the problem of a retailer that maximizes profit through joint replenishment, pricing and removal decisions. This problem is motivated by the observation that retailers usually retain rights to remove inventory from their network either by returning it to the suppliers or through liquidation in the face of random demand and capacity constraints. We … Read more
We consider integer optimization problems where variables can potentially take fractional values, but this occurrence is penalized in the objective function. This general situation has relevant examples in scheduling (preemption), routing (split delivery), cutting and telecommunications, just to mention a few. However, the general case in which variables integrality can be relaxed at cost of … Read more
Multistage stochastic programming problems are an important class of optimisation problems, especially in energy planning and scheduling. These problems and their solution methods have been of particular interest to researchers in stochastic programming recently. Because of the large scenario trees that these problems induce, current solution methods require random sampling of the tree in order … Read more
The multiple Checkpoint Ordering Problem (mCOP) aims to find an optimal arrangement of n one-dimensional departments with given lengths such that the total weighted sum of their distances to m given checkpoints is minimized. In this paper we suggest an integer linear programming (ILP) approach and a dynamic programming (DP) algorithm, which is only exact … 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
Christofides and Hadjiconstantinou introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably … Read more
We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range … Read more
We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more
In various settings time consistency in dynamic programming has been addressed by many authors going all the way back to original developments by Richard Bellman. The basic idea of the involved dynamic principle is that a policy designed at the first stage, before observing realizations of the random data, should not be changed at the … Read more