10
$\begingroup$

Consider a CSP model where changing the value of a particular variable is expensive. Is there any work where the objective function also considers the number of changes in the value of the variable during the search process?

An example: The expensive-to-change variable may be in the control of some other agent and there is some overhead of involving that agent to change the variable. Another example: The variable participates in one of the constraints, and the satisfaction of this constraint involves calling an expensive function (such as, a simulator), e.g. $z = f(x, y)$ is the constraint, and $f$ is an expensive-to-compute function. Therefore, $x$ and $y$ are expensive-to-change variables.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The objective function talks about the final values of the CSP and is unaware of the search process. So, in standard formulations, the changes in such variables is not exposed to the CSP model. Some solvers, such as Choco, provide heuristics for guiding the search process. Some of these might even be user-defined. Perhaps that's the place to change how the search is done. $\endgroup$
    – Dave Clarke
    Apr 2, 2012 at 7:41
  • 1
    $\begingroup$ But why would the objective function reflect how expensive it was to come up with the solution? Should you not compare solutions by how useful they are in the problem domain afterwards? Or is the time-to-solution part of the real-world problem? $\endgroup$
    – Raphael ♦
    Apr 2, 2012 at 9:43
  • 1
    $\begingroup$ It sounds like you are in the setting of distributed constraint satisfaction and it sounds like you are looking for heuristics. $\endgroup$
    – Dave Clarke
    Apr 2, 2012 at 12:34

1 Answer 1

Reset to default
4
$\begingroup$

It sounds like you want a cost-sensitive (cost-aware, budgeted) optimization technique. Minimizing two values (e.g. the solution of your objective and the cost of operations on $x$ and $y$) is a multicriteria optimization problem, and those tend to be very hard to solve. A common approach is to specify a budget for the maximum allowable costs and then minimize the objective function with respect to $costs(x,y) \le Budget$. This formulation tends to fit nicely into existing frameworks as an additional constraint. Of course, specifying the cost function and the allowable budget in such a way that you get meaningful solutions can be difficult - this will depend on the specific problem you are trying to solve.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.