Please wait ...

Benchmark(s) have been added to cart.

Tag has been added.

• Login
• Links
• FAQs
• Contact

Navigation

• Instance
  • Show Instances
• Problem
  • Show Problems
• Show Tags
• Search
• Cart

Encoding checkdepots.lparse

Name	checkdepots.lparse
Class Tree	[Root]    Unclassified (114)    Fastfood (5)    Decision Version of Fastfood (3)
Submitter	Martin Gebser
Author	Wolfgang Faber
Description	This program checks whether a depot allocation has minimal supply costs among all depot allocations of the same cardinality. Input predicates: restaurant(Name,Km), depot(Name,Km) Output predicates: altdepot(Name,Km) Author: Wolfgang Faber <> License: GNU Public License, http://www.gnu.org/licenses/gpl.html
Created	2009-03-30 13:03
Modified	2009-03-12 22:45
Languages	lparse
Language Features	Cardinality constraints Choice rules Weight constraints
Compatible Instance Classes	Decision Version of Fastfood
Input Predicates	depot/2 restaurant/2
Output Predicates	altdepot/2
Encoding Parameter
Standalone	No
Tags
Attributes
Content	% This program checks whether a depot allocation has minimal supply % costs among all depot allocations of the same cardinality. % % Input predicates: % restaurant(Name,Km), depot(Name,Km) % Output predicates: % altdepot(Name,Km) % % Author: Wolfgang Faber <wf@wfaber.com> % License: GNU Public License, http://www.gnu.org/licenses/gpl.html % All possible kilometers. kilometer(0..910). % Auxiliary predicate: All distances between restaurant locations. distance(X,Y,X-Y):- restaurant(R1,X), restaurant(R2,Y), X>Y. distance(X,Y,Y-X):- restaurant(R1,X), restaurant(R2,Y), X<=Y. % The supply distance for each restaurant for the candidate solution % in the input. % PROBLEM: Not having "min", I first define in what distances are non serving % depots. doesntserve(Rname,D1) :- restaurant(Rname,RK), depot(Dname1,DK1), distance(RK,DK1,D1), depot(Dname2,DK2), distance(RK,DK2,D2), D2<D1. serves(Rname,Dist) :- restaurant(Rname,RK), depot(Dname,DK), distance(RK,DK,Dist), not doesntserve(Rname,Dist). % Each restaurant may be an alternative depot or not. {altdepot(R,K)} :- restaurant(R,K). % The number of alternative depots must be equal to the number of depots in % the input. % PROBLEM: Here I must make an additional assumption, that there will % be at most 910*2 depots, assuming that there are at most 2 % restaurants per kilometer, while this number is determined by the % instance really. % PROBLEM: I can use at most 1 cardinality atom per rule/constraint, so I must % define ndepots first. domainndepots(0..910*2). :- N+1 {altdepot(D1,K1):restaurant(D1,K1)}, N {depot(D2,K2):depot(D2,K2)} N, domainndepots(N). :- {altdepot(D1,K1):restaurant(D1,K1)} N-1, N {depot(D2,K2):depot(D2,K2)} N, domainndepots(N). % The supply distance for each restaurant for the alternative solution. % PROBLEM: Not having "min", I first define in what distances are non serving % depots. % PROBLEM: Need domain predicates for altdepot. doesntaltserve(Rname,D1) :- restaurant(Rname,RK), altdepot(Dname1,DK1), distance(RK,DK1,D1), altdepot(Dname2,DK2), distance(RK,DK2,D2), D2<D1, restaurant(Dname1,DK1), restaurant(Dname2,DK2). altserves(Rname,Dist) :- restaurant(Rname,RK), altdepot(Dname,DK), distance(RK,DK,Dist), not doesntserve(Rname,Dist), restaurant(Dname,DK). % Accept an alternative solution only if its supply costs are less % than the supply costs for the input candidate. % PROBLEM: I have to specify a domain for the cost. It is not clear % what this can become, assuming at most 2 restaurants per kilometer, the % maximum would be 207480 (one depot in the middle, two restaurants at each % kilometer, 2*(455+454+...+1) = 2*(455*456/2) by our friend Gauss), minimum % is 0 (all restaurants are depots). % PROBLEM: Even if I just take the kilometers as cost domain (which is in % general insufficient, see commented rule), lparse fills 2GB of memory % within 3 minutes. costdomain(0..455*456). :- C [altserves(R1,Dist1) : restaurant(R1,K1): kilometer(Dist1) = Dist1] C, C1 [serves(R2,Dist2) : restaurant(R2,K2): kilometer(Dist2) = Dist2] C1, C >= C1, costdomain(C), costdomain(C1). %:- C [altserves(R1,Dist1) : restaurant(R1,K1): kilometer(Dist1) = Dist1] C, % C1 [serves(R2,Dist2) : restaurant(R2,K2): kilometer(Dist2) = Dist2] C1, % C >= C1, kilometer(C), kilometer(C1).