Ellipsoidal one-class constraint acquisition for quadratically constrained programming. (English) Zbl 1487.90489
Summary: We propose Ellipsoidal One-Class Constraint Acquisition (EOCCA), a fast and scalable algorithm for the acquisition of constraints for Mixed-Integer Quadratically Constrained Programming (MIQCP) models from data. EOCCA acquires a well-formed MIQCP model using solely the examples of the feasible solutions to this model. It combines x-means partitioning, standardization, and principal components analysis to preprocess the training set and then wraps the preprocessed data into several hyper-ellipsoids expressed using MIQCP constraints. These MIQCP constraints are projected back to the space of the original training set, and their further use does not require data preprocessing. Experimental evaluation shows that EOCCA scores better than a state-of-the-art algorithm in terms of fidelity of the acquired constraints to ground-truth constraints and achieves this in few orders of magnitude shorter time. We demonstrate the practical use case of EOCCA in a fully automated workflow of modeling and optimization of a rice farm using real-world data.
MSC:
| 90C11 | Mixed integer programming |
| 90C20 | Quadratic programming |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
artificial intelligence; quadratic programming; system modeling; process mining; business processReferences:
| [1] | Ahuja, R. K.; Orlin, J. B., Inverse optimization, Operations Research, 49, 5, 771-783 (2001) · Zbl 1163.90764 |
| [2] | http://slideplayer.com/slide/7976536/ |
| [3] | Barrett, C.; Sebastiani, R.; Seshia, S.; Tinelli, C., Satisfiability modulo theories, (vol.185, 825-885) (2009), IOS Press |
| [4] | Beldiceanu, N.; Simonis, H., A model seeker: Extracting global constraint models from positive examples, CP’12, LNCS 7514, 141-157 (2012), Springer: Springer Quebec City, Canada |
| [5] | Bellman, R., Dynamic programming, Dover Books on Computer Science (2013), Dover Publications · Zbl 0208.17501 |
| [6] | Bessiere, C.; Coletta, R.; Hebrard, E.; Katsirelos, G.; Lazaar, N.; Narodytska, N.; Walsh, T., Constraint acquisition via partial queries, IJCAI 2013, 475-481 (2013) |
| [7] | Bessiere, C.; Coletta, R.; Koriche, F.; O’Sullivan, B., A SAT-based version space algorithm for acquiring constraint satisfaction problems, (Gama, J.; Camacho, R.; Brazdil, P. B.; Jorge, A. M.; Torgo, L. (2005), Springer Berlin Heidelberg), 23-34) |
| [8] | Bessiere, C.; Coletta, R.; O’Sullivan, B.; Paulin, M., Query-driven constraint acquisition, Proceedings of the IJCAI 2007, 50-55 (2007) |
| [9] | Beyer, H.-G.; Schwefel, H.-P., Evolution strategies – a comprehensive introduction, Natural Computing, 1, 1, 3-52 (2002) · Zbl 1014.68134 |
| [10] | Bishop, C. M., Pattern recognition and machine learning (Information Science and Statistics) (2006), Springer-Verlag New York, Inc. · Zbl 1107.68072 |
| [11] | Blonder, B.; Lamanna, C.; Violle, C.; Enquist, B. J., The n-dimensional hypervolume, Global Ecology and Biogeography, 23, 595-609 (2014) |
| [12] | Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press · Zbl 1058.90049 |
| [13] | Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete & Computational Geometry, 10, 4, 377-409 (1993) · Zbl 0786.68091 |
| [14] | https://esajournals.onlinelibrary.wiley.com/doi/10.1890/0012-9658 |
| [15] | Cortes, C.; Vapnik, V., Support-vector networks, Machine Learning, 20, 3, 273-297 (1995) · Zbl 0831.68098 |
| [16] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002) |
| [17] | Epanechnikov, V. A., Non-parametric estimation of a multivariate probability density, Theory of Probability & Its Applications, 14, 1, 153-158 (1969) |
| [18] | Feng, Q.; Horrace, W. C., Alternative technical efficiency measures: Skew, bias and scale, Journal of Applied Econometrics, 27, 2, 253-268 (2012) |
| [19] | Flach, P., Machine learning: The art and science of algorithms that make sense of data (2012), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 1267.68010 |
| [20] | Fourer, R.; Gay, D.; Kernighan, B., AMPL: A modeling language for mathematical programming, Scientific Press series (2003), Thomson/Brooks/Cole |
| [21] | Gurobi Optimization, LLC (2018). Gurobi optimizer reference manual. http://www.gurobi.com. |
| [22] | Haykin, S., Neural networks: A comprehensive foundation (1998), Prentice Hall PTR: Prentice Hall PTR Upper Saddle River, NJ, USA · Zbl 0934.68076 |
| [23] | Kanji, G., 100 Statistical tests (1999), SAGE Publications |
| [24] | Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-395 (1984) · Zbl 0557.90065 |
| [25] | Karmelita, M.; Pawlak, T. P., CMA-ES for one-class constraint synthesis, Proceedings of the 2020 genetic and evolutionary computation conference. Proceedings of the 2020 genetic and evolutionary computation conference, GECCO ’20, 859-867 (2020), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA |
| [26] | Khan, S. S.; Madden, M. G., One-class classification: Taxonomy of study and review of techniques, The Knowledge engineering review, 29, 3, 345-374 (2014) |
| [27] | Kolb, S.; Teso, S.; Passerini, A.; Raedt, L. D., Learning SMT(LRA) constraints using SMT solvers, Proceedings of the twenty-seventh international joint conference on artificial intelligence, IJCAI-18, 2333-2340 (2018), International Joint Conferences on Artificial Intelligence Organization |
| [28] | Kudła, P.; Pawlak, T. P., One-class synthesis of constraints for mixed-integer linear programming with C4.5 decision trees, Applied Soft Computing, 68, 1-12 (2018) |
| [29] | Lance, G. N.; Williams, W. T., Mixed-data classificatory programs i - agglomerative systems, Australian Computer Journal, 1, 1, 15-20 (1967) |
| [30] | Leemans, S. J.J.; Fahland, D.; van der Aalst, W. M.P., Scalable process discovery with guarantees, (Gaaloul, K.; Schmidt, R.; Nurcan, S.; Guerreiro, S.; Ma, Q., Enterprise, business-process and information systems modeling (2015), Springer International Publishing: Springer International Publishing Cham), 85-101 |
| [31] | Lombardi, M.; Milano, M.; Bartolini, A., Empirical decision model learning, Artificial Intelligence, 244, Supplement C, 343-367 (2017) · Zbl 1404.68113 |
| [32] | Manevitz, L. M.; Yousef, M., One-class SVMs for document classification, Journal of Machine Learning Research : JMLR, 2, 139-154 (2002) · Zbl 1002.68597 |
| [33] | Mayoh, B.; Tyugu, E.; Penjam, J., Constraint programming, Nato ASI Subseries F: (2013), Springer |
| [34] | Mitchell, T. M., Generalization as search, Artificial Intelligence, 18, 2, 203-226 (1982) |
| [35] | Montana, D. J., Strongly typed genetic programming, Evolutionary Computation, 3, 2, 199-230 (1995) |
| [36] | Novikov, A., PyClustering: Data mining library, Journal of Open Source Software, 4, 36, 1230 (2019) |
| [37] | Pawlak, T. P., Performance improvements for evolutionary strategy-based one-class constraint synthesis, Proceedings of the genetic and evolutionary computation conference. Proceedings of the genetic and evolutionary computation conference, GECCO ’18, 873-880 (2018), ACM: ACM New York, NY, USA |
| [38] | Pawlak, T. P., Synthesis of mathematical programming models with one-class evolutionary strategies, Swarm and Evolutionary Computation, 44, 335-348 (2019) |
| [39] | Pawlak, T. P.; Krawiec, K., Automatic synthesis of constraints from examples using mixed integer linear programming, European Journal of Operational Research, 261, 3, 1141-1157 (2017) · Zbl 1403.90527 |
| [40] | Pawlak, T. P.; Krawiec, K., Synthesis of mathematical programming constraints with genetic programming, Proceedings of the 20th European Conference on Genetic Programming, EUROGP 2017. Proceedings of the 20th European Conference on Genetic Programming, EUROGP 2017, LNCS, 10196, 178-193 (2017), Springer Verlag: Springer Verlag Amsterdam |
| [41] | Pawlak, T. P.; Krawiec, K., Synthesis of constraints for mathematical programming with one-class genetic programming, IEEE Transactions on Evolutionary Computation, 23, 1, 117-129 (2019) |
| [42] | Pelleg, D.; Moore, A., X-means: Extending k-means with efficient estimation of the number of clusters, Proceedings of the 17th international conference on machine learning, 727-734 (2000), Morgan Kaufmann |
| [43] | Quinlan, J. R., C4.5: Programs for machine learning (1993), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA |
| [44] | Schólkopf, B.; Williamson, R. C.; Smola, A.; Shawe-Taylor, J., SV estimation of a distribution’s support, Proceedings of the Advances in neural information processing systems 1999 (1999) |
| [45] | Shchekotykhin, K. M.; Friedrich, G., Argumentation based constraint acquisition, Proceedings of the, the ninth IEEE international conference on data mining, ICDM 2009, Miami, Florida, usa, 6-9 December 2009, 476-482 (2009) |
| [46] | Simonoff, J., Smoothing methods in statistics, Springer Series in Statistics (1996), Springer · Zbl 0859.62035 |
| [47] | Souza, C. R. (2017). The Accord.NET Framework. http://accord-framework.net. |
| [48] | Sroka, D.; Pawlak, T. P., One-class constraint acquisition with local search, Proceedings of the genetic and evolutionary computation conference. Proceedings of the genetic and evolutionary computation conference, GECCO ’18, 363-370 (2018), ACM: ACM New York, NY, USA |
| [49] | Tax, D. M.J., One-class classification: Concept-learning in the absence of counter-examples (2001), Delft University of Technology, Ph.D. thesis. |
| [50] | Teso, S.; Sebastiani, R.; Passerini, A., Structured learning modulo theories, Artificial Intelligence, 244, 166-187 (2017) · Zbl 1404.68121 |
| [51] | van der Aalst, W.; Weijter, A.; Maruster, L., Workflow mining: Discovering process models from event logs, IEEE Transactions on Knowledge and Data Engineering, 16, 2004 (2003) |
| [52] | van der Aalst, W. M.P., Process mining: Data science in action (2016), Springer: Springer Heidelberg |
| [53] | Weijters, A. J.M. M.; Ribeiro, J. T.S., Flexible heuristics miner (FHM), Proceedings of the IEEE symposium on computational intelligence and data mining (CIDM), 2011, 310-317 (2010) |
| [54] | Williams, H., Model building in mathematical programming (2013), Wiley · Zbl 1261.90003 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
