1,720,971 research outputs found
Uncertainty in bipolar preference problems
No full textPreferences and uncertainty are common in many real-life problems. In this article, we focus on bipolar preferences and uncertainty modelled via uncontrollable variables, and we assume that uncontrollable variables are specified by possibility distributions over their domains. To tackle such problems, we concentrate on uncertain bipolar problems with totally ordered preferences, and we eliminate the uncertain part of the problem, while making sure that some desirable properties hold about the robustness of the problem and its relationship with the preference of the optimal solutions. We also consider several semantics to order the solutions according to different attitudes with respect to the notions of preference and robustness
Dealing with incomplete preferences in soft constraint problems
No full textWe consider soft constraint problems where some of the preferences may be unspecified. This models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define an algorithm to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. Experimental results show that in many cases a necessarily optimal solution can be found without eliciting too many preferences
Compact Preference Representation via Fuzzy Constraints in Stable Matching Problems: Theoretical and Experimental Studies
No full textThe stable matching problem has many practical applications in two-sided markets, like those that assign doctors to hospitals or students to schools. Usually it is assumed that all agents in each side explicitly express a preference ordering over those in the other side. This can be unfeasible and impractical when the set of agents is very big. However, usually this set has a combinatorial structure, since each agent is often described by some features. To tackle these scenarios, we define a framework for stable matching problems where agents are allowed to express their preferences over those of the other group in a compact way, via soft constraints over the features describing these agents. We focus on a special kind of soft constraints, namely fuzzy constraints. We provide a solving engine for this new kind of stable matching problems that does not increase the time complexity of the classical Gale-Shapley algorithm, while maintaining stability of the matching returned. We then eval..
Robust solutions in unstable optimization problems
No full textWe consider constraint optimization problems where costs
(or preferences) are all given, but some are tagged as possibly unstable,
and provided with a range of alternative values. We also allow for some
uncontrollable variables, whose value cannot be decided by the agent
in charge of taking the decisions, but will be decided by Nature or by
some other agent. These two forms of uncertainty are often found in
many scheduling and planning scenarios. For such problems, we define
several notions of desirable solutions. Such notions take into account not
only the optimality of the solutions, but also their degree of robustness
(of the optimality status, or of the cost) w.r.t. the uncertainty present
in the problem. We provide an algorithm to find solutions accordingly
to the considered notions of optimality, and we study the properties of
these algorithms. For the uncontrollable variables, we propose to adopt
a variant of classical variable elimination, where we act pessimistically
rather than optimistically
A Local Search Approach for Incomplete Soft Constraint Problems: Experimental Results on Meeting Scheduling Problems
No full textWe 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..
- …
