Document Open Access Logo

Human-Centred Feasibility Restoration

Authors Ilankaikone Senthooran , Matthias Klapperstueck , Gleb Belov , Tobias Czauderna , Kevin Leo , Mark Wallace , Michael Wybrow , Maria Garcia de la Banda

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.49.pdf
  • Filesize: 1.81 MB
  • 18 pages

Document Identifiers

Author Details

Ilankaikone Senthooran
  • Data Science & AI, Monash University, Clayton, Australia
Matthias Klapperstueck
  • Human-Centred Computing, Monash University, Clayton, Australia
Gleb Belov
  • Data Science & AI, Monash University, Clayton, Australia
Tobias Czauderna
  • Human-Centred Computing, Monash University, Clayton, Australia
Kevin Leo
  • Data Science & AI, Monash University, Clayton, Australia
Mark Wallace
  • Data Science & AI, Monash University, Clayton, Australia
Michael Wybrow
  • Human-Centred Computing, Monash University, Clayton, Australia
Maria Garcia de la Banda
  • Data Science & AI, Monash University, Clayton, Australia

Funding

Partly by Australian Research Council grant DP180100151 and Woodside Energy Ltd.

Cite AsGet BibTex

Ilankaikone Senthooran, Matthias Klapperstueck, Gleb Belov, Tobias Czauderna, Kevin Leo, Mark Wallace, Michael Wybrow, and Maria Garcia de la Banda. Human-Centred Feasibility Restoration. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.49

Abstract

Decision systems for solving real-world combinatorial problems must be able to report infeasibility in such a way that users can understand the reasons behind it, and understand how to modify the problem to restore feasibility. Current methods mainly focus on reporting one or more subsets of the problem constraints that cause infeasibility. Methods that also show users how to restore feasibility tend to be less flexible and/or problem-dependent. We describe a problem-independent approach to feasibility restoration that combines existing techniques from the literature in novel ways to yield meaningful, useful, practical and flexible user support. We evaluate the resulting framework on two real-world applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Theory of computation → Integer programming
Keywords
  • Combinatorial optimisation
  • modelling
  • human-centred
  • conflict resolution
  • feasibility restoration
  • explainable AI
  • soft constraints

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Fahiem Bacchus and George Katsirelos. Using minimal correction sets to more efficiently compute minimal unsatisfiable sets. In International Conference on Computer Aided Verification, pages 70-86. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21668-3_5.
  2. Gleb Belov, Tobias Czauderna, Maria Garcia de la Banda, Matthias Klapperstueck, Ilankaikone Senthooran, Mitch Smith, Michael Wybrow, and Mark Wallace. Process Plant Layout Optimization: Equipment Allocation. In John Hooker, editor, Principles and Practice of Constraint Programming, pages 473-489. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98334-9_31.
  3. Gleb Belov, Peter J. Stuckey, Guido Tack, and Mark Wallace. Improved Linearization of Constraint Programming Models. In Michel Rueher, editor, Principles and Practice of Constraint Programming, pages 49-65. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-44953-1_4.
  4. Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, and Philippe David. Interactively solving school timetabling problems using extensions of constraint programming. In PATAT 2004, volume 3616 of LNCS, pages 190-207, 2004. URL: https://doi.org/10.1007/11593577_12.
  5. John W. Chinneck. Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods. Springer, 2008. URL: https://doi.org/10.1007/978-0-387-74932-7.
  6. John W. Chinneck. The maximum feasible subset problem (maxFS) and applications. INFOR: Information Systems and Operational Research, 57(4):496-516, 2019. URL: https://doi.org/10.1080/03155986.2019.1607715.
  7. Iain Dunning, Joey Huchette, and Miles Lubin. JuMP: A modeling language for mathematical optimization. SIAM Review, 59(2):295-320, 2017. URL: https://doi.org/10.1137/15M1020575.
  8. Andreas Falkner, Alois Haselboeck, Gerfried Krames, Gottfried Schenner, Herwig Schreiner, and Richard Taupe. Solver Requirements for Interactive Configuration. Journal of Universal Computer Science, 26(3):343-373, 2020. Google Scholar
  9. Alexander Felfernig, Monika Schubert, and Christoph Zehentner. An efficient diagnosis algorithm for inconsistent constraint sets. AI EDAM, 26(1):53-62, 2012. URL: https://doi.org/10.1017/S0890060411000011.
  10. Eugene C. Freuder. Explaining Ourselves: Human-Aware Constraint Reasoning. In Proceedings 31st AAAI, pages 4858-4862. AAAI, 2017. Google Scholar
  11. R. M. Gasca, C. Valle, M. T. Gómez-López, and R. Ceballos. NMUS: Structural Analysis for Improving the Derivation of All MUSes in Overconstrained Numeric CSPs. In Daniel Borrajo, Luis Castillo, and Juan Manuel Corchado, editors, Current Topics in Artificial Intelligence: 12th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2007, Salamanca, Spain, November 12-16, 2007. Selected Papers, volume 4788 of LNCS, pages 160-169. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-75271-4_17.
  12. John Gleeson and Jennifer Ryan. Identifying Minimally Infeasible Subsystems of Inequalities. INFORMS Journal on Computing, 2(1):61-63, 1990. URL: https://doi.org/10.1287/ijoc.2.1.61.
  13. Olivier Guieu and John W. Chinneck. Analyzing infeasible mixed-integer and integer linear programs. INFORMS Journal on Computing, 11(1):63-77, 1999. URL: https://doi.org/10.1287/ijoc.11.1.63.
  14. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2020. URL: http://www.gurobi.com.
  15. Heerbod Jahanbani, M.D.U.P. Kularathna, Guido Tack, and Ilankaikone Senthooran. Considerations in developing an optimisation modelling tool to support annual operation planning of Melbourne Water Supply System. In Sondoss Elsawah, editor, MODSIM2019, 23rd International Congress on Modelling and Simulation. Modelling and Simulation Society of Australia and New Zealand, December 2019, page 592. Springer, 2019. Google Scholar
  16. Ulrich Junker. QuickXplain: Conflict detection for arbitrary constraint propagation algorithms. In IJCAI’01 Workshop on Modelling and Solving Problems with Constraints, 2001. Google Scholar
  17. Niklas Lauffer and Ufuk Topcu. Human-understandable explanations of infeasibility for resource-constrained scheduling problems. In Proc. 2nd Workshop on Explainable AI Planning, pages 44-52, 2019. Google Scholar
  18. Kevin Leo and Guido Tack. Debugging Unsatisfiable Constraint Models. In CPAIOR 2017, pages 77-93, 2017. URL: https://doi.org/10.1007/978-3-319-59776-8_7.
  19. Mark H. Liffiton and Ammar Malik. Enumerating Infeasibility: Finding Multiple MUSes Quickly. In Carla Gomes and Meinolf Sellmann, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 160-175. Springer Berlin Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-38171-3_11.
  20. Mark H. Liffiton and Karem A. Sakallah. Algorithms for computing minimal unsatisfiable subsets of constraints. Journal of Automated Reasoning, 40(1):1-33, 2008. URL: https://doi.org/10.1007/s10817-007-9084-z.
  21. Joao Marques-Silva, Federico Heras, Mikolás Janota, Alessandro Previti, and Anton Belov. On computing minimal correction subsets. In Twenty-Third International Joint Conference on Artificial Intelligence, pages 615-622, 2013. Google Scholar
  22. Joao Marques-Silva and Alessandro Previti. On Computing Preferred MUSes and MCSes. In International Conference on Theory and Applications of Satisfiability Testing, pages 58-74. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-09284-3_6.
  23. Deepak Mehta, Barry O’Sullivan, and Luis Quesada. Extending the notion of preferred explanations for quantified constraint satisfaction problems. In International Colloquium on Theoretical Aspects of Computing, pages 309-327. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-25150-9_19.
  24. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. MiniZinc: Towards a standard CP modelling language. In International Conference on Principles and Practice of Constraint Programming, pages 529-543. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74970-7_38.
  25. Alexander Schiendorfer, Alexander Knapp, Gerrit Anders, and Wolfgang Reif. MiniBrass: Soft constraints for MiniZinc. Constraints, 23(4):403-450, 2018. URL: https://doi.org/10.1007/s10601-018-9289-2.
  26. J.N.M. van Loon. Irreducibly inconsistent systems of linear inequalities. European Journal of Operational Research, 8(3):283-288, 1981. URL: https://doi.org/10.1016/0377-2217(81)90177-6.
  27. Jian Yang. Infeasibility resolution based on goal programming. Computers & Operations Research, 35(5):1483-1493, 2008. URL: https://doi.org/10.1016/j.cor.2006.08.006.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact