answer set programming - ClingoGringo: How to prevent meaningless variants from being grounded - Stack Overflow

admin管理员组

文章数量:1314255

I'm trying to solve time dependent ASP problem using Clingo (version 5.7.1). Imagine that some project can start any year (2025, 2026 or 2027), and depending on this, its value in a given year can be 0 (if it hasn't started yet), or 30 (if started this year), 31 or 32 (if started in the previous year). At the end I want to sum up the obtained values. Here is my ASP/clingo code:

% Time horizon
 horizon(2025..2027).

% q(value, years from start)
 q(30, 0; 31, 1; 32, 2).  
                
% choice of start year
 { start(Year) : horizon(Year) } 1.

% possible values ​​depending on the year of start
 value(Value, Year) 
   :- q(Value, Year - YearStart), YearStart <= Year, start(YearStart), horizon(Year).

% summation of values ​​(in a real program, summation is performed for different objects, but it doesn't matter here)

 summation(Q, Year) 
   :- Q = #sum { Value : value(Value, Year) }, horizon(Year).

I expected the code grounding to be small, so that the possible variants of the sum constitute one of the values, namely 0, 30, 31 or 32.

But grounding (obtained with --text flag) is inflating at a factorial rate. Here is the result of grounding:

summation(0,2025):-#sum{30:value(30,2025)}=0.
summation(30,2025):-#sum{30:value(30,2025)}=30.
summation(0,2026):-#sum{30:value(30,2026);31:value(31,2026)}=0.
summation(30,2026):-#sum{30:value(30,2026);31:value(31,2026)}=30.
summation(31,2026):-#sum{30:value(30,2026);31:value(31,2026)}=31.
summation(61,2026):-#sum{30:value(30,2026);31:value(31,2026)}=61.
summation(0,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=0.
summation(30,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=30.
summation(31,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=31.
summation(61,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=61.
summation(32,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=32.
summation(62,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=62.
summation(63,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=63.
summation(93,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=93.

The reason is that gringo pre-sums all possible combinations of numbers. For example, in 2026 the value cannot be 61, but gringo grounds such an option (see above). In a time dependent problem this causes it to slow down considerably. The question is, how to avoid excessive grounding of meaningless combinations to reduce overall calculation time?

I'm trying to solve time dependent ASP problem using Clingo (version 5.7.1). Imagine that some project can start any year (2025, 2026 or 2027), and depending on this, its value in a given year can be 0 (if it hasn't started yet), or 30 (if started this year), 31 or 32 (if started in the previous year). At the end I want to sum up the obtained values. Here is my ASP/clingo code:

% Time horizon
 horizon(2025..2027).

% q(value, years from start)
 q(30, 0; 31, 1; 32, 2).  
                
% choice of start year
 { start(Year) : horizon(Year) } 1.

% possible values ​​depending on the year of start
 value(Value, Year) 
   :- q(Value, Year - YearStart), YearStart <= Year, start(YearStart), horizon(Year).

% summation of values ​​(in a real program, summation is performed for different objects, but it doesn't matter here)

 summation(Q, Year) 
   :- Q = #sum { Value : value(Value, Year) }, horizon(Year).

I expected the code grounding to be small, so that the possible variants of the sum constitute one of the values, namely 0, 30, 31 or 32.

But grounding (obtained with --text flag) is inflating at a factorial rate. Here is the result of grounding:

summation(0,2025):-#sum{30:value(30,2025)}=0.
summation(30,2025):-#sum{30:value(30,2025)}=30.
summation(0,2026):-#sum{30:value(30,2026);31:value(31,2026)}=0.
summation(30,2026):-#sum{30:value(30,2026);31:value(31,2026)}=30.
summation(31,2026):-#sum{30:value(30,2026);31:value(31,2026)}=31.
summation(61,2026):-#sum{30:value(30,2026);31:value(31,2026)}=61.
summation(0,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=0.
summation(30,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=30.
summation(31,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=31.
summation(61,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=61.
summation(32,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=32.
summation(62,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=62.
summation(63,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=63.
summation(93,2027):-#sum{30:value(30,2027);31:value(31,2027);32:value(32,2027)}=93.

The reason is that gringo pre-sums all possible combinations of numbers. For example, in 2026 the value cannot be 61, but gringo grounds such an option (see above). In a time dependent problem this causes it to slow down considerably. The question is, how to avoid excessive grounding of meaningless combinations to reduce overall calculation time?

• answer-set-programming
• clingo
• gringo

Share Improve this question Follow edited Jan 30 at 16:11 Alexander Belinsky asked Jan 30 at 13:47 Alexander BelinskyAlexander Belinsky 2111 silver badge22 bronze badges 3

• Is adding Q < 33 a feasible solution? This indeed reduces the grounding size. – damianodamiano Commented Feb 1 at 13:35
• Thank you very much, adding such inequality to the formula for calculating the sum partially solves the problem, limits grounding. But in some situations it can still perform grounding of meaningless sums (sum of numbers of different years). – Alexander Belinsky Commented Feb 2 at 14:02
• in your example, every summation/2 involves only one year. Where is the problem? Can you provide an example? – damianodamiano Commented Feb 4 at 13:17

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

You could precompute the possible sums instead of dynamically determining them.

% Time horizon
 horizon(2025..2027).

% q(value, years from start)
 q(30, 0; 31, 1; 32, 2).

% possible values
 value(YearStart, Value, Year)
   :- q(Value, Year - YearStart), YearStart <= Year, horizon(YearStart), horizon(Year).

% summation of values
 summation(YearStart, Q, Year)
   :- Q = #sum { Value : value(YearStart, Value, Year) }, horizon(Year), horizon(YearStart).

% choice of start year
 { start(Year) : horizon(Year) } 1.

sumofstartyear(Q, Year) :- start(YearStart), summation(YearStart, Q, Year).

And in the end you select the sum that you want. Depending on your usecase this might reduce your grounding.

But why not simply calculate the value you want:

 horizon(2025..2027).
 { start(Year) : horizon(Year) } 1.

summation(0, Year) :- start(YearStart), horizon(Year), Year < YearStart.
summation(30+Year-YearStart, Year) :- start(YearStart), horizon(Year), Year >= YearStart.

本文标签： answer set programmingClingoGringo How to prevent meaningless variants from being groundedStack Overflow