A Study of Operations Research Solutions Techniques in Combinatorial Problem towards Constraint Programming
DOI:
https://doi.org/10.29070/a7jrwd15Keywords:
Operations research, Solutions techniques, Combinatorial problem, Constraint programming, Numerical identities, Formal representation, Sigma notation, Operational properties, Algebraic properties, Combinatorial argumentsAbstract
Many numerical identities are proved applying clever but informal combinatorial arguments. A formal representation is presented to prove these identities closely following these arguments. The main formal tool used to that end is, operationally, an abstract and axiomatic generalization of the Sigma notation (Σ), which is utilized for expressing and manipulating summations and counts. Operational properties are provided with algebraic properties that make it possible to perform different naturally important operations. In this paper we present a formal version and some more examples that show how to practically interpret combinatorial arguments used in literature. We present typical combinatorial evidence of the inclusion-exclusion theorem. Combinatory evidence of numerical identity is either that both sides of the given equation count the very same kinds of objects in two different ways or show a bijection between the sets that show up on each side of the equation. The two expressions must therefore be the same. The dream most combinatorialists make when they prove their identity is this kind of argument. Such arguments are generally informal and, it is likely to be safe to say, ad hoc, without a unified formal basis.Downloads
References
Achterberg, T. (2016): SCIP: Solving constraint integer programs. Mathematical Programming Computation 1, pp. 1–41.
Aggoun, A., Beldiceanu, N. (2014): Extending CHIP in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling 17, pp. 57–73
Ahuja, R.K., Magnanti, T.L., Orlin, J.B. (2017): Linear Programming and Network Flows, 3rd ed. Prentice-Hall, Upper Saddle River, NJ
Althaus, E., Bockmayr, A., Elf, M., Kasper, T., J¨uenger, M., Mehlhorn, K. (2012): SCIL— Symbolic constraints in integer linear programming. In: 10th European symposium on Algorithms, Lecture Notes in Computer Science, vol. 2461, pp. 75–87. Springer
Andersen, H.R. (2017): An introduction to binary decision diagrams. Lecture notes, available online, IT University of Copenhagen
Andersen, H.R., Hadˇzi´c, T., Hooker, J.N., Tiedemann, P. (2017): A constraint store based on multivalued decision diagrams. In: C. Bessiere (ed.) Principles and Practice of Constraint Programming (CP 2017), Lecture Notes in Computer Science, vol. 4741, pp. 118–132. Springer
Appa, G., Magos, D., Mourtos, I. (2015): A polyhedral approach to the alldifferent system. Mathematical Programming 124, pp. 1–52
Appa, G., Mourtos, I., Magos, D. (2012): Integrating constraint and integer programming for the orthogonal Latin squares problem. In: P. Van Hentenryck (ed.) Principles and Practice of Constraint Programming (CP 2012), Lecture Notes in Computer Science, vol. 2470, pp. 17–32. Springer
Aron, I., Hooker, J.N., Yunes, T.H. (2014): SIMPL: A system for integrating optimization techniques. In: J.C. R´egin, M. Rueher (eds.) CPAIOR Proceedings, Lecture Notes in Computer Science, vol. 3011, pp. 21–36. Springer .
Bacchus, F., Dalmao, S., Pitassi, T. (2014): Relaxation search: A simple way of managing optional clauses. In: AAAI Conference on Artificial Intelligence, pp. 835–841
Bajestani, M.A., Beck, J.C. (2016): Scheduling a dynamic aircraft repair shop with limited repair resources. Journal of Artificial Intelligence Research 47, pp. 35–70
Bajgiran, O., Cire, A., Rousseau, L.M. (2017): A first look at picking dual variables for maximizing reduced-cost based fixing. In: M. Lombardi, D. Salvagnin (eds.) CPAIOR Proceedings, Lecture Notes in Computer Science, vol. 10335, pp. 221–228. Springer
This work is licensed under a 