%
% Problem:
%
% From: marco
% Newsgroups: comp.lang.prolog
% Subject: CLP-FD suggestions
% Date: Wed, 9 Dec 2009 05:20:12 -0800 (PST)
%
% I would like to solve a simple problem in CLP: assign 26 groups of
% people of various sizes to 6 slots respecting the capacity of each
% slot and minimizing the conflicts among the preferences of people.
% Preferences are expressed, for each group, as a list of distances from
% optimum.
% ...
%
% Solution:
%
% This solution uses a combination of linear programming solver (eplex)
% and finite domain solver (ic). The finite domain solver handles all
% constraints, including integrality. The linear solver solves the
% continuous relaxation (ignoring integrality) of the problem, thus
% providing a lower bound on the Cost variable. Moreover, the labeling
% procedure is guided by the fractional solutions to the relaxation as
% a heuristic.
%
% Note that it would be possible to add constraints that are (or can be)
% handled by the finite domain solver alone.
%
% Joachim Schimpf, Monash University, Dec 2009.
% This code may be freely used for any purpose.
%
:- lib(eplex).
:- lib(ic).
:- lib(branch_and_bound).
solve(Cost, Slots) :-
data(Pref, Cap, Size),
model(Pref, Cap, Size, Slots, Obj),
ic:(Cost #= eval(Obj)),
eplex_solver_setup(min(Obj), Cost, [sync_bounds(yes)], [deviating_bounds]),
minimize(lp_guided_search(Slots), Cost),
( foreacharg(Slot,Slots) do writeln(Slot) ).
lp_guided_search(Xs) :-
( foreachelem(X,Xs) do
eplex_var_get(X, solution, RelaxedSol),
Guess is integer(round(RelaxedSol)),
( X = Guess ; X #\= Guess )
).
model(Pref, Cap, Size, Slots, Obj) :-
dim(Cap, [NSlots]),
dim(Size, [NGroups]),
dim(Slots, [NSlots,NGroups]),
[ic,eplex]: (Slots[1..NSlots,1..NGroups] $:: 0.0..1.0),
ic: integers(Slots[1..NSlots,1..NGroups]),
( for(T,1,NSlots), param(Slots,Cap,Size,NGroups) do
( for(G,1,NGroups), foreach(U,Used), param(Slots,Size,T) do
U = Size[G] * Slots[T,G]
),
[ic,eplex]: (sum(Used) $=< Cap[T])
),
( for(G,1,NGroups), param(Slots,NSlots) do
[ic,eplex]: (sum(Slots[1..NSlots,G]) $= 1)
),
( multifor([T,G],1,[NSlots,NGroups]), foreach(C,Cs), param(Pref,Slots) do
C = Pref[T,G] * Slots[T,G]
),
Obj = sum(Cs).
data(Prefs, Capac, Compon) :-
Prefs = [](
[](1, 2, 6, 5, 6, 6, 3, 4, 4, 1, 2, 4, 4, 3, 1, 5, 1, 4, 5, 6, 5, 2, 5, 5, 3, 2),
[](2, 3, 3, 2, 1, 4, 4, 2, 2, 6, 3, 1, 5, 5, 5, 6, 4, 2, 6, 4, 4, 5, 6, 2, 2, 1),
[](5, 1, 1, 6, 3, 5, 5, 3, 6, 5, 5, 3, 6, 2, 4, 1, 6, 3, 2, 5, 1, 1, 2, 6, 4, 3),
[](3, 6, 5, 3, 5, 3, 2, 1, 3, 3, 4, 2, 1, 1, 6, 2, 3, 5, 1, 3, 6, 3, 4, 3, 6, 5),
[](4, 4, 4, 4, 2, 2, 1, 6, 1, 4, 6, 5, 2, 4, 2, 3, 5, 6, 4, 2, 3, 6, 1, 1, 1, 6),
[](6, 5, 2, 1, 4, 1, 6, 5, 5, 2, 1, 6, 3, 6, 3, 4, 2, 1, 3, 1, 2, 4, 3, 4, 5, 4)
),
Capac = [](18, 18, 18, 18, 18, 18),
Compon = [](5, 4, 4, 4, 3, 3, 3, 3, 3, 4, 4, 5, 5, 2, 5, 3, 4, 4, 3, 3, 3, 5, 2, 4, 4, 5).