[Oz] Examples of configuration-type problems

[Lua Seet Chong]

On Mon, 25 Jan 1999, Kent Hoxsey wrote:

Kent,

	I tried to implement a simple example in Dr. Alan Borning's paper.
You may want to take a look at this simple oz program and his paper.

	You can use the reified constraint to reflect the validity of a
constraint to another 0-1 constraint variable.  Then you can have
a simple hierarchical cost function on these reified variables.  See 
the reference in finite domain "reified constraint" section.

	Please see the attachment for the simple program.  You can see his
home page for Hierarchical Constraint Logic Programming.  

Regards,
Seet Chong

	
> In addition, if the problem were set up so it was over-constrained,
> where the constraints are hierarchical and the goal is to minimize the
> weights of the violated constraints, is it possible to know which
> constraints were violated?
> 
> TIA,
> Kent

------------------------------------------------------------------------

declare
proc {Timetable Root}

   % Start and End time of the scheduled meeting
   S = {FD.decl}
   E = {FD.decl}

   % Root consists of the Solution and the Quality of solution 
   Solution
   Quality

   % Constraint Hierarchy quality
   StrongQuality = {FD.decl}
   MediumQuality = {FD.decl}

   proc {SoftConstraint Quality PrefList}
      {FD.sum {Flatten PrefList} '=:' Quality}
   end

   fun {FindTime StartFree EndFree Start End}
      [ (StartFree =<: Start)  (End       =<: EndFree) ]
   end

in
   % The root variable
   Root = r(solution:Solution quality:Quality)
   Solution = sol(s:S e:E)
   Quality = StrongQuality # MediumQuality

   % Required constraints
   Solution ::: 6#12
   E =: S + 1
   
   % Constraint Hierarchy Level 1
   % Meeting room constraint

   {SoftConstraint StrongQuality {FindTime 8 10 S E} }

   % Constraint Hierarchy Level 2 
   % Meeting people's constraints
   %   FreeData = [%Name Start End
   %	            alan # 6 # 8
   %	            bjorn # 8 # 9
   %	            john # 11 # 12
   %	            molly # 10 # 12]


   {SoftConstraint MediumQuality
    [
      {FindTime 6 8 S E}   %Alan
      {FindTime 8 9 S E}   %Bjorn
      {FindTime 11 12 S E} %John
      {FindTime 10 12 S E} %Molly
    ]
   }

   % Distribute the search space
   {FD.distribute ff Solution}
end

% The weighted sum better comparator (with weight = 1)
declare
proc {Comparator Old New}
   % Level 1
   Old.quality.1 =<: New.quality.1

   % Level 2
   if Old.quality.1 =: New.quality.1 then
      Old.quality.2 =<: New.quality.2
   else skip end
end

{ExploreBest Timetable Comparator}

/*
% Use a simple procedure for comparison

{ExploreBest Timetable proc {$ Old New} Old.quality.1 =<: New.quality.1 end}
*/

/*
% Use the SearchOne, SearchBest
declare ?Solution
{SearchOne Timetable ?Solution}
{SearchBest Timetable Comparator ?Solution}
{Browse ?Solution}
*/


-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.