conjure
conjure copied to clipboard
conjure-cp
Dealing with floats
I have a couple of problems I want to specify with Conjure. Several of them involve floats, either as variable types, or in the context of floating-point division in objective functions.
I noticed that Essence only supports integers. Is there a particular reason for that?
Are there some known workarounds for this issue, like "specification patterns" - either for variables or to implement floating-point division?
Many thanks in advance!
Dear @dstrueber - apologies for our very slow response!
Essence doesn't support floating-point numbers. There isn't really a deep reason for this other than nobody bothering to add support for them so far. Discrete satisfaction/optimisation problems are our main research interest.
The main method for handling floating-point numbers in a system like ours would be discretisation. How much success you can get with this depends on your use of floating-point. Is it only data, part of decisions, or objective function?
We use floating point division in our objective function. The data and decisions in our case are discrete.
We now tried to circumvent the issue with floating-point division by transforming the objective function. Our original objective function was a sum over a fraction. Our new, transformed objective function is a sum over a complicated sum that includes a product. Unfortunately, we get the following error during execution (I can also open a new issue if you prefer). Is there anything we can do about that? Here's our problem specification.
Error: Savile Row stdout: Savile Row stderr: Exception in thread "Thread-0" java.lang.OutOfMemoryError: Java heap space at java.util.Arrays.copyOf(Arrays.java:3181) at java.util.ArrayList.grow(ArrayList.java:265) at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:239) at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:231) at java.util.ArrayList.add(ArrayList.java:462) at savilerow.expression.Times.getIntervalSetExp(Times.java:197) at savilerow.model.SymbolTable.newAuxHelper(SymbolTable.java:483) at savilerow.treetransformer.TransformToFlat.processNode(TransformToFlat.java:45) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:135) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121) at savilerow.treetransformer.TreeTransformerBottomUp.transform(TreeTransformerBottomUp.java:86) at savilerow.model.Model.transform(Model.java:228) at savilerow.model.ModelContainer.instanceFlattening(ModelContainer.java:891) at savilerow.model.ModelContainer.squashDomains(ModelContainer.java:451) at savilerow.model.ModelContainer.process(ModelContainer.java:55) at savilerow.SRWorkThread.run(SRWorkThread.java:87)
Savile Row exit-code: 0
Hi,
Not a Conjure developer but some information that might help both the issuer and developer:
I had a quick look, it seems like the main issue is with the line:
product([ |preImage(fm,cj)|*|preImage(fa,cj)|*|preImage(fm,cj)|*(|preImage(fm,cj)|-1) | cj : ClassDomain, ci != cj ])
though you most likely already knew this.
I tested this by removing the line and all seems to be okay. Interestingly, removing everything apart from the problematic line reveals a different issue:
So I wrote:
minimising sum([
product([ |preImage(fm,cj)|*|preImage(fa,cj)|*|preImage(fm,cj)|*(|preImage(fm,cj)|-1) | cj : ClassDomain, ci != cj ])
| ci : ClassDomain ])
This produces an error in SR:
Magnitude of number too large!,
produced by the minion solver.
Which suggests that the deduced maximum value of the expression is two large for a machine int.
Usually, this is solved by explicitly specifying the domain of the expression result.
One way to do this is to rewrite the expression to assign the intermediate result of each product to a variable who's domain has some smaller upper bound.
So maybe use a function:
find f : function (ClassDomain, ClassDomain) --> int(1..upperbound)
such that forAll ((ci,cj),r) in f . r = |preImage(fm,cj)||preImage(fa,cj)||preImage(fm,cj)|*(|preImage(fm,cj)|-1)
`f` is a partial function. Most likely want to enforce that it does not contain the pre image where `ci = cj` to match the original expression.
forAll ((ci,cj),_) in f . ci != cj
Then you need to do the product over the function, maybe also assigning that to a variable with an explicit domain upper bound.
Hope this helps!
> On 14 Oct 2019, at 16:11, Daniel Strüber <[email protected]> wrote:
>
> We use floating point division in our objective function. The data and decisions in our case are discrete.
>
> We now tried to circumvent the issue with floating-point division by transforming the objective function. Our original objective function was a sum over a fraction. Our new, transformed objective function is a sum over a term that includes a product with many components. Unfortunately, we get the following error during execution (I can also open a new issue if you prefer).
> Is there anything we can do about that? Here's our problem specification. <https://github.com/conjure-cp/conjure/files/3725105/problem.essence.txt>
> Error:
> Savile Row stdout:
> Savile Row stderr: Exception in thread "Thread-0" java.lang.OutOfMemoryError: Java heap space
> at java.util.Arrays.copyOf(Arrays.java:3181)
> at java.util.ArrayList.grow(ArrayList.java:265)
> at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:239)
> at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:231)
> at java.util.ArrayList.add(ArrayList.java:462)
> at savilerow.expression.Times.getIntervalSetExp(Times.java:197)
> at savilerow.model.SymbolTable.newAuxHelper(SymbolTable.java:483)
> at savilerow.treetransformer.TransformToFlat.processNode(TransformToFlat.java:45)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:135)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.recursiveSearch(TreeTransformerBottomUp.java:121)
> at savilerow.treetransformer.TreeTransformerBottomUp.transform(TreeTransformerBottomUp.java:86)
> at savilerow.model.Model.transform(Model.java:228)
> at savilerow.model.ModelContainer.instanceFlattening(ModelContainer.java:891)
> at savilerow.model.ModelContainer.squashDomains(ModelContainer.java:451)
> at savilerow.model.ModelContainer.process(ModelContainer.java:55)
> at savilerow.SRWorkThread.run(SRWorkThread.java:87)
>
> Savile Row exit-code: 0
>
> —
> You are receiving this because you are subscribed to this thread.
> Reply to this email directly, view it on GitHub <https://github.com/conjure-cp/conjure/issues/451?email_source=notifications&email_token=ABNOACVPAHNPD4QYCSYVZBLQOSD27A5CNFSM4IXPZ7NKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEBFEF7I#issuecomment-541737725>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABNOACQ34GNXJDEOPFII6ATQOSD27ANCNFSM4IXPZ7NA>.
>
Many thanks for your detailed and insightful response, SaadAttieh!
I followed your advice and found that I can get a reduced version of the problem to run, where the objective function is the sum over the problematic product, and the bounds for f's values are set to int(0..24). If I use a slightly larger upper bound of 96, I run into the same minion error message you reported for the unbounded case.
When I use the upper bound of 24 and include the remainder of the original objective function, I get the OutOfMemoryError I reported earlier in this thread.
It seems that the objective function in my problem is too complicated (has too many multiplication components) to be supported at this time.
Hi @dstrueber - I am looking at this now. Basically doing what Saad said (but maybe a bit more aggressively).
I must say this is really not ideal, but coming up with small intermediate domains would be wrong in general, so our tools must assume the worst.
Can I ask if you have the optimal solution for this instance? I have a solution where the objective is 0 but I might have made a mistake during my translation.
Thanks, @ozgurakgun. For the given version of the problem, I don't have the optimum, but a 0 is rather likely.
It is derived from a version of the problem with an even more tricky objective function, for which I probably know the global maximum. The objective function in that one has some dedicated handling (if-then-else style) of components whose value computes to zero. I didn't fully formulate that one yet as I'm not too optimistic it will work, when this simpler version doesn't.
Actually I didn't have to be more aggressive at all. @SaadAttieh's solution seems to work.
I get the following, which seems quite reasonable.
~/tmp> time conjure solve 451.essence
Generating models for 451.essence
Generated models: model000001.eprime
Saved under: conjure-output
Savile Row: model000001.eprime
Running minion for domain filtering.
Running solver: minion
Copying solution to: 451.solution
real 0m2.810s
user 0m4.290s
sys 0m0.224s
~/tmp> cat 451.solution
language Essence 1.3
letting fa be function(1 --> 2, 2 --> 2, 3 --> 2, 4 --> 2, 5 --> 2)
letting fm be function(1 --> 1, 2 --> 1, 3 --> 1, 4 --> 1)
letting obj be 0
letting products_ci_cj be
[[0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)], [0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)],
[0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)], [0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)],
[0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)], [0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)],
[0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)], [0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)],
[0, 0, 0, 0, 0, 0, 0, 0, 0; int(1..9)];
int(1..9)]
$ Visualisation for products_ci_cj
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
$ 0 0 0 0 0 0 0 0 0
And this is the modified model that I used.
language Essence 1.3
letting ClassDomain be domain int(1..9)
letting MethodDomain be domain int(1..4)
letting AttributeDomain be domain int(1..5)
letting DMM be
[[1, 1, 0, 0; int(1..4)],
[1, 1, 0, 0; int(1..4)],
[0, 0, 1, 1; int(1..4)],
[0, 0, 1, 1; int(1..4)];
int(1..4)]
letting DMA be
[[1, 1, 0, 0, 1; int(1..5)],
[1, 1, 0, 0, 1; int(1..5)],
[0, 0, 1, 1, 1; int(1..5)],
[0, 0, 1, 1, 1; int(1..5)];
int(1..4)]
find fm : function (total) MethodDomain --> ClassDomain
find fa : function (total) AttributeDomain --> ClassDomain
letting M be 100
find products_ci_cj : matrix indexed by [ClassDomain, ClassDomain] of int(0..M)
such that forAll ci, cj : ClassDomain . products_ci_cj[ci,cj] = |preImage(fm,cj)|*|preImage(fa,cj)|*|preImage(fm,cj)|*(|preImage(fm,cj)|-1)
such that forAll ci : ClassDomain . products_ci_cj[ci,ci] = 0
find obj : int(0..10000000)
such that obj = sum ci : ClassDomain .
sum([ DMA[i,j] | i : MethodDomain , j : AttributeDomain , fm(i) = ci , fa(j) = ci ])
*
|preImage(fm,ci)|
*
(|preImage(fm,ci)|-1)
+
sum([ DMM[i,j] | i : MethodDomain , j : MethodDomain , fm(i) = ci , fm(j) = ci ])
*
|preImage(fm,ci)|
*
|preImage(fa,ci)|
*
product([ products_ci_cj[ci,cj] | cj : ClassDomain, ci != cj ])
minimising obj
Note: I edited the comment to use a matrix for products_ci_cj instead of a function. function would have worked as well.
Hi @dstrueber - I am just wondering whether you had a chance to try this?
Just took a peak, the only difference I can see is that I used a partial function whilst you used a total function mapping values to 0 where necessary. Perhaps this produced a better refinement?
On 4 Nov 2019, at 11:43, Özgür Akgün [email protected] wrote:
Hi @dstrueber https://github.com/dstrueber - I am just wondering whether you had a chance to try this?
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/conjure-cp/conjure/issues/451?email_source=notifications&email_token=ABNOACVDJBEUYG2HGANG3MTQSADHZA5CNFSM4IXPZ7NKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEC667XA#issuecomment-549318620, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABNOACR2X77EUOYJOJ7AIP3QSADHZANCNFSM4IXPZ7NA.
I don't think there is a significant difference between your model and mine Saad. Except mine was a complete model so I assumed it may be easier to check :)