Abstract
Online optimization approaches are popular for solving optimization problems where not all data is considered at once, because it is computationally prohibitive, or because new data arrives in an ongoing fashion. Online approaches solve the problem iteratively, with the amount of data growing in each iteration. Over time, many problem variables progressively become realized, i.e., their values were fixed in the past iterations and they can no longer affect the solution. If the solving approach does not remove these realized variables and associated data and simplify the corresponding constraints, solving performance will slow down significantly over time. Unfortunately, simply removing realized variables can be incorrect, as they might affect unrealized decisions. This is why this complex task is currently performed manually in a problem-specific and time-consuming way. We propose a problem-independent framework to identify realized data and decisions, and remove them by summarizing their effect on future iterations in a compact way. The result is a substantially improved model performance.
Partly funded by Australian Research Council grant DP180100151.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barták, R.: Dynamic global constraints in backtracking based environments. Ann. Oper. Res. 118, 101–119 (2003). https://doi.org/10.1023/A:1021805623454
Bent, R., Van Hentenryck, P.: Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper. Res. 52(6), 977–987 (2004)
Bent, R., Van Hentenryck, P.: Online stochastic optimization without distributions. In: ICAPS 2005, pp. 171–180 (2005)
Brown, K.N., Miguel, I.: Uncertainty and change. In: Handbook of Constraint Programming, pp. 731–760. Elsevier (2006). (Chap. 21)
Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1(3/4), 197–206 (1955)
Dechter, R., Dechter, A.: Belief maintenance in dynamic constraint networks. In: AAAI 1988, pp. 37–42. AAAI Press, June 1988
Ek, A., Garcia de la Banda, M., Schutt, A., Stuckey, P.J., Tack, G.: Modelling and solving online optimisation problems. In: AAAI 2020, pp. 1477–1485. AAAI Press (2020)
Faltings, B., Macho-Gonzalez, S.: Open constraint programming. Artif. Intell. 161(1–2), 181–208 (2005)
Gecode Team. Gecode: A generic constraint development environment (2020). http://www.gecode.org
Graham, R.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563–1581 (1966)
Jaillet, P., Wagner, M.R.: Online vehicle routing problems: a survey. In: Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, vol. 43, pp. 221–237. Springer, Boston (2008). https://doi.org/10.1007/978-0-387-77778-8_10
Jones, R.E., Hosking, A.L., Moss, J.E.B.: The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman and Hall/CRC Applied Algorithms and Data Structures Series. CRC Press, Boca Raton (2011)
Mears, C., Garcia de la Banda, M., Wallace, M., Demoen, B.: A method for detecting symmetries in constraint models and its generalisation. Constraints 20(2), 235–273 (2014). https://doi.org/10.1007/s10601-014-9175-5
Metodi, A., Codish, M., Stuckey, P.J.: Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems. J. Artif. Intell. Res. 46, 303–341 (2013)
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_38
Pruhs, K., Sgall, J., Torng, E.: Online scheduling. In: Handbook of Scheduling - Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC (2004)
Roelofs, M., Bisschop, J.: Time-based modelling. In: AIMMS: The Language Reference, May 2, 2019 edn. (2019). www.aimms.com. (Chap. 33)
Schulte, C., Stuckey, P.J.: Dynamic variable elimination during propagation solving. In: Antoy, S., Albert, E. (eds.) Proceedings of the 10th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, Valencia, Spain, 15–17 July 2008, pp. 247–257. ACM (2008)
Sethi, S., Soerger, G.: A theory of rolling horizon decision making. Ann. Oper. Res. 29, 387–415 (1991). https://doi.org/10.1007/BF02283607
Van Hentenryck, P., Bent, R.: Online Stochastic Combinatorial Optimization. MIT Press, Cambridge (2009)
Verfaillie, G., Jussien, N.: Constraint solving in uncertain and dynamic environments: a survey. Constraints 10(3), 253–281 (2005). https://doi.org/10.1007/s10601-005-2239-9
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ek, A., Garcia de la Banda, M., Schutt, A., Stuckey, P.J., Tack, G. (2020). Aggregation and Garbage Collection for Online Optimization. In: Simonis, H. (eds) Principles and Practice of Constraint Programming. CP 2020. Lecture Notes in Computer Science(), vol 12333. Springer, Cham. https://doi.org/10.1007/978-3-030-58475-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-58475-7_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58474-0
Online ISBN: 978-3-030-58475-7
eBook Packages: Computer ScienceComputer Science (R0)