American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Production planning in a three-stock reverse-logistics system with deteriorating items under a periodic review policy
  • JIMO Home
  • This Issue
  • Next Article
    Cardinality constrained portfolio selection problem: A completely positive programming approach
July  2016, 12(3): 1057-1073. doi: 10.3934/jimo.2016.12.1057

Pseudo-polynomial time algorithms for combinatorial food mixture packing problems

Shinji Imahori 1, , Yoshiyuki Karuno 2, and  Kenju Tateishi 3,

1. 

Faculty of Science and Engineering, Chuo University, Kasuga 1-13-27, Bunkyo-ku, Tokyo 112-8551, Japan
2. 

Faculty of Mechanical Engineering, Kyoto Institute of Technology, Matsugasaki, Sakyo-ku, Kyoto 606-8585, Japan
3. 

Graduate School of Science and Technology, Kyoto Institute of Technology, Matsugasaki, Sakyo-ku, Kyoto 606-8585, Japan

Received  November 2014 Revised  April 2015 Published  September 2015

A union $\mathcal{I}=\mathcal{I}_{1}\cup \mathcal{I}_{2}\cup \cdots \cup \mathcal{I}_{m}$ of $m$ sets of items is given, where for each $i=1,2,\ldots,m$, $\mathcal{I}_{i}=\{I_{ik} \mid k=1,2,\ldots,n\}$ denotes a set of $n$ items of the $i$-th type and $I_{ik}$ denotes the $k$-th item of the $i$-th type. Each item $I_{ik}$ has an integral weight $w_{ik}$ and an integral priority $p_{ik}$. The food mixture packing problem to be discussed in this paper asks to find a union $\mathcal{I}'=\mathcal{I}'_{1}\cup \mathcal{I}'_{2}\cup \cdots \cup \mathcal{I}'_{m}$ of $m$ subsets of items so that for each $i=1,2,\ldots,m$, the sum weight of chosen items of the $i$-th type for $\mathcal{I}'_{i} \subseteq \mathcal{I}_{i}$ is no less than an integral indispensable bound $b_{i}$, and the total weight of chosen items for $\mathcal{I}'$ is no less than an integral target weight $t$. The total weight of chosen items for $\mathcal{I'}$ is minimized as the primary objective, and further the total priority of chosen items for $\mathcal{I'}$ is maximized as the second objective. In this paper, the known time complexity $O(mnt+mt^{m})$ is improved to $O(mnt+mt^{2})$ for an arbitrary $m\geq 3$ by a two-stage constitution algorithm with dynamic programming procedures. The improved time complexity figures out the weak NP-hardness of the food mixture packing problem.
Keywords: food packaging quality., mathematical modeling, Combinatorial optimization, dynamic programming, pseudo-polynomial time algorithms.
Mathematics Subject Classification: Primary: 90C27, 90C39; Secondary: 68Q2.
Citation: Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057
References:
[1]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,, W.H. Freeman, (1979). Google Scholar

[2]

S. Imahori and Y. Karuno, Pseudo-polynomial time algorithms for food mixture packing by automatic combination weighers,, in Proceedings of International Symposium on Scheduling 2013 (ISS 2013), (2013), 59. Google Scholar

[3]

S. Imahori, Y. Karuno, H. Nagamochi and X. Wang, Kansei engineering, humans and computers: Efficient dynamic programming algorithms for combinatorial food packing problems,, International Journal of Biometrics, 3 (2011), 228. doi: 10.1504/IJBM.2011.040817. Google Scholar

[4]

S. Imahori, Y. Karuno, R. Nishizaki and Y. Yoshimoto, Duplex and quasi-duplex operations in automated food packing systems,, in IEEE Xplore of the Fifth IEEE/SICE International Symposium on System Integration (SII 2012), (2012), 810. doi: 10.1109/SII.2012.6427267. Google Scholar

[5]

S. Imahori, Y. Karuno and K. Tateishi, Dynamic programming algorithms for producing food mixture packages by automatic combination weighers,, Journal of Advanced Mechanical Design, 8 (2014), 1. doi: 10.1299/jamdsm.2014jamdsm0065. Google Scholar

[6]

Ishida Co., Ltd., Products (Total System Solutions), Weighing and Packaging,, 2015. Available from: , (). Google Scholar

[7]

K. Kameoka and M. Nakatani, Feed control criterion for a combination weigher and its effects (in Japanese),, Transactions of the Society of Instrument and Control Engineers, 37 (2001), 911. Google Scholar

[8]

K. Kameoka, M. Nakatani and N. Inui, Phenomena in probability and statistics found in a combinatorial weigher (in Japanese),, Transactions of the Society of Instrument and Control Engineers, 36 (2000), 388. Google Scholar

[9]

Y. Karuno, H. Nagamochi and X. Wang, Bi-criteria food packing by dynamic programming,, Journal of the Operations Research Society of Japan, 50 (2007), 376. Google Scholar

[10]

Y. Karuno, H. Nagamochi and X. Wang, Optimization problems and algorithms in double-layered food packing systems,, Journal of Advanced Mechanical Design, 4 (2010), 605. doi: 10.1299/jamdsm.4.605. Google Scholar

[11]

Y. Karuno, K. Takahashi and A. Yamada, Dynamic programming algorithms with data rounding for combinatorial food packing problems,, Journal of Advanced Mechanical Design, 7 (2013), 233. doi: 10.1299/jamdsm.7.233. Google Scholar

[12]

H. Morinaka, Automatic combination weigher for product foods (in Japanese),, Journal of the Japan Society of Mechanical Engineers, 103 (2000), 130. Google Scholar

[13]

H. A. Wurdemann, V. Aminzadeh, J. S. Dai, J. Reed and G. Purnell, Category-based food ordering processes,, Trends in Food Science & Technology, 22 (2011), 14. doi: 10.1016/j.tifs.2010.10.003. Google Scholar

[14]

Yamato Scale Co., Ltd., Category Search, Filling and Packaging,, 2015. Available from: , (). Google Scholar

show all references

References:
[1]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,, W.H. Freeman, (1979). Google Scholar

[2]

S. Imahori and Y. Karuno, Pseudo-polynomial time algorithms for food mixture packing by automatic combination weighers,, in Proceedings of International Symposium on Scheduling 2013 (ISS 2013), (2013), 59. Google Scholar

[3]

S. Imahori, Y. Karuno, H. Nagamochi and X. Wang, Kansei engineering, humans and computers: Efficient dynamic programming algorithms for combinatorial food packing problems,, International Journal of Biometrics, 3 (2011), 228. doi: 10.1504/IJBM.2011.040817. Google Scholar

[4]

S. Imahori, Y. Karuno, R. Nishizaki and Y. Yoshimoto, Duplex and quasi-duplex operations in automated food packing systems,, in IEEE Xplore of the Fifth IEEE/SICE International Symposium on System Integration (SII 2012), (2012), 810. doi: 10.1109/SII.2012.6427267. Google Scholar

[5]

S. Imahori, Y. Karuno and K. Tateishi, Dynamic programming algorithms for producing food mixture packages by automatic combination weighers,, Journal of Advanced Mechanical Design, 8 (2014), 1. doi: 10.1299/jamdsm.2014jamdsm0065. Google Scholar

[6]

Ishida Co., Ltd., Products (Total System Solutions), Weighing and Packaging,, 2015. Available from: , (). Google Scholar

[7]

K. Kameoka and M. Nakatani, Feed control criterion for a combination weigher and its effects (in Japanese),, Transactions of the Society of Instrument and Control Engineers, 37 (2001), 911. Google Scholar

[8]

K. Kameoka, M. Nakatani and N. Inui, Phenomena in probability and statistics found in a combinatorial weigher (in Japanese),, Transactions of the Society of Instrument and Control Engineers, 36 (2000), 388. Google Scholar

[9]

Y. Karuno, H. Nagamochi and X. Wang, Bi-criteria food packing by dynamic programming,, Journal of the Operations Research Society of Japan, 50 (2007), 376. Google Scholar

[10]

Y. Karuno, H. Nagamochi and X. Wang, Optimization problems and algorithms in double-layered food packing systems,, Journal of Advanced Mechanical Design, 4 (2010), 605. doi: 10.1299/jamdsm.4.605. Google Scholar

[11]

Y. Karuno, K. Takahashi and A. Yamada, Dynamic programming algorithms with data rounding for combinatorial food packing problems,, Journal of Advanced Mechanical Design, 7 (2013), 233. doi: 10.1299/jamdsm.7.233. Google Scholar

[12]

H. Morinaka, Automatic combination weigher for product foods (in Japanese),, Journal of the Japan Society of Mechanical Engineers, 103 (2000), 130. Google Scholar

[13]

H. A. Wurdemann, V. Aminzadeh, J. S. Dai, J. Reed and G. Purnell, Category-based food ordering processes,, Trends in Food Science & Technology, 22 (2011), 14. doi: 10.1016/j.tifs.2010.10.003. Google Scholar

[14]

Yamato Scale Co., Ltd., Category Search, Filling and Packaging,, 2015. Available from: , (). Google Scholar

[1]

J. David Logan, William Wolesensky, Anthony Joern. Insect development under predation risk, variable temperature, and variable food quality. Mathematical Biosciences & Engineering, 2007, 4 (1) : 47-65. doi: 10.3934/mbe.2007.4.47
[2]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[3]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515
[4]

Ruiqi Li, Yifan Chen, Xiang Zhao, Yanli Hu, Weidong Xiao. Time series based urban air quality predication. Big Data & Information Analytics, 2016, 1 (2&3) : 171-183. doi: 10.3934/bdia.2016003
[5]

Martino Bardi, Shigeaki Koike, Pierpaolo Soravia. Pursuit-evasion games with state constraints: dynamic programming and discrete-time approximations. Discrete & Continuous Dynamical Systems - A, 2000, 6 (2) : 361-380. doi: 10.3934/dcds.2000.6.361
[6]

Zhanyou Ma, Pengcheng Wang, Wuyi Yue. Performance analysis and optimization of a pseudo-fault Geo/Geo/1 repairable queueing system with N-policy, setup time and multiple working vacations. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002
[7]

Patrice Bertail, Stéphan Clémençon, Jessica Tressou. A storage model with random release rate for modeling exposure to food contaminants. Mathematical Biosciences & Engineering, 2008, 5 (1) : 35-60. doi: 10.3934/mbe.2008.5.35
[8]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473
[9]

Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics & Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471
[10]

Avner Friedman, Wenrui Hao. Mathematical modeling of liver fibrosis. Mathematical Biosciences & Engineering, 2017, 14 (1) : 143-164. doi: 10.3934/mbe.2017010
[11]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks & Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315
[12]

Eric Dubach, Robert Luce, Jean-Marie Thomas. Pseudo-Conform Polynomial Lagrange Finite Elements on Quadrilaterals and Hexahedra. Communications on Pure & Applied Analysis, 2009, 8 (1) : 237-254. doi: 10.3934/cpaa.2009.8.237
[13]

Dmitri E. Kvasov, Yaroslav D. Sergeyev. Univariate geometric Lipschitz global optimization algorithms. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 69-90. doi: 10.3934/naco.2012.2.69
[14]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
[15]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013
[16]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[17]

Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167
[18]

Gang Bao. Mathematical modeling of nonlinear diffracvtive optics. Conference Publications, 1998, 1998 (Special) : 89-99. doi: 10.3934/proc.1998.1998.89
[19]

Daniel Glasscock, Andreas Koutsogiannis, Florian Karl Richter. Multiplicative combinatorial properties of return time sets in minimal dynamical systems. Discrete & Continuous Dynamical Systems - A, 2019, 39 (10) : 5891-5921. doi: 10.3934/dcds.2019258
[20]

David Yang Gao, Changzhi Wu. On the triality theory for a quartic polynomial optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (1) : 229-242. doi: 10.3934/jimo.2012.8.229

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (12)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences