In Constraint Programming, are there any models that take into account the number of variable changes? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T06:19:28Z https://cs.stackexchange.com/feeds/question/987 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/987 10 In Constraint Programming, are there any models that take into account the number of variable changes? amit https://cs.stackexchange.com/users/893 2012-04-02T06:56:55Z 2015-05-28T08:34:13Z <p>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?</p> <p>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.</p> https://cs.stackexchange.com/questions/987/-/1057#1057 4 Answer by Nick for In Constraint Programming, are there any models that take into account the number of variable changes? Nick https://cs.stackexchange.com/users/924 2012-04-05T14:48:45Z 2012-04-05T14:48:45Z <p>It sounds like you want a cost-sensitive (cost-aware, <a href="http://www.dmargineantu.net/workshop/BudgetedLearning_ICML-2010/" rel="nofollow">budgeted)</a> optimization technique. Minimizing two values (e.g. the solution of your objective and the cost of operations on \$x\$ and \$y\$) is a <a href="http://en.wikipedia.org/wiki/Multi-objective_optimization" rel="nofollow">multicriteria optimization problem</a>, 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.</p>