Knapsack Sets Dynamic Programming One Continuous Variable

• Access throughyour institution

Discrete Optimization

An iterative dynamic programming approach for the temporal knapsack problem

Abstract

In this paper, we address the temporal knapsack problem (TKP), a generalization of the classical knapsack problem, where selected items enter and leave the knapsack at fixed dates. We model the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature.

Introduction

In this paper, we address the Temporal Knapsack Problem (TKP), a generalization of the well-known knapsack problem, where each item has a time window during which it can be added to the knapsack, and the capacity constraint is considered at each time period. The name Temporal Knapsack was introduced in Bartlett et al. (2005), although the problem had already been studied in Chen, Hassin, and Tzur (2002) as a bandwidth allocation problem. Formally, the TKP can be stated as follows.

Problem 1 Temporal Knapsack Problem

Let $\mathcal{I}=\{1,\dots ,n\}$ be a set of items. Each item $i\in \mathcal{I}$ has a profit $p_i\in {\mathbb{R}}_{+},$ a size $w_i\in \mathbb{N},$ and a time interval $[s_i,f_i),$ where $s_i,f_i\in \mathbb{N}$ and $s_i<f_i$ . Moreover, let $W\in \mathbb{N}$ be the weight of the knapsack. A feasible solution comprises a subset $\mathcal{J}$ of $\mathcal{I}$ such that for any value of $m\in \mathbb{N},$ the sum of the sizes of the items in $\mathcal{J}$ whose time interval contains $m$ is less than or equal to $W$ . The Temporal Knapsack Problem is the problem of finding a feasible subset $\mathcal{J}$ of $\mathcal{I}$ with maximum profit.

Fig. 1 represents an instance of TKP with three items, and its two inclusion-wise maximal solutions. One can see that no solution can contain both items 2 and 3, since they are both active at time 3, and the sum of their sizes is larger than the capacity of the container. Conversely, 1 and 3 can be selected in the same solution, despite their size, since their time intervals do not overlap.

In its general version, the TKP is NP-hard in the strong sense (Bonsma, Schulz, & Wiese, 2014). The first results proposed for TKP were focused on a theoretical characterization: a polynomially solvable case (Arkin & Silverberg, 1987), and approximation results (Calinescu, Chakrabarti, Karloff, Rabani, 2002, Chen, Hassin, Tzur, 2002). Two dynamic programs were proposed by Chen et al. (2002) and Caprara, Furini, and Malaguti (2013), and are described more precisely in the next section. A Dantzig-Wolfe reformulation was proposed by Caprara et al. (2013), where the idea is to partition the time horizon into consecutive time periods (blocks). For each block, the variables related to the items whose time intervals intersect the corresponding time period are duplicated. Each subproblem is a smaller TKP, while the master problem makes sure that the duplicated variables related to the same item have the same value. Based on this reformulation, Caprara et al. (2013) proposed a branch-and-price algorithm. These results were improved in Gschwind and Irnich (2017) using an innovative stabilization technique. This method relies on so-called dual-optimal inequalities, and uses dominance relations between (pairs of) items to add additional effective dual cuts that are satisfied by at least one optimal dual solution. Finally, Caprara, Furini, Malaguti, and Traversi (2016) proposed a method based on the previous Dantzig-Wolfe reformulation, where each subproblem is itself decomposed into a master problem and several smaller TKPs, and solved by branch-and-price.

In this paper, we propose a new exact algorithm for TKP. It is based on an exponential size dynamic program, where the size of the state-space depends exponentially on the number of items $n$ . Several methods have been proposed in the literature to tackle such large dynamic programs (Ibaraki, 1987, Righini, Salani, 2008). All of them are based on the concept of state-space relaxation (Christofides, Mingozzi, & Toth, 1981). Among them, we selected the Successive Sublimation Dynamic Programming (SSDP) method, originally proposed by Ibaraki (1987), which has been successfully adapted to several one-machine scheduling problems (see Tanaka, Fujikuma, & Araki, 2009 for example).

SSDP consists in solving a relaxation of the original dynamic program, removing some transitions that cannot belong to an optimal solution, and incrementally reintroducing the relaxed constraints until an optimality proof is reached. An originality of this method is that it does not use a label-setting algorithm, but builds explicitly the graph representation of each relaxed dynamic program. The effectiveness of the method is highly dependent on the capability to reuse information from the previous iterations (primal and dual bounds, variable fixing).

As is the case with many generic methods, obtaining an effective version of SSDP for a new problem is not straightforward. We show numerically that a basic application of this technique to TKP is not competitive compared to state-of-the-art solvers. We then propose several advanced algorithmic techniques which allow a significant improvement on the computational results.

We implemented our algorithms and compared them empirically against a commercial MIP solver, using instances proposed in Caprara et al. (2013). We also report results obtained by Gschwind and Irnich (2017) on these instances. These experiments show that our algorithm is competitive compared to the state of the art.

The rest of the paper is organized as follows. In Section 2, we formally discuss integer programming formulations and dynamic programs for TKP. In Section 3, we describe an application of SSDP to TKP. Section 4 outlines the various refinements of the method that are necessary to obtain competitive results. We present our computational experiments in Section 5 before offering some brief concluding remarks and suggestions for future research.

Section snippets

Integer programming and dynamic programming models

In this section, we discuss compact MIP formulations and dynamic programs for TKP.

Specializing successive sublimation dynamic programming to TKP

In this section, we explain how SSDP can be used to solve TKP. We first describe the generic algorithm, emphasizing the main points to be studied, namely choosing a relaxation, solving the relaxation, and updating the relaxation to obtain a refined model. We then address each point specifically.

Refinements of SSDP to solve TKP effectively

Preliminary computational experiments showed that a direct implementation of SSDP for TKP is not able to produce results that can compete with state-of-the-art TKP solvers. This can be explained by several issues: the method requires a long computation time to build the first relaxation, many states that are not useful are generated when the first relaxation is computed, and the gap is not reduced significantly when only one constraint at a time is reintroduced in the sublimation phase. We now

Computational experiments

In this section, we provide experimental results for our methods. For each refinement proposed, we evaluate its impact on the performance of the general algorithm. Finally, we compare our results to those of Gschwind and Irnich (2017) and to the results obtained using an all-purpose commercial Integer Linear Programming solver. In this section, we consider an instance as solved if the algorithm finds an optimal solution and proves its optimality.

All our experiments are conducted using 2

Conclusion

In this paper we have proposed a new algorithm for solving the temporal knapsack problem. It is based on an exponentially large dynamic program, which is solved effectively using SSDP. With the help of several refinements that we describe, our method is able to obtain results that are competitive with those of the literature. The strategies that we propose are subject to many parameters, and the numerical experiments suggest that better parameterization could yield better results (notably the

Acknowledgements

We would like to thank Fabio Furini and Enrico Malaguti for sending us the detailed results of their experiments. We also would like to thank Timo Gschwind for running additional experiments for us.

This work was funded byInvestments for the future Program IdEx Bordeaux, Cluster of Excellence SySNum.

Experiments presented in this paper were carried out using the PLAFRIM experimental testbed being developed under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB

References (18)

• et al.

  A dynamic programming method for single machine scheduling

  European Journal of Operational Research

  (1994)

• A. Caprara et al.

  Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation

  Information Processing Letters

  (2016)

• E.M. Arkin et al.

  Scheduling with fixed start and end times

  Discrete Applied Mathematics

  (1987)

• F. Barahona et al.

  The volume algorithm: Producing primal solutions with a subgradient method

  Mathematical Programming

  (2000)

• M. Bartlett et al.

  The temporal knapsack problem and its solution

  Integration of AI and OR techniques in constraint programming for combinatorial optimization problems

  (2005)

• D.P. Bertsekas et al.

  Convex optimization algorithms

  (2015)

• P. Bonsma et al.

  A constant-factor approximation algorithm for unsplittable flow on paths

  SIAM Journal on Computing

  (2014)

• G. Calinescu et al.

  Improved approximation algorithms for resource allocation

  Proceedings of the 9th international conference on integer programming and combinatorial optimization, IPCO 2002

  (2002)

• A. Caprara et al.

  Uncommon Dantzig-Wolfe reformulation for the temporal knapsack problem

  INFORMS Journal on Computing

  (2013)

There are more references available in the full text version of this article.

Cited by (6)

Recommended articles (6)

View full text

© 2021 Elsevier B.V. All rights reserved.

wakelinwairespleet1990.blogspot.com

Source: https://www.sciencedirect.com/science/article/abs/pii/S0377221720310791

Share :