A Lagrangian propagator for artificial neural networks in constraint programming.

*(English)*Zbl 1368.90148Summary: This paper discusses a new method to perform propagation over a (two-layer, feed-forward) Neural Network embedded in a Constraint Programming model. The method is meant to be employed in Empirical Model Learning, a technique designed to enable optimal decision making over systems that cannot be modeled via conventional declarative means. The key step in Empirical Model Learning is to embed a Machine Learning model into a combinatorial model. It has been showed that Neural Networks can be embedded in a Constraint Programming model by simply encoding each neuron as a global constraint, which is then propagated individually. Unfortunately, this decomposition approach may lead to weak bounds. To overcome such limitation, we propose a new network-level propagator based on a non-linear Lagrangian relaxation that is solved with a subgradient algorithm. The method proved capable of dramatically reducing the search tree size on a thermal-aware dispatching problem on multicore CPUs. The overhead for
optimizing the Lagrangian multipliers is kept within a reasonable level via a few simple techniques. This paper is an extended version of the authors [“A new propagator for two-layer neural networks in empirical model learning”, Lect. Notes Comput. Sci. 8124, 448–463 (2013; doi:10.1007/978-3-642-40627-0_35)], featuring an improved structure, a new filtering technique for the network inputs, a set of overhead reduction techniques, and a thorough experimentation.

##### Software:

Paramils
PDF
BibTeX
XML
Cite

\textit{M. Lombardi} and \textit{S. Gualandi}, Constraints 21, No. 4, 435--462 (2016; Zbl 1368.90148)

Full Text:
DOI

##### References:

[1] | Audet, C. (2014). A survey on direct search methods for blackbox optimization and their applications. In Mathematics Without Boundaries (pp. 31-56): Springer. · Zbl 1321.90125 |

[2] | Bartolini, A., Lombardi, M., Milano, M., & Benini, L. (2011). Neuron Constraints to Model Complex Real-World Problems. In Proc. of CP (pp. 115-129). |

[3] | Bartolini, A., Lombardi, M., Milano, M., & Benini, L. (2012). Optimization and Controlled Systems: A Case Study on Thermal Aware Workload Dispatching. Proc. of AAAI. |

[4] | Basheer, IA; Hajmeer, M, Artificial neural networks: fundamentals, computing, design, and application, Journal of Microbiological Methods, 43, 3-31, (2000) |

[5] | Belew, R.K., McInerney, J., & Schraudolph, N.N. (1991). Evolving networks: Using the genetic algorithm with connectionist learning. Proc. of Artificial Life, 511-547. |

[6] | Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24, 597-634, (2009) · Zbl 1179.90237 |

[7] | Bergman, D; Cirė, AA; van Hoeve, W-J, Lagrangian bounds from decision diagrams, Constraints, 20, 346-361, (2015) · Zbl 1327.90116 |

[8] | Bonfietti, A., & Lombardi, M. (2012). The weighted average constraint. In Proc. of CP (pp. 191-206): Springer. |

[9] | Bonfietti, A., Lombardi, M., & Milano, M. (2015). Embedding decision trees and random forests in constraint programming. In Proc. of CPAIOR (pp. 74-90). · Zbl 06605749 |

[10] | Cambazard, H; Fages, J-G, New filtering for atmostnvalue and its weighted variant: A Lagrangian approach, Constraints, 20, 362-380, (2015) · Zbl 1327.90130 |

[11] | Chow, TT; Zhang, GQ; Lin, Z; Song, CL, Global optimization of absorption chiller system by genetic algorithm and neural network, Energy and Buildings, 34, 103-109, (2002) |

[12] | Conn, A.R., Scheinberg, K., & Vicente, L.N. (2009). Introduction To Derivative-free Optimization, volume 8. Siam. · Zbl 1163.49001 |

[13] | d’Antonio, G; Frangioni, A, Convergence analysis of deflected conditional approximate subgradient methods, SIAM Journal on Optimization, 20, 357-386, (2009) · Zbl 1187.90222 |

[14] | Focacci, F., Lodi, A., & Milano, M. (1999). Cost-based domain filtering. · Zbl 1327.90116 |

[15] | Ge, S.S., Hang, C.C., Lee, T.H., & Zhang, T. (2010). Stable adaptive neural network control. Springer Publishing Company, Incorporated. · Zbl 1001.93002 |

[16] | Gent, I.P., Kotthoff, L., Miguel, I., & Nightingale, P. (2010). Machine learning for constraint solver design - A case study for the alldifferent constraint. CoRR, abs/1008.4326. |

[17] | Glover, F., Kelly, J.P., & Laguna, M. (1999). New Advances for Wedding optimization and simulation. In Proc. of WSC. IEEE (pp. 255-260). |

[18] | Gopalakrishnan, K; Asce, AM, Neural network swarm intelligence hybrid nonlinear optimization algorithm for pavement moduli back-calculation, Journal of Transportation Engineering, 136, 528-536, (2009) |

[19] | Gualandi, S., & Malucelli, F. (2012). Resource constrained shortest paths with a super additive objective function. In Proc. of CP (pp. 299-315): Springer. |

[20] | Howard, J; Dighe, S; Vangal, SR; Ruhl, G; Borkar, N; Jain, S; Erraguntla, V; Konow, M; Riepen, M; Gries, M; etal., A 48-core ia-32 processor in 45 nm cmos using on-die message-passing and dvfs for performance and power scaling, IEEE Journal of Solid-State Circuits, 46, 173-183, (2011) |

[21] | Huang, W; Ghosh, S; Velusamy, S, Hotspot: A compact thermal modeling methodology for early-stage VLSI design, IEEE Transactions on VLSI, 14, 501-513, (2006) |

[22] | Hutter, F; Hoos, HH; Leyton-Brown, K; Stu̇tzle, T, Paramils: an automatic algorithm configuration framework, Journal of Artificial Intelligence Research, 36, 267-306, (2009) · Zbl 1192.68831 |

[23] | Jayaseelan, R., & Mitra, T. (2009). A hybrid local-global approach for multi-core thermal management. In Proc. of ICCAD (pp. 314-320): ACM Press. |

[24] | Kiranyaz, S; Ince, T; Yildirim, A; Gabbouj, M, Evolutionary artificial neural networks by multi-dimensional particle swarm optimization, Neural Networks, 22, 1448-1462, (2009) |

[25] | Lemaréchal, C. (2001). Lagrangian relaxation. In Computational Combinatorial Optimization (pp. 112-156): Springer. |

[26] | Ljung, L. (1999). System identification. Wiley Online Library. · Zbl 0949.93509 |

[27] | Lombardi, M., & Gualandi, S. (2013). A new propagator for two-layer neural networks in empirical model learning. In Proc. of CP (pp. 448-463). |

[28] | Montana, D.J., & Davis, L. (1989). Training feedforward neural networks using genetic algorithms. In Proc. of IJCAI (pp. 762-767). · Zbl 0709.68060 |

[29] | Moore, J., Chase, J.S., & Ranganathan, P. (2006). Weatherman: Automated, Online and Predictive Thermal Mapping and Management for Data Centers. In Proc. of ICAC. IEEE (pp. 155-164). |

[30] | Moré, J.J. (1978). The Levenberg-Marquardt algorithm: implementation and theory. In Numerical analysis (pp. 105-116): Springer. |

[31] | Queipo, NV; Haftka, RT; Shyy, W; Goel, T; Vaidyanathan, R; Tucker, PK, Surrogate-based analysis and optimization, Progress In Aerospace Sciences, 41, 1-28, (2005) |

[32] | Sellmann, M. (2004). Theoretical foundations of cp-based lagrangian relaxation. In Proc. of CP (pp. 634-647): Springer. · Zbl 1152.68584 |

[33] | Sellmann, M; Fahle, T, Constraint programming based Lagrangian relaxation for the automatic recording problem, Annals of Operations Research, 118, 17-33, (2003) · Zbl 1026.90510 |

[34] | Slusky, M.R., & van Hoeve, W.J. (2013). A lagrangian relaxation for golomb rulers. In Proc. of CPAIOR (pp. 251-267): Springer. · Zbl 1382.68233 |

[35] | Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2015). Understanding the potential of propagators. In Proc. of CPAIOR (pp. 427-436). · Zbl 06605772 |

[36] | Zhang, G; Patuwo, BE; Hu, MY, Forecasting with artificial neural networks: the state of the art, International Journal of Forecasting, 14, 35-62, (1998) |

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.