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]

Baba Issa Camara, Houda Mokrani, Evans K. Afenya. Mathematical modeling of glioma therapy using oncolytic viruses. Mathematical Biosciences & Engineering, 2013, 10 (3) : 565-578. doi: 10.3934/mbe.2013.10.565
[2]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[4]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

[5]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389
[6]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[7]

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909
[8]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029
[9]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[10]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
[11]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269
[12]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024
[13]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035
[14]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623
[15]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393
[16]

Brandy Rapatski, James Yorke. Modeling HIV outbreaks: The male to female prevalence ratio in the core population. Mathematical Biosciences & Engineering, 2009, 6 (1) : 135-143. doi: 10.3934/mbe.2009.6.135
[17]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[18]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[19]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075
[20]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences