Re: [ojAlgo-user] Integer Linear Programming: ojAlgo calculates invalid solution

[Uli S. <Uli...@In...>]

Hi,

Am 27.01.2015 um 12:23 schrieb Anders Peterson:
> Running your program with the latest development version of ojAlgo (requires Java 8) I get this output and no exceptions;

Sorry that I didn't mention it, but I am using ojAlgo 37. I did not try 
with the latest development version and sadly my project cannot switch 
from Java 7 to Java 8.

> x = 21.0 ~ 21
> y = -1.0 ~ -1
>
> Is that what you want?

x = 21 and y = -1 is indeed one of my desired solution.

> There are a number of configurable options in ExpressionsBasedModel.options that control accuracy and rounding. Some of
 > these are a bit sensitive and changing them is not generally 
recommended, but he "integer" and "solution" number
 > contexts should be relatively safe to tweak.

I don't have much time right now, but I will look more closely into this 
later.

 From what I understand right now, "solution" affects how the solution 
is turned into a BigDecimal. However, I don't see how rounding 
"19.999.." can get help me here, since the desired value would be 21.

The member "integer" sounds more promising. I guess I want something 
like a new NumberContext(largish-value-e.g.-10, RoundingMode.HALF_UP). I 
will experiment with this later. Thanks for the hint.

> If you call minimise() rather than solve() does it make a difference?

None that matters, but the values in the result change a little.

solve():

x = 19.999999999999993 ~ 20
y = -0.9950000000000006 ~ -1

minimise():

x = 20.00000000000000 ~ 20
y = -0.99500000000000 ~ -1

> /Anders

Thanks for looking into this.
Uli

>> On 27 jan 2015, at 10:10, Uli Schlachter <Uli...@In...> wrote:
>>
>> Hi everyone,
>>
>> the attached Java program solves a relatively simple ILP with ojAlgo. However, the solution calculates is invalid. Can somehow shed some light into why this is?
>>
>> Hopefully the program explains itself, but here is some more text:
>>
>> The function getCoefficients() returns the coefficients for 202 inequalities of the form coef[0]*x + coef[1]*y < 0. The main function creates an ExpressionsBasedModel from this, transformimg the "< 0" into "<= -1" (which is valid since this is about integer values). It prints the solution calculated and then checks if all the inequalities really are satisfied.
>>
>> However, this fails since the solution calculated doesn't solve all inequalities:
>>
>> x = 19.999999999999993 ~ 20
>> y = -0.9950000000000006 ~ -1
>> Exception in thread "main" java.lang.Exception: -10*x + -200*y = 0 must be negative (exact: -0.9999999999998100)
>> 	at Solve.main(Solve.java:60)
>>
>> The program also prints the exact solutions calculated from the BigDecimals that ojAlgo produced. This is the "exact" value you see in the error message above and, as you see, this value (almost) satisfies the condition "<= -1".
>>
>> Valid solutions to this inequality systems would be x=21, y=-1 or x=201, y=-10.
>>
>> Obviously, this seems to be a rounding issue. Is there anything that can be done about it?
>>
>> Cheers,
>> Uli
>> --
>> - Buck, when, exactly, did you lose your mind?
>> - Three months ago. I woke up one morning married to a pineapple.
>>   An ugly pineapple... But I loved her.
>> <Solve.java>------------------------------------------------------------------------------
>> Dive into the World of Parallel Programming. The Go Parallel Website,
>> sponsored by Intel and developed in partnership with Slashdot Media, is your
>> hub for all things parallel software development, from weekly thought
>> leadership blogs to news, videos, case studies, tutorials and more. Take a
>> look and join the conversation now. http://goparallel.sourceforge.net/_______________________________________________
>> ojAlgo-user mailing list
>> ojA...@li...
>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming. The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>


-- 
- Buck, when, exactly, did you lose your mind?
- Three months ago. I woke up one morning married to a pineapple.
   An ugly pineapple... But I loved her.