A Local Search Approach for Incomplete Soft Constraint Problems: Experimental Results on Meeting Scheduling Problems

We consider soft constraint problems where some of the preferences may be unspecified. In practice, some preferences may be missing when there is, for example, a high cost for computing the preference values, or an incomplete elicitation process. Within such a setting, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define a local search approach that interleaves search and preference elicitation, with the goal to find a solution which is “necessarily optimal”, that is, optimal no matter the missing data, whilst asking the user to reveal as few preferences as possible. Previously, this problem has been tackled with a systematic branch & bound algorithm. We now investigate whether a local search approach can find good quality solutions to such problems with fewer resources. While the approach is general, we evaluate it experimentally on a class of meeting scheduling problems with missing preferences. The experimental results sho...