Human-centred feasibility restoration in practice
Open Access
- 1 June 2023
- journal article
- research article
- Published by Springer Nature in Constraints
- Vol. 28 (2) , 203-243
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 determine 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 evaluated the resulting framework on three real-world applications and conducted a qualitative expert user study with participants from different application domains.Keywords
Funding Information
- Monash University
This publication has 22 references indexed in Scilit:
- Enumerating Infeasibility: Finding Multiple MUSes Quickly2013
- An efficient diagnosis algorithm for inconsistent constraint setsArtificial Intelligence for Engineering Design, Analysis and Manufacturing, 2011
- Infeasibility resolution based on goal programmingComputers & Operations Research, 2008
- Algorithms for Computing Minimal Unsatisfiable Subsets of ConstraintsJournal of Automated Reasoning, 2007
- NMUS: Structural Analysis for Improving the Derivation of All MUSes in Overconstrained Numeric CSPsLecture Notes in Computer Science, 2007
- On global warming: Flow-based soft global constraintsJournal of Heuristics, 2006
- Interactively Solving School Timetabling Problems Using Extensions of Constraint Programming2005
- Analyzing Infeasible Mixed-Integer and Integer Linear ProgramsINFORMS Journal on Computing, 1999
- A Description of Think Aloud Method and Protocol AnalysisQualitative Health Research, 1993
- Irreducibly inconsistent systems of linear inequalitiesEuropean Journal of Operational Research, 1981