iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10878-014-9717-1
Algorithms for randomized time-varying knapsack problems | Journal of Combinatorial Optimization Skip to main content

Advertisement

Springer Nature Link
Log in

Algorithms for randomized time-varying knapsack problems

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this paper, we first give the definition of randomized time-varying knapsack problems (\(\textit{RTVKP}\)) and its mathematic model, and analyze the character about the various forms of \(\textit{RTVKP}\). Next, we propose three algorithms for \(\textit{RTVKP}\): (1) an exact algorithm with pseudo-polynomial time based on dynamic programming; (2) a 2-approximation algorithm for \(\textit{RTVKP}\) based on greedy algorithm; (3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of \(\textit{RTVKP}\), the simulation computation results coincide with the theory analysis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ashlock D (2006) Evolutionary computation for modeling and optimization. Springer, Berlin

    MATH  Google Scholar 

  • Bansal JC, Deep K (2012) A modified binary particle swarm optimization for knapsack problems. Appl Math Comput 218(22):11042–11061

    Article  MathSciNet  MATH  Google Scholar 

  • Brassard G, Bratley P (2003) Fundamentals of algorithmics. Prentice Hall, Inc., London

  • Cormen TH, Leiserson CE, Rivest RL et al (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge, pp 370–399

    MATH  Google Scholar 

  • Das S, Suganthan PN (2011) Differential evolution: a survey of the state-of-the-art. IEEE Trans Evol Comput 15(1):4–31

    Article  Google Scholar 

  • Dorigo M, Caro G (1999) The ant colony optimization meta-heuristic. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw Hill, London, pp 11–32

    Google Scholar 

  • Du D-Z, Ko K-I (2000) Theory of computational complexity. Wiley-Interscience, New York

    Book  MATH  Google Scholar 

  • Du D-Z, Ko K-I, Hu X (2012) Design and analysis of approximation algorithms. Springer Science Business Media LLC, Berlin

  • Eiben AE, Arts EH, Van Hee KM (1991) Global convergence of genetic algorithm: an infinite Markov chain analysis. In: Schwefel HP, Manner R (eds) Parallel solving from nature (PPSN1). Springer, Berlin, pp 4–12

    Google Scholar 

  • Elsayed SM, Sarker RA, Essam DL (2014) A new genetic algorithm for solving optimization problems. Eng Appl Artif Intell 27:57–69

    Article  Google Scholar 

  • Ezziane Z (2002) Solving the 0/1 knapsack problem using an adaptive genetic algorithm. Artif Intell Eng Des Anal Manuf 16(1):23–30

    Article  Google Scholar 

  • Eusuff MM, Lansey KE (2003) Optimization of water distribution network design using the shuffled frog-leaping algorithm. J Water Resour Plan Manag 129(3):210–225

    Article  Google Scholar 

  • Geem ZW, Kim JH, Loganathan GV (2001) A new heuristic optimization algorithm: harmony search. Simulation 76(2):60–68

    Article  Google Scholar 

  • Goldberg DE, Smith RE (1987) Nonstationary function optimization using genetic algorithms with dominance and diploidy. In: International conference on genetic algorithms. L. Erlbaum Associates Inc, Hillsdale, pp 59–68

  • Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Boston

    MATH  Google Scholar 

  • Gottlieb J, Marchiori E, Rossi C (2002) Evolutionary algorithms for the satisfiability problem. Evol Comput 10(1):35–50

    Article  Google Scholar 

  • Hembecker F, Lopes HS (2007) Godoy Jr W (2007) Particle swarm optimization for the multidimensional knapsack problem. In: Adaptive and natural computing algorithms, lecture notes in computer science vol 4431, pp 358–365

  • Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor

    Google Scholar 

  • Jun S, Jian L (2009) Solving 0-1 knapsack Problems via a hybrid differential evolution. In: Third international symposium on intelligent information technology application vol 3. IITA, pp 134–137

  • Kang L, Zhou A, Bob M et al. (2004) Benchmarking algorithms for dynamic travelling salesman problems. In: The congress on evolutionary computation. Portland, Oregon

  • Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks (Perth), vol IV. IEEE Service Center, Piscataway, NJ, pp 1942–1948

  • Krishnakumar K (1989) Micro-genetic algorithms for stationary and non-stationary function optimization. In: SPIE intelligent control and adaptive systems, pp 289–296

  • Kumar R, Banerjeec N (2006) Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem. Theor Comput Sci 358(1):104–120

    Article  MATH  Google Scholar 

  • Lee J, Shragowitz E, Sahni S (1988) A hypercube algorithm for the 0/1 knapsack problem. J Parallel Distrib Comput 5(4):438–456

    Article  Google Scholar 

  • Li C, Yang M, Kang L (2006) A new approach to solving dynamic traveling salesman problems. In: Simulated evolution and learning, lecture notes in computer science vol 4247, pp 236–243

  • Li X, Yao X (2012) Cooperatively coevolving particle swarms for large scale optimization. IEEE Trans Evol Comput 16(2):210–224

    Article  MathSciNet  Google Scholar 

  • Liao Y-F, Yau D-H, Chen C-L (2012) Evolutionary algorithm to traveling salesman problems. Comput Math Appl 64(5):788–797

    Article  Google Scholar 

  • Man KF, Tang KS, Kwong S (1996) Genetic algorithms: concepts and applications. IEEE Trans Ind Electron 43(5):519–534

    Article  Google Scholar 

  • Mori N, Kita H, Nishikawa Y (1996) Adaptation to a changing environment by means of the thermodynamical genetic algorithm vol 1141 of LNCS. Springer, Berlin, pp 513–522

  • Rudolph G (1994) Convergence analysis of canonical genetic algorithms. IEEE Trans Neural Netw 5(1):86–101

    Article  Google Scholar 

  • Ryan C (1997) Diploidy without dominance. In: Alander JT (ed) Third nordic workshop on genetic algorithms, pp 63–70

  • Simon D (2013) Evolutionary optimization algorithms. Wiley, New York

    MATH  Google Scholar 

  • Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341–359

    Article  MathSciNet  MATH  Google Scholar 

  • Tsai H-K, Yang J-M, Tsai Y-F et al (2004) An evolutionary algorithm for large traveling salesman problems. IEEE Trans Syst Man Cybern Part B 34(4):1718–1729

    Article  Google Scholar 

  • Uyar AS, Harmanci AE (2005) A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments. Soft Comput 9(11):803–814

    Article  MATH  Google Scholar 

  • Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evol Comput 3(2):82–102

    Article  Google Scholar 

  • Yuen SY, Chow CK (2009) A genetic algorithm that adaptively mutates and never revisits. IEEE Trans Evol Comput 13(2):454–472

    Article  Google Scholar 

Download references

Acknowledgments

Support in part by NSF of China (No. 11271257), the Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 20121303110005), the NSF of Hebei Province (No. A2013205021).

Author information

Authors and Affiliations

  1. College of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang , 050031, China

    Yichao He

  2. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang , 050024, China

    Xinlu Zhang & Suogang Gao

  3. Laboratory of Network and Information Security, Shijiazhuang University of Economics, Shijiazhuang , 050031, China

    Wenbin Li

  4. Department of Industrial and System Engineering, University of Florida, Gainesville, FL , 32611, USA

    Xiang Li

  5. Department of Computer Science, University of Texas at Dallas, Richardson, TX , 75080, USA

    Weili Wu

Authors
  1. Yichao He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xinlu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenbin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Weili Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Suogang Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Suogang Gao.

Appendix: Three large-scale instances of \(fixRTVKP\)

Appendix: Three large-scale instances of \(fixRTVKP\)

For describing the instance of \(fixRTVKP\) succinctly, after sub-problem 0-1 \(KP(n, C_{i-1}, V_{i-1}, W_{i-1})\) changed to sub-problem 0-1 \(KP(n, C_i, V_i, W_i)\), let \((V_i\bigcup W_i)\setminus (V_{i-1}\bigcup W_{i-1})=\{V(l_k,w_k)| 1\le k\le N_1\}\bigcup \{W(l_j,w_j)|1\le j\le N_2\}\), where \(N_1+N_2 \le Threshold, V(l_k,v_k)\) represent that the profit of \(l_k\mathrm{th}\) item of sub-problem 0-1 \(KP_{i-1} (n, C_{i-1}, V_{i-1}, W_{i-1})\) has changed to \(v_k\) in sub-problem 0-1 \(KP_i (n, C_i, V_i, W_i). W(l_j,w_j)\) represent that the weight of \(l_j\mathrm{th}\) item of sub-problem 0-1 \(KP_{i-1} (n, C_{i-1}, V_{i-1}, W_{i-1})\) has changed to \(w_j\) in sub-problem 0-1 \(KP_i (n, C_i, V_i, W_i)\).

Instance 1 of \(fixRTVKP\).

Initial profit set of items is \(V_0[1\ldots 50]=\{\)220, 208, 198, 192, 180, 180, 165, 162, 160, 158, 155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98, 96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58, 56, 50, 30, 20, 15, 10, 8, 5, 3, 1\(\}\).

Initial weight set of items is \(W_0[1\ldots 50]=\{\)80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48, 50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45, 30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2, 1\(\}\).

Initial knapsack capacity is \(C_0=1000\).

The random variation period is 2 s, and \([A_v, B_v]=[1, 225], [A_w, B_w]=[1, 87], [A_c, B_c]=[930,1395]\).

The number of subproblems is \(m=10\), and \(Threshold\le 10\).

The random oscillation change of profit, weight of items and knapsack capacity are following:

\(C_1=1220, C_2=1000, C_3=1341, C_4=1285, C_5=1285, C_6=931, C_7=1119, C_8=947, C_9=1043\).

\((V_1\bigcup W_1)\setminus (V_0\bigcup W_0)=\{W\)(18,71), \(W\)(20,65), \(V\)(9,188), \(W\)(6,45), \(W\)(28,44), \(W\)(46,24), \(V\)(37,217), \(W\)(3,67), \(W\)(33,22), \(V\)(19,96)\(\}\).

\((V_2\bigcup W_2)\setminus (V_1\bigcup W_1)=\{W\)(39,43), \(W\)(18,26), \(W\)(45,81), \(W\)(23,58), \(W\)(15,4), \(W\)(4,83), \(V\)(45,38), \(V\)(38,35), \(W\)(42,38), \(V\)(17,111)\(\}\).

\((V_3\bigcup W_3)\setminus (V_2\bigcup W_2)=\{W\)(39,5), \(W\)(43,38), \(V\)(47,181), \(W\)(30,11), \(W\)(7,43), \(W\)(49,55), \(W\)(35,32), \(V\)(41,17), \(V\)(32,209), \(W\)(40,6)\(\}\).

\((V_4\bigcup W_4)\setminus (V_3\bigcup W_3)=\{V\)(19,58), \(V\)(42,109), \(W\)(40,79), \(W\)(31,58), \(W\)(46,42), \(W\)(21,1), \(V\)(24,148), \(W\)(37,84)\(\}\).

\((V_5\bigcup W_5)\setminus (V_4\bigcup W_4)=\{W\)(32,47), \(W\)(1,64), \(W\)(17,38), \(V\)(42,8), \(V\)(8,138), \(W\)(34,69), \(V\)(10,84), \(W\)(39,72), \(V\)(7,206), \(W\)(19,31)\(\}\).

\((V_6\bigcup W_6)\setminus (V_5\bigcup W_5)=\{W\)(6,11), \(V\)(25,63), \(V\)(34,146), \(W\)(3,78), \(W\)(37,66), \(W\)(47,10), \(V\)(50,94), \(W\)(32,37), \(W\)(50,58), \(V\)(1,189)\(\}\).

\((V_7\bigcup W_7)\setminus (V_6\bigcup W_6)=\{V\)(44,124), \(W\)(8,73), \(W\)(18,20), \(W\)(10,48), \(W\)(2,69), \(V\)(20,57), \(V\)(4,150), \(V\)(45,210), \(V\)(3,46), \(W\)(44,76)\(\}\).

\((V_8\bigcup W_8)\setminus (V_7\bigcup W_7)=\{W\)(4,54), \(W\)(9,7), \(W\)(47,9), \(W\)(40,6), \(V\)(8,223), \(V\)(30,191), \(V\)(9,117), \(W\)(39,17), \(W\)(3,25)\(\}\).

\((V_9\bigcup W_9)\setminus (V_8\bigcup W_8)=\{V\)(47,38), \(V\)(26,84), \(V\)(43,220), \(V\)(32,49), \(W\)(2,17), \(V\)(8,127), \(W\)(40,30), \(W\)(1,75), \(W\)(20,27), \(V\)(2,115)\(\}\).

Instance 2 of \(fixRTVKP\).

Initial profit set of items is \(V_0[1\ldots 100]=\{\)117, 113, 113, 113, 112, 112, 112, 112, 112, 111, 110, 110, 109, 109, 108, 108, 108, 108, 108, 108, 108, 107, 106, 106, 105, 105, 105, 105, 104, 103, 102, 102, 102, 101, 101, 101, 101, 100, 100, 100, 100, 100, 100, 99, 99, 99, 99, 99, 99, 99, 99, 98, 98, 98, 98, 98, 98, 98, 98, 97, 97, 97, 97, 97, 97, 97, 97, 96, 96, 96, 96, 96, 96, 95, 95, 95, 95, 95, 94, 94, 94, 94, 94, 93, 93, 93, 92, 92, 92, 91, 91, 91, 90, 90, 89, 89, 88, 88, 87, 87\(\}\).

Initial weight set of items is \(W_0[1\ldots 100]=\{\)108, 98, 95, 107, 98, 100, 96, 105, 93, 112, 95, 105, 91, 96, 100, 103, 91, 96, 105, 90, 101, 110, 108, 95, 99, 96, 108, 101, 102, 100, 111, 88, 99, 112, 101, 105, 94, 113, 87, 101, 108, 96, 91, 89, 102, 99, 98, 93, 98, 99, 106, 112, 90, 100, 92, 94, 98, 97, 99, 95, 112, 108, 100, 98, 117, 98, 100, 98, 99, 113, 94, 111, 102, 99, 97, 87, 97, 103, 97, 89, 96, 94, 93, 104, 92, 109, 97, 109, 100, 88, 92, 108, 97, 106, 97, 97, 99, 94, 102, 95\(\}\).

Initial knapsack capacity is \(C_0=4995\).

The random variation period is 4 s, and \([A_v,B_v]=[71,121],[A_w,B_w]=[75,127],[A_c,B_c]=[4979,6971]\).

The number of subproblems is \(m=10\),and \(Threshold\le 20\).

The random oscillation change of profit,weight of items and knapsack capacity are following:

\(C_1=6021,C_2=5411,C_3=5900,C_4=6525,C_5=5102,C_6=5698,C_7=6058,C_8=4997,C_9=6414\).

\((V_1\bigcup W_1)\setminus (V_0\bigcup W_0)=\{W\)(68,102), \(W\)(70,111), \(V\)(59,105), \(W\)(6,77), \(W\)(28,125), \(W\)(96,92), \(V\)(37,77), \(W\)(3,122), \(W\)(83,112), \(V\)(19,76), \(V\)(27,103), \(V\)(70,93), \(V\)(100,72), \(W\)(4,89), \(W\)(34,99), \(W\)(42,101), \(W\)(69,76), \(W\)(63,78), \(V\)(60,73), \(W\)(30,111)\(\}\)

\((V_2\bigcup W_2)\setminus (V_1\bigcup W_1)=\{W\)(43,98), \(V\)(41,88), \(W\)(49,120), \(W\)(91,126), \(W\)(51,82), \(W\)(94,125), \(W\)(57,96), \(V\)(77,79), \(V\)(45,74), \(V\)(24,100), \(V\)(19,113), \(V\)(42,110), \(W\)(40,106), \(W\)(31,113), \(W\)(46,75), \(W\)(71,127), \(V\)(74,110), \(V\)(91,103)\(\}\)

\((V_3\bigcup W_3)\setminus (V_2\bigcup W_2)=\{V\)(56,90), \(W\)(53,77), \(W\)(42,122), \(W\)(8,123), \(V\)(88,80), \(W\)(46,80), \(V\)(59,118), \(V\)(23,78), \(V\)(31,113), \(V\)(1,73), \(W\)(56,101), \(V\)(25,106), \(V\)(84,75), \(W\)(3,98), \(W\)(37,121), \(W\)(97,87), \(V\)(100,104), \(W\)(82,92), \(W\)(100,99)\(\}\)

\((V_4\bigcup W_4)\setminus (V_3\bigcup W_3)=\{V\)(28,79), \(V\)(94,86), \(W\)(8,111), \(W\)(18,98), \(W\)(1,77), \(V\)(57,72), \(W\)(25,112), \(W\)(10,118), \(W\)(96,102), \(W\)(44,123), \(V\)(15,88), \(V\)(1,116), \(V\)(81,79), \(V\)(82,76), \(V\)(10,96), \(W\)(23,116), \(W\)(39,86), \(W\)(58,83), \(W\)(16,120)\(\}\) \((V_5\bigcup W_5)\setminus (V_4\bigcup W_4)=\{W\)(35,126), \(W\)(29,90), \(W\)(87,82), \(W\)(17,120), \(V\)(23,107), \(W\)(100,81), \(V\)(93,82), \(W\)(13,78), \(W\)(4,126), \(V\)(56,72), \(W\)(86,89), \(W\)(89,125), \(V\)(58,111), \(W\)(70,109), \(W\)(90,123), \(V\)(69,101), \(W\)(56,117), \(V\)(42,97)\(\}\)

\((V_6\bigcup W_6)\setminus (V_5\bigcup W_5)=\{V\)(54,94), \(W\)(80,101), \(V\)(30,78), \(V\)(67,117), \(W\)(96,86), \(V\)(87,111), \(V\)(83,82), \(W\)(15,116), \(V\)(72,94), \(W\)(14, 103), \(W\)(54,86), \(V\)(33,106), \(W\)(57,94), \(V\)(47,105), \(W\)(45,110), \(W\)(30,116), \(W\)(51,118), \(V\)(45,106), \(W\)(40,103), \(W\)(55,117)\(\}\)

\((V_7\bigcup W_7)\setminus (V_6\bigcup W_6)=\{V\)(14,108), \(W\)(69,101), \(V\)(6,77), \(W\)(3,96), \(V\)(15,103), \(W\)(35,85), \(W\)(60,89), \(V\)(78,96), \(W\)(64,93), \(W\)(86,103), \(W\)(14,123), \(W\)(100,127), \(W\)(44,91), \(W\)(73,98), \(W\)(4,106), \(W\)(94,116), \(W\)(93,111), \(W\)(87,101), \(W\)(88,114)\(\}\)

\((V_8\bigcup W_8)\setminus (V_7\bigcup W_7)=\{W\)(71,98), \(W\)(12,77), \(V\)(68,114), \(W\)(41,95), \(W\)(25,110), \(W\)(77,92), \(V\)(3,102), \(V\)(79,71), \(W\)(85,86), \(W\)(20, 119), \(W\)(88,77), \(V\)(11,85), \(W\)(16,111), \(V\)(44,83), \(W\)(10,113), \(V\)(66,90), \(V\)(75,96), \(V\)(29,96), \(W\)(3,91), \(W\)(97,102)\(\}\)

\((V_9\bigcup W_9)\setminus (V_8\bigcup W_8)=\{W\)(26,120), \(W\)(3,82), \(W\)(27,95), \(W\)(12,76), \(W\)(21,79), \(W\)(89,108), \(W\)(52,81), \(V\)(1,87), \(V\)(79,72), \(V\)(78,98), \(V\)(40,79), \(W\)(58,120), \(V\)(9,121), \(V\)(2,73), \(W\)(29,83), \(W\)(6,96), \(W\)(5,84), \(V\)(73,75), \(W\)(57,77), \(V\)(58,80)\(\}\)

Instance 3 of \(fixRTVKP\).

Initial profit set of items is \(V_0[1\ldots 300]=\{\)383, 519, 420, 272, 166, 125, 354, 374, 44, 540, 9, 108, 13, 4, 403, 376, 599, 432, 184, 439, 114, 45, 333, 238, 95, 10, 195, 542, 231, 476, 129, 582, 223, 210, 442, 250, 116, 211, 342, 461, 300, 368, 327, 524, 460, 158, 171, 261, 24, 89, 174, 214, 455, 87, 222, 588, 25, 453, 256, 458, 375, 129, 104, 428, 344, 165, 556, 166, 359, 440, 373, 210, 576, 14, 548, 105, 396, 116, 243, 196, 583, 307, 141, 345, 544, 500, 250, 280, 449, 388, 107, 135, 182, 235, 521, 480, 48, 272, 17, 190, 122, 6, 380, 226, 243, 567, 513, 444, 469, 567, 86, 520, 573, 125, 494, 123, 30, 276, 288, 219, 191, 91, 531, 382, 508, 541, 574, 568, 111, 581, 452, 351, 74, 411, 239, 513, 39, 43, 213, 484, 189, 314, 240, 25, 253, 430, 239, 494, 71, 296, 568, 359, 460, 242, 307, 186, 366, 215, 347, 240, 386, 178, 510, 118, 487, 468, 116, 376, 136, 593, 500, 514, 294, 508, 514, 322, 164, 544, 20, 224, 408, 436, 418, 234, 102, 558, 452, 362, 527, 240, 288, 179, 544, 174, 498, 370, 325, 521, 543, 248, 341, 516, 49, 440, 319, 346, 551, 454, 587, 374, 29, 511, 424, 419, 127, 471, 596, 385, 578, 148, 28, 421, 542, 358, 108, 538, 143, 405, 59, 267, 300, 458, 140, 383, 364, 445, 424, 488, 42, 65, 179, 303, 435, 370, 304, 584, 277, 82, 33, 77, 382, 434, 438, 232, 169, 160, 390, 24, 340, 332, 541, 91, 574, 318, 317, 577, 356, 332, 237, 172, 415, 489, 444, 102, 46, 406, 122, 269, 18, 296, 516, 42, 490, 107, 109, 294, 391, 164, 162, 438, 518, 122, 290, 504, 448, 408, 205, 266, 390, 470\(\}, \)

Initial weight set of items is \(W_0[1\ldots 300]=\{\)653, 11, 543, 649, 278, 173, 879, 796, 710, 840, 238, 280, 844, 886, 522, 30, 982, 754, 182, 163, 155, 969, 766, 433, 710, 888, 802, 295, 386, 985, 8, 152, 483, 828, 488, 685, 373, 44, 117, 599, 369, 619, 543, 902, 177, 655, 842, 257, 945, 684, 238, 512, 570, 507, 516, 557, 27, 839, 566, 613, 612, 524, 456, 82, 485, 810, 492, 889, 729, 636, 263, 645, 191, 45, 109, 937, 688, 42, 634, 890, 431, 34, 291, 916, 478, 173, 258, 977, 443, 920, 643, 87, 91, 565, 822, 374, 438, 421, 759, 246, 791, 420, 714, 546, 134, 238, 173, 874, 904, 71, 624, 150, 778, 378, 607, 576, 686, 547, 249, 120, 483, 563, 733, 217, 108, 645, 898, 861, 646, 751, 422, 165, 528, 288, 590, 342, 683, 147, 495, 32, 676, 192, 464, 480, 853, 322, 978, 914, 126, 637, 673, 634, 194, 29, 659, 735, 477, 726, 996, 201, 336, 515, 533, 483, 434, 956, 139, 95, 448, 140, 362, 150, 777, 480, 731, 549, 49, 492, 324, 977, 252, 72, 837, 198, 746, 600, 770, 195, 736, 197, 956, 74, 464, 853, 273, 659, 926, 571, 527, 495, 563, 216, 784, 396, 510, 35, 926, 253, 877, 740, 85, 839, 447, 108, 575, 912, 639, 985, 738, 774, 948, 66, 544, 789, 905, 331, 347, 980, 951, 699, 653, 854, 488, 594, 99, 161, 698, 579, 476, 712, 782, 545, 29, 996, 818, 225, 44, 501, 93, 319, 565, 80, 101, 173, 846, 279, 264, 338, 784, 356, 976, 733, 536, 911, 607, 722, 167, 862, 93, 263, 334, 471, 727, 808, 648, 973, 396, 730, 927, 118, 455, 559, 771, 538, 306, 378, 478, 698, 469, 490, 140, 121, 396, 292, 722, 431, 830, 472, 174, 541\(\}\).

Initial knapsack capacity is \(C_0=84340\).

The random variation period is 8 s, and \([A_v,B_v]=[3,600],[A_w,B_w]=[3,998],[A_c,B_c]=[81750,117564]\).

The number of subproblems is \(m=10\), and \(Threshold\le 40\).

The random oscillation change of profit, weight of items and knapsack capacity are following:

\(C_1=95040,C_2=111407,C_3=103409,C_4=107377,C_5=113684,C_6=83289,C_7=112588,C_8=103113,C_9=91317\).

\((V_1\bigcup W_1)\setminus (V_0\bigcup W_0)=\{W\)(168,361), \(W\)(270,787), \(W\)(6,260), \(W\)(28,4), \(W\)(296,989), \(V\)(37,102), \(W\)(3,156), \(W\)(83,492), \(V\)(219,164), \(V\)(127,422), \(V\)(70,181), \(V\)(200,294), \(W\)(204,906), \(W\)(142,742), \(W\)(269,650), \(W\)(263,888), \(V\)(260,354), \(W\)(230,781), \(V\)(36,67), \(W\)(289,229), \(W\)(243,343), \(V\)(147,486), \(W\)(7,228), \(W\)(249,708), \(W\)(85,37), \(V\)(141,185), \(V\)(132,597), \(W\)(40,725), \(W\)(138,625), \(V\)(283,208), \(W\)(34,242), \(V\)(259,581), \(W\)(178,317), \(W\)(187,44), \(W\)(225,151), \(W\)(130,884), \(W\)(298,579)\(\}\).

\((V_2\bigcup W_2)\setminus (V_1\bigcup W_1)=\{W\)(37,446), \(V\)(256,29), \(W\)(53,461), \(W\)(142,811), \(W\)(8,384), \(V\)(288,248), \(W\)(246,944), \(V\)(159,304), \(V\)(123,431), \(V\)(131,270),,\(W\)(156,481), \(V\)(25,208), \(V\)(184,90), \(W\)(3,449), \(W\)(237,413), \(W\)(97,120), \(V\)(100,535), \(W\)(182,753), \(W\)(200,525), \(V\)(168,143), \(W\)(49,574), \(V\)(22,559), \(V\)(14,547), \(V\)(117,400), \(V\)(57,77), \(W\)(225,55), \(W\)(210,52), \(W\)(196,568), \(W\)(244,646), \(V\)(215,536), \(V\)(1,305), \(V\)(181,65), \(V\)(282,456), \(V\)(110,250), \(W\)(223,613), \(W\)(39,278)\(\}\).

\((V_3\bigcup W_3)\setminus (V_2\bigcup W_2)=\{V\)(192,84), \(V\)(257,152), \(W\)(235,371), \(W\)(229,737), \(W\)(170,225), \(W\)(217,968), \(V\)(123,116), \(W\)(300,572), \(V\)(293,472), \(W\)(213,611), \(W\)(4,976), \(W\)(289,456), \(V\)(256,280), \(W\)(86,281), \(W\)(89,553), \(V\)(58,267), \(W\)(270,165), \(W\)(90,59), \(V\)(269,589),,\(V\)(242,545), \(W\)(61,805), \(W\)(240,474), \(V\)(197,544), \(V\)(50,196), \(W\)(298,499), \(V\)(206,571), \(W\)(156,837), \(W\)(2,443), \(W\)(87,314), \(W\)(56,312), \(W\)(13,851), \(W\)(246,332), \(V\)(122,425), \(V\)(83,484), \(W\)(97,305), \(V\)(62,156), \(W\)(74,509)\(\}\).

\((V_4\bigcup W_4)\setminus (V_3\bigcup W_3)=\{W\)(40,324), \(W\)(55,629), \(W\)(250,241), \(W\)(275,137), \(V\)(219,252), \(W\)(259,422), \(W\)(26,584), \(W\)(15,927), \(W\)(75,471), \(V\)(134,565), \(V\)(98,345), \(V\)(74,579), \(W\)(269,263), \(W\)(103,515), \(W\)(128,821), \(W\)(125,70), \(W\)(162,240), \(W\)(133,576), \(W\)(226,86), \(W\)(143,293), \(V\)(165,129), \(V\)(261,290), \(W\)(171,289), \(W\)(234,790), \(W\)(297,686), \(W\)(251,143), \(W\)(296,711), \(V\)(26,267), \(W\)(159,409), \(W\)(267,697), \(W\)(152,587), \(W\)(101,162), \(W\)(127,49), \(V\)(71,584), \(V\)(228,86), \(V\)(265,328), \(W\)(287,684), \(V\)(178,125)\(\}\).

\((V_5\bigcup W_5)\setminus (V_4\bigcup W_4)=\{V\)(129,310), \(W\)(3,25), \(W\)(296,656), \(V\)(231,595), \(W\)(172,438), \(V\)(154,593), \(W\)(225,311), \(W\)(141,934), \(W\)(30,27), \(W\)(59,649), \(W\)(108,524), \(W\)(259,466), \(W\)(161,436), \(W\)(178,131), \(W\)(188,880), \(W\)(61,519), \(W\)(85,484), \(W\)(212,819), \(W\)(257,99), \(W\)(224,544), \(V\)(117,433), \(V\)(127,204), \(V\)(172,550), \(W\)(297,77), \(V\)(213,162), \(V\)(186,124), \(W\)(130,328), \(W\)(260,967), \(V\)(156,96), \(W\)(285,853), \(W\)(173,544), \(V\)(33,574), \(V\)(84,316), \(W\)(168,939), \(W\)(39,234), \(W\)(55,538), \(W\)(76, 546), \(W\)(222,941)\(\}\).

\((V_6\bigcup W_6)\setminus (V_5\bigcup W_5)=\{W\)(284,945), \(V\)(80,578), \(W\)(135,644), \(W\)(157,4), \(V\)(206,387), \(V\)(282,303), \(W\)(142,934), \(W\)(243,509), \(W\)(278,507), \(V\)(253,506), \(V\)(74,475), \(W\)(276,155), \(V\)(11,422), \(W\)(213,818), \(V\)(132,309), \(V\)(186,555), \(V\)(190,279), \(W\)(154,393), \(W\)(41,135), \(V\)(36,390), \(W\)(106,367), \(W\)(4,844), \(W\)(209,411), \(V\)(150,257), \(W\)(128,494), \(W\)(30,367), \(W\)(75,684), \(V\)(116,314), \(W\)(293,822), \(W\)(29,142), \(W\)(176,861), \(V\)(71,310), \(V\)(205,506), \(W\)(164,729), \(W\)(11,262), \(V\)(241,207), \(W\)(120,996), \(W\)(105,945), \(W\)(151,308)\(\}\).

\((V_7\bigcup W_7)\setminus (V_6\bigcup W_6)=\{W\)(23,185), \(V\)(85,495), \(W\)(165,8), \(W\)(246,827), \(V\)(79,576), \(W\)(120,44), \(V\)(45,476), \(W\)(146,611), \(V\)(271,36), \(W\)(133,571), \(W\)(188,685), \(W\)(202,174), \(W\)(228,647), \(V\)(216,186), \(V\)(244,82), \(V\)(64,268), \(W\)(89,389), \(V\)(261,294), \(V\)(255,559), \(V\)(91,178), \(W\)(131,723), \(V\)(68,353), \(W\)(36,357), \(W\)(139,892), \(V\)(125,203), \(W\)(60,388), \(V\)(145,8), \(V\)(27,298), \(W\)(256,128), \(V\)(197,49), \(W\)(265,437), \(W\)(214,209), \(V\)(49,557), \(V\)(207,462), \(V\)(5,130), \(V\)(113,242), \(W\)(66,103), \(V\)(42,319), \(W\)(157,679)\(\}\).

\((V_8\bigcup W_8)\setminus (V_7\bigcup W_7)=\{W\)(231,912), \(W\)(212,768), \(V\)(191,457), \(W\)(35,936), \(W\)(117,507), \(V\)(63,110), \(W\)(104,701), \(W\)(157,151), \(W\)(18,232), \(V\)(29,499), \(W\)(19,925), \(W\)(156,488), \(W\)(204,691), \(W\)(210,961), \(W\)(290,51), \(W\)(154,797), \(W\)(3,950), \(W\)(170,893), \(V\)(109,496), \(W\)(4,36), \(W\)(105,443), \(W\)(114,725), \(V\)(123,559), \(V\)(111,368), \(W\)(209,4), \(V\)(194,322), \(V\)(38,168), \(V\)(1,220), \(W\)(118,282), \(W\)(16,405), \(V\)(213,587), \(W\)(155,152), \(W\)(185,873), \(W\)(116,686), \(W\)(99,168), \(V\)(278,195), \(V\)(190,402), \(V\)(42,245)\(\}\).

\((V_9\bigcup W_9)\setminus (V_8\bigcup W_8)=\{V\)(285,263), \(W\)(272,892), \(W\)(172,380), \(V\)(54,544), \(V\)(126,111), \(V\)(151,209), \(V\)(194,503), \(W\)(217,300), \(V\)(29,370), \(W\)(22,440), \(V\)(217,343), \(V\)(167,386), \(W\)(165,347), \(V\)(22,303), \(W\)(65,428), \(W\)(203,992), \(W\)(242,876), \(W\)(224,642), \(V\)(269,351), \(W\)(108,406), \(W\)(113,223), \(W\)(157,341), \(W\)(297,271), \(W\)(146,767), \(V\)(292,559), \(W\)(115,506), \(V\)(123,405), \(W\)(153,372), \(V\)(239,114), \(V\)(67,320), \(V\)(287,269), \(W\)(234,209), \(W\)(247,467), \(V\)(26,484), \(V\)(3,312), \(V\)(231,591), \(W\)(79,882), \(W\)(49,937), \(W\)(116,594)\(\}\).

Rights and permissions

Reprints and permissions

About this article

Cite this article

He, Y., Zhang, X., Li, W. et al. Algorithms for randomized time-varying knapsack problems. J Comb Optim 31, 95–117 (2016). https://doi.org/10.1007/s10878-014-9717-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-014-9717-1

Keywords

Search

Navigation