Re: [eclipse-users] storing a context

From: Joachim Schimpf (Independent Contractor) <jschimpf_at_cisco.com>
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


-- Joachim
Received 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