×

zbMATH — the first resource for mathematics

A polyhedral approach to the alldifferent system. (English) Zbl 1257.90055
This paper deals with the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The key concept of the analysis is based on a property, called inclusion property, pertinent to such a system. The authors present two families of inequalities and establish that they are facet-defining and completely describe the convex hull of an alldifferent system bearing the inclusion property. It is shown that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Under a technical condition, the reverse direction of this statement (i.e., if the convex hull is described by these families of inequalities then the inclusion property holds) is established for systems consisting of three predicates. For the systems for which the inclusion property does not hold, the authors have established another family of facet-defining inequalities and described a separation algorithm of polynomial complexity. All the separation algorithms are incorporated within a cutting-plane scheme. Experimentation, on a set of randomly generated alldifferent systems, has produced encouraging results as the integrality gap in most cases was considerably reduced.

MSC:
90C10 Integer programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
CPLEX; Mosel; SCIP; SIMPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.: SCIP–a Framework to Integrate Constraint and Mixed Integer Programming. http://www.zib.de/Publications/Reports/ZR-04-19.pdf (2004)
[2] Appa, G., Magos, D., Mourtos, I.: LP relaxations of multiple all_different predicates. In: Régin, J., Rueher, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization problems. 1st International Conference CPAIOR 2004, Nice, France, Lecturer Notes in Computer Science, vol. 3011, pp. 21–36 (2004)
[3] Appa G., Magos D., Mourtos I.: On the system of two alldifferent predicates. Inf. Process. Lett. 94, 99–105 (2005) · Zbl 1182.68141 · doi:10.1016/j.ipl.2005.01.009
[4] Aron, I.D., Hooker, J.N., Yunes, T.H.: SIMPL: A system for integrating optimization techniques. In: Régin, J., Rueher, M., (eds.) Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization problems. 1st International Conference CPAIOR 2004, Nice, France, Lecturer Notes in Computer Science, vol. 3011, pp. 21–36 (2004) · Zbl 1094.68636
[5] Aron, I.D., Leventhal, D.H. Sellmann, M.: A Totally Unimodular Description of the Consistent Value Polytope for Binary Constraint Programming. In: Beck, J.C., Smith, B.M. (eds.) Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization problems. 3rd International Conference CPAIOR 2006, Cork, Ireland. Lecturer Notes in Computer Science, vol. 3990, pp. 16–28 (2006) · Zbl 1177.68181
[6] Balas E., Bockmayr A., Pisaruk N., Wolsey L.: On unions and dominants of polytopes. Math. program. 99, 223–239 (2004) · Zbl 1098.90092 · doi:10.1007/s10107-003-0432-4
[7] Chaitin G.J., Auslander M., Chandra A.K., Cocke J., Hopkins M.E., Markstein P.: Register allocation via coloring. Comput. Lang. 6, 47–57 (1981) · doi:10.1016/0096-0551(81)90048-5
[8] Colombani, Y. Heipcke, S.: Mosel: An Overview. Dash Optimization (2002) · Zbl 1097.90036
[9] Elbassioni, K., Katriel, I., Kutz, M., Mahajan, M.: Simultaneous matchings. In: Deng, X., Du, D., (eds.) Algorithms and Computation. 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, Lecturer Notes in Computer Science, vol. 3827, pp. 106–115 (2005) · Zbl 1144.68336
[10] Gomes, C.P., Shmoys, D.: The promise of LP to boost CSP techniques for combinatorial problems. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization problems. 4th International Workshop CPAIOR 2002, Le Croisic, France, pp. 291–305 (2002)
[11] Grötschel M., Lovász L., Schrijver A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981) · Zbl 0492.90056 · doi:10.1007/BF02579273
[12] Hooker J.N.: Logic-Based Methods for Optimization. Wiley InterScience, New York (2000) · Zbl 0974.90001
[13] Hooker, J.N.: A search-infer-and-relax framework for integrating solution methods. In: Bartak, R., Milano, M., (eds.) Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization problems. 2nd International Conference CPAIOR 2005, Prague, Czech Republic, Lecturer Notes in Computer Science, vol. 3524, pp. 243–257 (2005)
[14] Hooker J.N.: Logic-based modeling. In: Appa, G., Pitsoulis, L., Williams, H.P. (eds) Handbook on modelling for Discrete Optimization, International Series in Operations Research Management & Science, Springer, New York (2006)
[15] Hooker J.N.: Integrated methods for optimization, International Series in Operations Research & Management Science. Springer, New York (2007)
[16] Hooker J.N., Osorio M.A.: Mixed logical-linear programming. Discret. Appl. Math. 96(97), 395–442 (1999) · Zbl 0945.90031 · doi:10.1016/S0166-218X(99)00100-6
[17] Hooker, J.N., Yan, H.: A relaxation of the cumulative constraint. In: van Hentenryck, P. (ed.) Principles and Practice of Constraint Programming, 8th International Conference, CP2002, Ithaka, NY, Lecturer Notes in Computer Science, vol. 2470, pp. 80–92 (2002)
[18] ILOG S.A., ILOG CPLEX Callable Library 9.1 (2005)
[19] Kaya, L.G., Hooker, J.N.: The circuit polytope. http://wpweb2.tepper.cmu.edu/jnh/CircuitPolytope.pdf
[20] Kaznachey D., Jagota A., Das S.: Neural network-based heuristic algorithms for hypergraph coloring problems with applications. J. Parallel Distrib. Comput. 63, 786–800 (2003) · Zbl 1047.68092 · doi:10.1016/S0743-7315(03)00064-9
[21] Lee J.: All-different polytopes. J. Comb. Opt. 6, 335–352 (2002) · Zbl 1007.90041 · doi:10.1023/A:1014804110661
[22] Milano M., Ottosson G., Refalo P., Thorsteinsson E.: The role of integer programming techniques in constraint programming’s global constraints. Inf. J. Comput. 14(4), 387–402 (2002) · Zbl 1238.90101 · doi:10.1287/ijoc.14.4.387.2830
[23] Mirsky, L.: Transversal theory, Mathematics Science and Engineering. vol. 75, Academic Press, London (1971) · Zbl 0282.05001
[24] Refalo, P.: Linear formulation of constraint programming models and hybrid solvers. In: Dechter, R. (ed.) Principles and Practice of Constraint Programming, 6th International Conference, CP 2000, Singapore, Lecturer Notes in Computer Science, vol. 1894, pp. 369–383 (2000) · Zbl 1044.68792
[25] Régin J.C.: Cost-based arc consistency for global cardinality constraints. Constraints 7, 387–405 (2002) · Zbl 1028.68157 · doi:10.1023/A:1020506526052
[26] Régin, J.C., Gomes, C.P.: The cardinality matrix constraint. In: Wallace, M. (ed.) Principles and Practice of Constraint Programming, 10th International Conference, CP 2006, Toronto, Lecturer Notes in Computer Science, vol. 3258, pp. 572–587 (2004) · Zbl 1152.68578
[27] Sellmann, M., Mercier, L., Leventhal, D.H.: The linear programming polytope of binary constraint problems with bounded tree-width. In: Van Hentenryck, P., Wolsey, L. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization problems. 4th International Conference CPAIOR 2007, Brussels, Belgium. Lecturer Notes in Computer Science, vol. 4510, pp. 275–287 (2007) · Zbl 1214.90105
[28] van Hentenryck P.: The OPL Optimization Programming Language. MIT Press, Boston (1999)
[29] van Hoeve, W.J.: The Alldifferent constraint: A survey. Sixth Annual Workshop of the ERCIM Working Group on Constraints, Prague (2001)
[30] Williams H.P., Yan H.: Representations of the all-different predicate of constraint satisfaction in integer programming. Inf. J. Comput. 13, 96–103 (2001) · Zbl 1238.90103 · doi:10.1287/ijoc.13.2.96.10515
[31] Yan H., Hooker J.N.: Tight representation of logic constraints as cardinality rules. Math. Program. 85, 363–377 (1999) · Zbl 0954.90043 · doi:10.1007/s101070050061
[32] Yunes, T.H.: On the sum constraint: relaxation and applications. In: van Hentenryck, P. (ed.) Principles and Practice of Constraint Programming, 8th International Conference, CP2002, Ithaka, NY, Lecturer Notes in Computer Science, vol. 2470, pp. 80–92 (2002)
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.