From: Joachim Schimpf (Independent Contractor) <jschimpf_at_cisco.com>

Date: Tue, 05 Jun 2007 23:42:19 +0100

Date: Tue, 05 Jun 2007 23:42:19 +0100

Vicenç wrote: > Say you have: > > cost(green, Size, Cost) :- Cost is Size*2. > cost(black, Size, Cost) :- Cost is Size/2. > > Now you need to declare constraints on the Size > related with objects: > > size(table, 10). > size(chair, 5). > ... > > but from another *totally independent* predicate > you want to constraint the same variable Size, > which could be, for instance, the second argument of > another predicate: > > machine(a1, 10, ... ). > machine(a2, 20, ... ). > ... I am still not exactly sure what problem you see. Maybe you are confusing code and data. The predicates in your code, and the variables in them are just templates. You will get actual instances of these variables when you call the predicates, and for every call you have fresh instances. > > Speaking in more technical terms, the "execution" of a > Prolog program can be viewed as the construction of > a "model", in which if variable Size has been already > instantiated, it should not take another value. > Because it is cumbersome to put all variables > as arguments (and also because not all models > will require all the variables) one has the necessity > of passing a "context" which includes the current > "partial" model. You will indeed need to pass variables as arguments, such that you can connect the right variables with the right constraints. A standard schema for a constraint program is solve(Data, Result) :- create_variables(Data, Variables), impose_constraints(Variables), search(Variables), Result = Variables. You need some data structure(s) that contain the problem variables. In the simplest case this is a list of variables, but the variables could also be contained in structures, organised in a hash table, or whatever. To set up your constraints, you traverse these data structures, or use them to look up the variables you need for each constraint. In the end, you still have the data structure with the variables, but they are now "invisibly" connected through constraints. Then you go into search, which again needs to visit the variables and select values for them. Here is an example, inspired by your data. Suppose we want to produce chairs and tables with choosen colours. Cost depends on item size and colour. We want to know how many we can produce without exceeding a maximum cost. % The solver library to use :- lib(ic). % Problem Model % Data input: % Demands is a list of terms like demand(chair,blue) % MaxCost is a number % Output: % Amounts is a list of constrained variables, one for each demand % TotalCost is a constrained variable for the total cost model(Demands, MaxCost, Amounts, TotalCost) :- % for every demand, create and constrain Cost and Amount variables % and collect them in two lists ( foreach(demand(Item,Color),Demands), % in foreach(Cost,Costs), % out foreach(Amount,Amounts) % out do Amount #>= 0, item_size(Item,Size), color_cost(Color,CostPerUnit), Cost #= Size*CostPerUnit*Amount ), % set up some additional constraints TotalCost #>= 0, TotalCost #=< MaxCost, sum(Costs) #= TotalCost. % Solving consists of modelling (= constraint setup) and search solve(Demands, MaxCost, Amounts, TotalCost) :- model(Demands, MaxCost, Amounts, TotalCost), labeling(Amounts). % Data that never changes can be stored as facts color_cost(red, 5). color_cost(green, 7). color_cost(blue, 3). color_cost(yellow, 4). item_size(table, 10). item_size(chair, 5). You can now call ?- solve([demand(chair,red),demand(table,blue)], 100, Amounts, Cost). which will give you (on backtracking) all solutions that satisfy your constraints. A few final remarks: - we have data that never changes (e.g. table size) and only for that reason is it justified to store it in the form of facts! - we have data that is different for every run of the solver (the demand list), and is therefore passed into model/4 as an argument. - as opposed to the schema above, variable creation and constraint setup are interleaved in model/4 - this is fairly common. - we don't need to pass all of the variables to the search: we treat some variables as "decision variables" (the amounts), because the costs will automatically follow from them. - to find an optimal solution, use lib(branch_and_bound) on top of this -- JoachimReceived on Tue Jun 05 2007 - 23:42:32 CEST

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*