×

A worst-case analysis of constraint-based algorithms for exact multi-objective combinatorial optimization. (English) Zbl 1454.90074

Mouhoub, Malek (ed.) et al., Advances in artificial intelligence. 30th Canadian conference on artificial intelligence, Canadian AI 2017, Edmonton, AB, Canada, May 16–19, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10233, 117-128 (2017).
Summary: In a multi-objective combinatorial optimization (MOCO) problem, multiple objectives must be optimized simultaneously. In past years, several constraint-based algorithms have been proposed for finding Pareto-optimal solutions to MOCO problems that rely on repeated calls to a constraint solver. Understanding the properties of these algorithms and analyzing their performance is an important problem. Previous work has focused on empirical evaluations on benchmark instances. Such evaluations, while important, have their limitations. Our paper adopts a different, purely theoretical approach, which is based on characterizing the search space into subspaces and analyzing the worst-case performance of a MOCO algorithm in terms of the expected number of calls to the underlying constraint solver. We apply the approach to two important constraint-based MOCO algorithms. Our analysis reveals a deep connection between the search mechanism of a constraint solver and the exploration of the search space of a MOCO problem.
For the entire collection see [Zbl 1361.68011].

MSC:

90C27 Combinatorial optimization
68W40 Analysis of algorithms
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baptiste, P., Le Pape, C., Nuijten, W.: Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer, Dordrecht (2001) · Zbl 1094.90002 · doi:10.1007/978-1-4615-1479-4
[2] Bjørner, N., Phan, A.D.: \( \nu\) Z - maximal satisfaction with Z3. In: Proceedings of the SCSS, pp. 632-647 (2014)
[3] Chakraborty, S., Fremont, D.J., Meel, K.S., Seshia, S.A., Vardi, M.Y.: Distribution-aware sampling and weighted model counting for SAT. In: Proceedings of the AAAI, pp. 1722-1730 (2014)
[4] Chakraborty, S., Meel, K.S., Vardi, M.Y.: A scalable and nearly uniform generator of SAT witnesses. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 608-623. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39799-8_40 · doi:10.1007/978-3-642-39799-8_40
[5] Chakraborty, S., Meel, K.S., Vardi, M.Y.: Balancing scalability and uniformity in sat witness generator. In: Proceedings of the DAC, pp. 1-6 (2014)
[6] Dechter, R., Kask, K., Bin, E., Emek, R.: Generating random solutions for constraint satisfaction problems. In: Proceedings of the AAAI, pp. 15-21 (2002)
[7] Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Heidelberg (2005) · Zbl 1132.90001
[8] Gavanelli, M.: An algorithm for multi-criteria optimization in CSPs. In: Proceedings of the ECAI, pp. 136-140 (2002)
[9] Gomes, C., Selman, B., Kautz, H.: Boosting combinatorial search through randomization. In: Proceedings of the AAAI, pp. 431-437 (1998)
[10] Gomes, C.P., Sabharwal, A., Selman, B.: Near-uniform sampling of combinatorial spaces using XOR constraints. In: Proceedings of the NIPS, pp. 481-488 (2006)
[11] Hartert, R., Schaus, P.: A support-based algorithm for the bi-objective pareto constraint. In: Proceedings of the AAAI, pp. 2674-2679 (2014)
[12] Le Pape, C., Couronné, P., Vergamini, D., Gosselin, V.: Time-versus-capacity compromises in project scheduling. In: Proceedings of the Thirteenth Workshop of the UK Planning Special Interest Group, Strathclyde, UK (1994)
[13] Lukasiewycz, M., Glaß, M., Haubelt, C., Teich, J.: Solving multi-objective Pseudo-Boolean problems. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol. 4501, pp. 56-69. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72788-0_9 · Zbl 1214.90085 · doi:10.1007/978-3-540-72788-0_9
[14] Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998) · Zbl 0944.90066
[15] Rayside, D., Estler, H.C., Jackson, D.: The guided improvement algorithm for exact, general purpose, many-objective combinatorial optimization. Technical report, MIT-CSAIL-TR-2009-033 (2009)
[16] Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, Amsterdam (2006) · Zbl 1175.90011
[17] Sadeh, N., Fox, M.: Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artif. Intell. 86(1), 1-41 (1996) · doi:10.1016/0004-3702(95)00098-4
[18] Spielman, D., Teng, S.H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385-463 (2004) · Zbl 1192.90120 · doi:10.1145/990308.990310
[19] Van Hentenryck, P.: Constraint Satisfaction in Logic Programming. MIT Press, Cambridge (1989)
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.