×

zbMATH — the first resource for mathematics

Improved filtering for the bin-packing with cardinality constraint. (English) Zbl 1402.90144
Summary: Previous research shows that a cardinality reasoning can improve the pruning of the bin-packing constraint. We first introduce a new algorithm, called BPCFlow, that filters both load and cardinality bounds on the bins, using a flow reasoning similar to the Global Cardinality Constraint. Moreover, we detect impossible assignments of items by combining the load and cardinality of the bins, using a method to detect items that are either “too-big” or “too-small”. This method is adapted to two previously existing filtering techniques along with BPCFlow, creating three new propagators. We then experiment the four new algorithms on Balanced Academic Curriculum Problem and Tank Allocation Problem instances. BPCFlow is shown to be stronger than previously existing filtering, and more computationally intensive. We show that the new filtering is useful on a small number of hard instances, while being too expensive for general use. Our results show that the introduced “too-big/too-small” filtering can most of the time drastically reduce the size of the search tree and the computation time. This method is profitable in 88% of the tested instances.
MSC:
90C27 Combinatorial optimization
Software:
OscaR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bessiere, C, Constraint propagation, Foundations of Artificial Intelligence, 2, 29-83, (2006)
[2] Cambazard, H., & O’Sullivan, B. (2010). Propagating the bin packing constraint using linear programming. In Cohen, D. (Ed.) International Conference on Principles and Practice of Constraint Programming (pp. 129-136). Berlin: Springer.
[3] Dupuis, J., Schaus, P., & Deville, Y. (2010). Consistency check for the bin packing constraint revisited. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp. 117-122. Springer. · Zbl 1285.68156
[4] Edmonds, J; Karp, RM, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM (JACM), 19, 248-264, (1972) · Zbl 0318.90024
[5] Ford, L.R., & Fulkerson, D.R. (1955). A simple algorithm for finding maximal network flows and an application to the Hitchcock problem. DTIC Document: Tech. rep. · Zbl 0088.12907
[6] Goldberg, AV; Tarjan, RE, Finding minimum-cost circulations by canceling negative cycles, J. ACM, 36, 873-886, (1989) · Zbl 0697.68063
[7] Labbé, M; Laporte, G; Martello, S, An exact algorithm for the dual bin packing problem, Operations Research Letters, 17, 9-18, (1995) · Zbl 0835.90077
[8] Labbé, M; Laporte, G; Martello, S, Upper bounds and algorithms for the maximum cardinality bin packing problem, European Journal of Operational Research, 149, 490-498, (2003) · Zbl 1033.90108
[9] Lodi, A; Martello, S; Vigo, D, Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics, 123, 379-396, (2002) · Zbl 1022.90020
[10] Martello, S; Toth, P, Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, 28, 59-70, (1990) · Zbl 0704.90074
[11] Martello, S; Vigo, D, Exact solution of the two-dimensional finite bin packing problem, Management science, 44, 388-399, (1998) · Zbl 0989.90114
[12] Mohr, R., & Masini, G. (1988). Good Old Discrete Relaxation. In Kodratoff, Y. (Ed.) 8th European Conference on Artificial Intelligence (ECAI ’88)(pp. 651-656). Munich: Pitmann Publishing. https://hal.inria.fr/inria-00548479 .
[13] Monette, J.-N., Schaus, P., Zampelli, S., Deville, Y., & Dupont, P. (2007). A CP approach to the balanced academic curriculum problem. In Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, vol. 7.
[14] OscaR Team. OscaR: Scala in OR (2012). Available from https://bitbucket.org/oscarlib/oscar.
[15] Pelsser, F., Schaus, P., & Régin, J.-C. (2013). Revisiting the cardinality reasoning for binpacking constraint. In International Conference on Principles and Practice of Constraint Programming, pp. 578-586. Springer.
[16] Rėgin, J., & Rezgui, M. (2011). Discussion about constraint programming bin packing models. In AI for Data Center Management and Cloud Computing, Papers from the 2011 AAAI Workshop, San Francisco, California, USA, August 7, 2011. http://www.aaai.org/ocs/index.php/WS/AAAIW11/paper/view/3817.
[17] Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of the thirteenth national conference on Artificial intelligence-Volume 1, pp. 209-215. AAAI Press.
[18] Schaus, P. (2009). Solving balancing and bin-packing problems with constraint programming. These de doctorat: Université catholique de Louvain.
[19] Schaus, P., Régin, J.-C., Schaeren, R.V., Dullaert, W., & Raa, B. (2012). Cardinality reasoning for bin-packing constraint. application to a tank allocation problem. In International Conference on Principles and Practice of Constraint Programming.
[20] Schaus, P., Régin, J.-C., Van Schaeren, R., Dullaert, W., & Raa, B. (2012). Cardinality reasoning for bin-packing constraint: application to a tank allocation problem. In International Conference on Principles and Practice of Constraint Programming, pp. 815-822. Springer.
[21] Shaw, P. (2004). A constraint for bin packing. In International Conference on Principles and Practice of Constraint Programming, pp. 648-662. Springer. · Zbl 1152.68586
[22] Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2017). How efficient is a global constraint in practice Constraints. · Zbl 1394.90431
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.