American Institute of Mathematical Sciences

• 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

 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.
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:

show all references

References:
 [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