ojalgo-user

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

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

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.

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

[Anders P. <an...@op...>]

Running your program with the latest development version of ojAlgo (requires Java 8) I get this output and no exceptions;

x = 21.0 ~ 21
y = -1.0 ~ -1

Is that what you want?

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.

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


/Anders



> 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

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.

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

[Anders P. <an...@op...>]

Most likely the rounding problem/numerical issue is with the LinearSolver. 

I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.

To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.

I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.

If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.

If you turn on solver debugging you'll get some info regarding what goes on:

    model.options.debug(LinearSolver.class);

or

    model.options.debug(IntegerSolver.class);


or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.


/Anders



> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
> 
> 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.
> 
> ------------------------------------------------------------------------------
> 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

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

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

Hi,

I tried looking into this, but I'm not familiar enough with ojAlgo's 
internals, I guess. Attached is what I ended up with:

- I reduced the model used to:

   -10*x + -199*y <= -1
   -10*x + -200*y <= -1

This still shows the same behavior as the code from my first mail.

- Thanks to your hint with model.options.debug(), I added the following 
which is what the Branch&Bounde Node where "something goes wrong" uses:

   1 <= x <= 20
   y <= -1

  -This makes the model unsolvable, but with model.options.validate = 
true, ojAlgo still notices that "something is wrong".

- Also this has the nice side effect that no branching happens anymore 
and thus no non-determinism due to threads. (More readable debug output!)

- In OldIntegerSolver, there is some code that is commented out which 
prints more information in case validation fails. I ended up with this:

   if (OldIntegerSolver.this.options.validate && 
!tmpModel.validate(tmpResult)) {
     // This should not be possible. There is a bug somewhere.
     OldIntegerSolver.this.debug("!!!!!!!\n!!!!!!!\n" +
           "Node solution marked as OPTIMAL, but is actually 
INVALID/INFEASIBLE/FAILED. Stop this branch!\n" +
            myKey.toString() + "\n" +
            OldIntegerSolver.this.toString() +"\n" +
            tmpModel.toString() +"\n");
     final GenericSolver tmpDefaultSolver = tmpModel.getDefaultSolver(); 
 

     tmpDefaultSolver.solve();
     OldIntegerSolver.this.debug(tmpDefaultSolver.toString());
     return false;
  }

- The output produced by model.options.debug(LinearSolver.class); from 
this is attached. Please note that the above code calls solve() again on 
the model. I checked that this second run produces the same debug output 
and removed it from the log file. The position is marked with "[SNIP...]".

At this point I don't know how to continue, but hopefully this helps you 
in figuring out things when you have the time.

Cheers & have a nice week,
Uli

Am 27.01.2015 um 17:56 schrieb Anders Peterson:
> Most likely the rounding problem/numerical issue is with the LinearSolver.
>
> I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.
>
> To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.
>
> I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.
>
> If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.
>
> If you turn on solver debugging you'll get some info regarding what goes on:
>
>      model.options.debug(LinearSolver.class);
>
> or
>
>      model.options.debug(IntegerSolver.class);
>
>
> or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.
>
>
> /Anders
>
>
>
>> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
>>
>> 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.
>>
>> ------------------------------------------------------------------------------
>> 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.

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

[Anders P. <an...@op...>]

Have I understood this correct: You have a model with 2 variables and 2 inequality constraints that, at a specific branch-and-bound node, demonstrates the problem?

From the output and your comments it seems clear that the problem is with the LinearSolver - it fails to discover/report that a subproblem is infeasible.

The output contains this: "Switching to Phase2 with 1 artificial variable(s) still in the basis."

...and then I've noticed that you have not specified an objective function (any/all solutions are equally good). 

This combination could very well be something that ojAlgo fails to handle. I'll look in to this, but it has to be in a few days or so.

Have you tried specifying an objective function - preferably one that clearly favours some solutions over others? (x is better than y)


/Anders



> On 28 jan 2015, at 10:25, Uli Schlachter <Uli...@In...> wrote:
> 
> Hi,
> 
> I tried looking into this, but I'm not familiar enough with ojAlgo's internals, I guess. Attached is what I ended up with:
> 
> - I reduced the model used to:
> 
>  -10*x + -199*y <= -1
>  -10*x + -200*y <= -1
> 
> This still shows the same behavior as the code from my first mail.
> 
> - Thanks to your hint with model.options.debug(), I added the following which is what the Branch&Bounde Node where "something goes wrong" uses:
> 
>  1 <= x <= 20
>  y <= -1
> 
> -This makes the model unsolvable, but with model.options.validate = true, ojAlgo still notices that "something is wrong".
> 
> - Also this has the nice side effect that no branching happens anymore and thus no non-determinism due to threads. (More readable debug output!)
> 
> - In OldIntegerSolver, there is some code that is commented out which prints more information in case validation fails. I ended up with this:
> 
>  if (OldIntegerSolver.this.options.validate && !tmpModel.validate(tmpResult)) {
>    // This should not be possible. There is a bug somewhere.
>    OldIntegerSolver.this.debug("!!!!!!!\n!!!!!!!\n" +
>          "Node solution marked as OPTIMAL, but is actually INVALID/INFEASIBLE/FAILED. Stop this branch!\n" +
>           myKey.toString() + "\n" +
>           OldIntegerSolver.this.toString() +"\n" +
>           tmpModel.toString() +"\n");
>    final GenericSolver tmpDefaultSolver = tmpModel.getDefaultSolver(); 
>    tmpDefaultSolver.solve();
>    OldIntegerSolver.this.debug(tmpDefaultSolver.toString());
>    return false;
> }
> 
> - The output produced by model.options.debug(LinearSolver.class); from this is attached. Please note that the above code calls solve() again on the model. I checked that this second run produces the same debug output and removed it from the log file. The position is marked with "[SNIP...]".
> 
> At this point I don't know how to continue, but hopefully this helps you in figuring out things when you have the time.
> 
> Cheers & have a nice week,
> Uli
> 
> Am 27.01.2015 um 17:56 schrieb Anders Peterson:
>> Most likely the rounding problem/numerical issue is with the LinearSolver.
>> 
>> I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.
>> 
>> To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.
>> 
>> I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.
>> 
>> If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.
>> 
>> If you turn on solver debugging you'll get some info regarding what goes on:
>> 
>>     model.options.debug(LinearSolver.class);
>> 
>> or
>> 
>>     model.options.debug(IntegerSolver.class);
>> 
>> 
>> or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.
>> 
>> 
>> /Anders
>> 
>> 
>> 
>>> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
>>> 
>>> 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.
>>> 
>>> ------------------------------------------------------------------------------
>>> 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.
> <Solve.java><output.txt>------------------------------------------------------------------------------
> 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

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

[Anders P. <an...@op...>]

Try modifying

model.options.objective

it is what determines when to switch to Phase2.


/Anders



> On 28 jan 2015, at 13:00, Anders Peterson <an...@op...> wrote:
> 
> Have I understood this correct: You have a model with 2 variables and 2 inequality constraints that, at a specific branch-and-bound node, demonstrates the problem?
> 
> From the output and your comments it seems clear that the problem is with the LinearSolver - it fails to discover/report that a subproblem is infeasible.
> 
> The output contains this: "Switching to Phase2 with 1 artificial variable(s) still in the basis."
> 
> ....and then I've noticed that you have not specified an objective function (any/all solutions are equally good). 
> 
> This combination could very well be something that ojAlgo fails to handle. I'll look in to this, but it has to be in a few days or so.
> 
> Have you tried specifying an objective function - preferably one that clearly favours some solutions over others? (x is better than y)
> 
> 
> /Anders
> 
> 
> 
>> On 28 jan 2015, at 10:25, Uli Schlachter <Uli...@In...> wrote:
>> 
>> Hi,
>> 
>> I tried looking into this, but I'm not familiar enough with ojAlgo's internals, I guess. Attached is what I ended up with:
>> 
>> - I reduced the model used to:
>> 
>> -10*x + -199*y <= -1
>> -10*x + -200*y <= -1
>> 
>> This still shows the same behavior as the code from my first mail.
>> 
>> - Thanks to your hint with model.options.debug(), I added the following which is what the Branch&Bounde Node where "something goes wrong" uses:
>> 
>> 1 <= x <= 20
>> y <= -1
>> 
>> -This makes the model unsolvable, but with model.options.validate = true, ojAlgo still notices that "something is wrong".
>> 
>> - Also this has the nice side effect that no branching happens anymore and thus no non-determinism due to threads. (More readable debug output!)
>> 
>> - In OldIntegerSolver, there is some code that is commented out which prints more information in case validation fails. I ended up with this:
>> 
>> if (OldIntegerSolver.this.options.validate && !tmpModel.validate(tmpResult)) {
>>   // This should not be possible. There is a bug somewhere.
>>   OldIntegerSolver.this.debug("!!!!!!!\n!!!!!!!\n" +
>>         "Node solution marked as OPTIMAL, but is actually INVALID/INFEASIBLE/FAILED. Stop this branch!\n" +
>>          myKey.toString() + "\n" +
>>          OldIntegerSolver.this.toString() +"\n" +
>>          tmpModel.toString() +"\n");
>>   final GenericSolver tmpDefaultSolver = tmpModel.getDefaultSolver(); 
>>   tmpDefaultSolver.solve();
>>   OldIntegerSolver.this.debug(tmpDefaultSolver.toString());
>>   return false;
>> }
>> 
>> - The output produced by model.options.debug(LinearSolver.class); from this is attached. Please note that the above code calls solve() again on the model. I checked that this second run produces the same debug output and removed it from the log file. The position is marked with "[SNIP...]".
>> 
>> At this point I don't know how to continue, but hopefully this helps you in figuring out things when you have the time.
>> 
>> Cheers & have a nice week,
>> Uli
>> 
>> Am 27.01.2015 um 17:56 schrieb Anders Peterson:
>>> Most likely the rounding problem/numerical issue is with the LinearSolver.
>>> 
>>> I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.
>>> 
>>> To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.
>>> 
>>> I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.
>>> 
>>> If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.
>>> 
>>> If you turn on solver debugging you'll get some info regarding what goes on:
>>> 
>>>    model.options.debug(LinearSolver.class);
>>> 
>>> or
>>> 
>>>    model.options.debug(IntegerSolver.class);
>>> 
>>> 
>>> or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.
>>> 
>>> 
>>> /Anders
>>> 
>>> 
>>> 
>>>> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
>>>> 
>>>> 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.
>>>> 
>>>> ------------------------------------------------------------------------------
>>>> 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.
>> <Solve.java><output.txt>------------------------------------------------------------------------------
>> 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

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

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

Am 28.01.2015 um 13:00 schrieb Anders Peterson:
> Have I understood this correct: You have a model with 2 variables and 2 inequality constraints that, at a specific branch-and-bound node, demonstrates the problem?

Yeah, correctly.

However, this model now demonstrates the problem without any branching 
at all.

>From the output and your comments it seems clear that the problem is with the LinearSolver - it fails to discover/report that a subproblem is infeasible.
>
> The output contains this: "Switching to Phase2 with 1 artificial variable(s) still in the basis."
>
> ...and then I've noticed that you have not specified an objective function (any/all solutions are equally good).
>
> This combination could very well be something that ojAlgo fails to handle. I'll look in to this, but it has to be in a few days or so.

Sure, no hurry. I just want to report my findings and hope that they 
will be useful to you. Feel free to ignore my problem until you have the 
time.

> Have you tried specifying an objective function - preferably one that clearly favours some solutions over others? (x is better than y)

Not yet. A quick experiment with various weights didn't change anything 
(I always got an invalid solution which was claimed to be OPTIMAL, but 
which solution I get changes with the weights).

I'm now down to this:

	ExpressionsBasedModel model = new ExpressionsBasedModel();

	model.addVariable(Variable.make("x").integer(true).
		lower(1).upper(20).weight(1));
	model.addVariable(Variable.make("y").integer(true).
		upper(-1).weight(-1));

	Expression e = model.addExpression("inequality1");
	e.setLinearFactor(0, -10);
	e.setLinearFactor(1, -199);
	e.upper(-1);

	e = model.addExpression("inequality2");
	e.setLinearFactor(0, -10);
	e.setLinearFactor(0, -10);
	e.setLinearFactor(1, -200);
	e.upper(-1);

	result = model.minimise();


With the weights as in the code above, I even get a solution x=1, y=0, 
which contradicts y's upper limit of -1. With model.options.validate = 
true, ojAlgo notices some problem and the above system is unsolvable.

Please note:
integer(true) on "y" is the key ingredient. If this variable isn't 
integer, ojAlgo correctly deduces "unsolvable". If both variables have 
.integer(false), ojAlgo also deduces "unsolvable". If this variable is 
integer, ojAlgo claims to find a solution (but validate = true still 
makes it notice its error).

So the OldIntegerSolver must somehow be involved with the problem as 
well, I just have no idea how. It must be more than just the relaxation, 
but what?

Attached is again some small java program. Feel free to ignore it, but 
it contains the above code and tries to solve this once with 
model.options.validate = true and once with = false. The result in both 
cases is different.

The results are the same with the latest git version of ojAlgo.

> /Anders

Cheers,
Uli
who can wait a week or two before looking at this again. :-)

>> On 28 jan 2015, at 10:25, Uli Schlachter <Uli...@In...> wrote:
>>
>> Hi,
>>
>> I tried looking into this, but I'm not familiar enough with ojAlgo's internals, I guess. Attached is what I ended up with:
>>
>> - I reduced the model used to:
>>
>>   -10*x + -199*y <= -1
>>   -10*x + -200*y <= -1
>>
>> This still shows the same behavior as the code from my first mail.
>>
>> - Thanks to your hint with model.options.debug(), I added the following which is what the Branch&Bounde Node where "something goes wrong" uses:
>>
>>   1 <= x <= 20
>>   y <= -1
>>
>> -This makes the model unsolvable, but with model.options.validate = true, ojAlgo still notices that "something is wrong".
>>
>> - Also this has the nice side effect that no branching happens anymore and thus no non-determinism due to threads. (More readable debug output!)
>>
>> - In OldIntegerSolver, there is some code that is commented out which prints more information in case validation fails. I ended up with this:
>>
>>   if (OldIntegerSolver.this.options.validate && !tmpModel.validate(tmpResult)) {
>>     // This should not be possible. There is a bug somewhere.
>>     OldIntegerSolver.this.debug("!!!!!!!\n!!!!!!!\n" +
>>           "Node solution marked as OPTIMAL, but is actually INVALID/INFEASIBLE/FAILED. Stop this branch!\n" +
>>            myKey.toString() + "\n" +
>>            OldIntegerSolver.this.toString() +"\n" +
>>            tmpModel.toString() +"\n");
>>     final GenericSolver tmpDefaultSolver = tmpModel.getDefaultSolver();
>>     tmpDefaultSolver.solve();
>>     OldIntegerSolver.this.debug(tmpDefaultSolver.toString());
>>     return false;
>> }
>>
>> - The output produced by model.options.debug(LinearSolver.class); from this is attached. Please note that the above code calls solve() again on the model. I checked that this second run produces the same debug output and removed it from the log file. The position is marked with "[SNIP...]".
>>
>> At this point I don't know how to continue, but hopefully this helps you in figuring out things when you have the time.
>>
>> Cheers & have a nice week,
>> Uli
>>
>> Am 27.01.2015 um 17:56 schrieb Anders Peterson:
>>> Most likely the rounding problem/numerical issue is with the LinearSolver.
>>>
>>> I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.
>>>
>>> To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.
>>>
>>> I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.
>>>
>>> If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.
>>>
>>> If you turn on solver debugging you'll get some info regarding what goes on:
>>>
>>>      model.options.debug(LinearSolver.class);
>>>
>>> or
>>>
>>>      model.options.debug(IntegerSolver.class);
>>>
>>>
>>> or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.
>>>
>>>
>>> /Anders
>>>
>>>
>>>
>>>> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
>>>>
>>>> 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.
>>>>
>>>> ------------------------------------------------------------------------------
>>>> 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.
>> <Solve.java><output.txt>------------------------------------------------------------------------------
>> 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.

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

[Anders P. <an...@op...>]

Very easy to construct test cases and debug using the code examples you sent me.

Compared to v37 that you used:

1) The IntegerSolver no longer creates subproblems that are difficult to solve (the way it did in your case).

2) The LinearSolver can now handle problem instances like the ones the IntegerSolver used to create

3) The ExpressionsBasedModel (in combination with the IntegerSolver) is now better at identifying when/if it doesn't need to call a solver at all.


I've backported the entire org.ojalgo.optimisation.* package(s) to the Java7 branch at GitHub, and I've built and uploaded v37.1 to SourceForge.


Please try this and report the results here,

/Anders



> On 28 jan 2015, at 14:55, Uli Schlachter <Uli...@In...> wrote:
> 
> Am 28.01.2015 um 13:00 schrieb Anders Peterson:
>> Have I understood this correct: You have a model with 2 variables and 2 inequality constraints that, at a specific branch-and-bound node, demonstrates the problem?
> 
> Yeah, correctly.
> 
> However, this model now demonstrates the problem without any branching at all.
> 
>> From the output and your comments it seems clear that the problem is with the LinearSolver - it fails to discover/report that a subproblem is infeasible.
>> 
>> The output contains this: "Switching to Phase2 with 1 artificial variable(s) still in the basis."
>> 
>> ...and then I've noticed that you have not specified an objective function (any/all solutions are equally good).
>> 
>> This combination could very well be something that ojAlgo fails to handle. I'll look in to this, but it has to be in a few days or so.
> 
> Sure, no hurry. I just want to report my findings and hope that they will be useful to you. Feel free to ignore my problem until you have the time.
> 
>> Have you tried specifying an objective function - preferably one that clearly favours some solutions over others? (x is better than y)
> 
> Not yet. A quick experiment with various weights didn't change anything (I always got an invalid solution which was claimed to be OPTIMAL, but which solution I get changes with the weights).
> 
> I'm now down to this:
> 
> 	ExpressionsBasedModel model = new ExpressionsBasedModel();
> 
> 	model.addVariable(Variable.make("x").integer(true).
> 		lower(1).upper(20).weight(1));
> 	model.addVariable(Variable.make("y").integer(true).
> 		upper(-1).weight(-1));
> 
> 	Expression e = model.addExpression("inequality1");
> 	e.setLinearFactor(0, -10);
> 	e.setLinearFactor(1, -199);
> 	e.upper(-1);
> 
> 	e = model.addExpression("inequality2");
> 	e.setLinearFactor(0, -10);
> 	e.setLinearFactor(0, -10);
> 	e.setLinearFactor(1, -200);
> 	e.upper(-1);
> 
> 	result = model.minimise();
> 
> 
> With the weights as in the code above, I even get a solution x=1, y=0, which contradicts y's upper limit of -1. With model.options.validate = true, ojAlgo notices some problem and the above system is unsolvable.
> 
> Please note:
> integer(true) on "y" is the key ingredient. If this variable isn't integer, ojAlgo correctly deduces "unsolvable". If both variables have ..integer(false), ojAlgo also deduces "unsolvable". If this variable is integer, ojAlgo claims to find a solution (but validate = true still makes it notice its error).
> 
> So the OldIntegerSolver must somehow be involved with the problem as well, I just have no idea how. It must be more than just the relaxation, but what?
> 
> Attached is again some small java program. Feel free to ignore it, but it contains the above code and tries to solve this once with model.options.validate = true and once with = false. The result in both cases is different.
> 
> The results are the same with the latest git version of ojAlgo.
> 
>> /Anders
> 
> Cheers,
> Uli
> who can wait a week or two before looking at this again. :-)
> 
>>> On 28 jan 2015, at 10:25, Uli Schlachter <Uli...@In...> wrote:
>>> 
>>> Hi,
>>> 
>>> I tried looking into this, but I'm not familiar enough with ojAlgo's internals, I guess. Attached is what I ended up with:
>>> 
>>> - I reduced the model used to:
>>> 
>>>  -10*x + -199*y <= -1
>>>  -10*x + -200*y <= -1
>>> 
>>> This still shows the same behavior as the code from my first mail.
>>> 
>>> - Thanks to your hint with model.options.debug(), I added the following which is what the Branch&Bounde Node where "something goes wrong" uses:
>>> 
>>>  1 <= x <= 20
>>>  y <= -1
>>> 
>>> -This makes the model unsolvable, but with model.options.validate = true, ojAlgo still notices that "something is wrong".
>>> 
>>> - Also this has the nice side effect that no branching happens anymore and thus no non-determinism due to threads. (More readable debug output!)
>>> 
>>> - In OldIntegerSolver, there is some code that is commented out which prints more information in case validation fails. I ended up with this:
>>> 
>>>  if (OldIntegerSolver.this.options.validate && !tmpModel.validate(tmpResult)) {
>>>    // This should not be possible. There is a bug somewhere.
>>>    OldIntegerSolver.this.debug("!!!!!!!\n!!!!!!!\n" +
>>>          "Node solution marked as OPTIMAL, but is actually INVALID/INFEASIBLE/FAILED. Stop this branch!\n" +
>>>           myKey.toString() + "\n" +
>>>           OldIntegerSolver.this.toString() +"\n" +
>>>           tmpModel.toString() +"\n");
>>>    final GenericSolver tmpDefaultSolver = tmpModel.getDefaultSolver();
>>>    tmpDefaultSolver.solve();
>>>    OldIntegerSolver.this.debug(tmpDefaultSolver.toString());
>>>    return false;
>>> }
>>> 
>>> - The output produced by model.options.debug(LinearSolver.class); from this is attached. Please note that the above code calls solve() again on the model. I checked that this second run produces the same debug output and removed it from the log file. The position is marked with "[SNIP...]".
>>> 
>>> At this point I don't know how to continue, but hopefully this helps you in figuring out things when you have the time.
>>> 
>>> Cheers & have a nice week,
>>> Uli
>>> 
>>> Am 27.01.2015 um 17:56 schrieb Anders Peterson:
>>>> Most likely the rounding problem/numerical issue is with the LinearSolver.
>>>> 
>>>> I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.
>>>> 
>>>> To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.
>>>> 
>>>> I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.
>>>> 
>>>> If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.
>>>> 
>>>> If you turn on solver debugging you'll get some info regarding what goes on:
>>>> 
>>>>     model.options.debug(LinearSolver.class);
>>>> 
>>>> or
>>>> 
>>>>     model.options.debug(IntegerSolver.class);
>>>> 
>>>> 
>>>> or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.
>>>> 
>>>> 
>>>> /Anders
>>>> 
>>>> 
>>>> 
>>>>> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
>>>>> 
>>>>> 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.
>>>>> 
>>>>> ------------------------------------------------------------------------------
>>>>> 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.
>>> <Solve.java><output.txt>------------------------------------------------------------------------------
>>> 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.
> <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

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

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

Thanks a lot!

I updated to v37.1, switched from .solve() (which was removed) to 
.minimise() and now my program works fine. Thanks a lot for this and for 
ojAlgo in general!

However, pressing the "Download"-button on ojalgo.org still downloads 
v37.0. I had to go to sourceforge and look for the file directly. 
Something seems to be wrong on there...?

Cheers,
Uli

Am 31.01.2015 um 21:16 schrieb Anders Peterson:
> Very easy to construct test cases and debug using the code examples you sent me.
>
> Compared to v37 that you used:
>
> 1) The IntegerSolver no longer creates subproblems that are difficult to solve (the way it did in your case).
>
> 2) The LinearSolver can now handle problem instances like the ones the IntegerSolver used to create
>
> 3) The ExpressionsBasedModel (in combination with the IntegerSolver) is now better at identifying when/if it doesn't need to call a solver at all.
>
>
> I've backported the entire org.ojalgo.optimisation.* package(s) to the Java7 branch at GitHub, and I've built and uploaded v37.1 to SourceForge.
>
>
> Please try this and report the results here,
>
> /Anders
>
>
>
>> On 28 jan 2015, at 14:55, Uli Schlachter <Uli...@In...> wrote:
>>
>> Am 28.01.2015 um 13:00 schrieb Anders Peterson:
>>> Have I understood this correct: You have a model with 2 variables and 2 inequality constraints that, at a specific branch-and-bound node, demonstrates the problem?
>>
>> Yeah, correctly.
>>
>> However, this model now demonstrates the problem without any branching at all.
>>
>>>  From the output and your comments it seems clear that the problem is with the LinearSolver - it fails to discover/report that a subproblem is infeasible.
>>>
>>> The output contains this: "Switching to Phase2 with 1 artificial variable(s) still in the basis."
>>>
>>> ...and then I've noticed that you have not specified an objective function (any/all solutions are equally good).
>>>
>>> This combination could very well be something that ojAlgo fails to handle. I'll look in to this, but it has to be in a few days or so.
>>
>> Sure, no hurry. I just want to report my findings and hope that they will be useful to you. Feel free to ignore my problem until you have the time.
>>
>>> Have you tried specifying an objective function - preferably one that clearly favours some solutions over others? (x is better than y)
>>
>> Not yet. A quick experiment with various weights didn't change anything (I always got an invalid solution which was claimed to be OPTIMAL, but which solution I get changes with the weights).
>>
>> I'm now down to this:
>>
>> 	ExpressionsBasedModel model = new ExpressionsBasedModel();
>>
>> 	model.addVariable(Variable.make("x").integer(true).
>> 		lower(1).upper(20).weight(1));
>> 	model.addVariable(Variable.make("y").integer(true).
>> 		upper(-1).weight(-1));
>>
>> 	Expression e = model.addExpression("inequality1");
>> 	e.setLinearFactor(0, -10);
>> 	e.setLinearFactor(1, -199);
>> 	e.upper(-1);
>>
>> 	e = model.addExpression("inequality2");
>> 	e.setLinearFactor(0, -10);
>> 	e.setLinearFactor(0, -10);
>> 	e.setLinearFactor(1, -200);
>> 	e.upper(-1);
>>
>> 	result = model.minimise();
>>
>>
>> With the weights as in the code above, I even get a solution x=1, y=0, which contradicts y's upper limit of -1. With model.options.validate = true, ojAlgo notices some problem and the above system is unsolvable.
>>
>> Please note:
>> integer(true) on "y" is the key ingredient. If this variable isn't integer, ojAlgo correctly deduces "unsolvable". If both variables have ..integer(false), ojAlgo also deduces "unsolvable". If this variable is integer, ojAlgo claims to find a solution (but validate = true still makes it notice its error).
>>
>> So the OldIntegerSolver must somehow be involved with the problem as well, I just have no idea how. It must be more than just the relaxation, but what?
>>
>> Attached is again some small java program. Feel free to ignore it, but it contains the above code and tries to solve this once with model.options.validate = true and once with = false. The result in both cases is different.
>>
>> The results are the same with the latest git version of ojAlgo.
>>
>>> /Anders
>>
>> Cheers,
>> Uli
>> who can wait a week or two before looking at this again. :-)
>>
>>>> On 28 jan 2015, at 10:25, Uli Schlachter <Uli...@In...> wrote:
>>>>
>>>> Hi,
>>>>
>>>> I tried looking into this, but I'm not familiar enough with ojAlgo's internals, I guess. Attached is what I ended up with:
>>>>
>>>> - I reduced the model used to:
>>>>
>>>>   -10*x + -199*y <= -1
>>>>   -10*x + -200*y <= -1
>>>>
>>>> This still shows the same behavior as the code from my first mail.
>>>>
>>>> - Thanks to your hint with model.options.debug(), I added the following which is what the Branch&Bounde Node where "something goes wrong" uses:
>>>>
>>>>   1 <= x <= 20
>>>>   y <= -1
>>>>
>>>> -This makes the model unsolvable, but with model.options.validate = true, ojAlgo still notices that "something is wrong".
>>>>
>>>> - Also this has the nice side effect that no branching happens anymore and thus no non-determinism due to threads. (More readable debug output!)
>>>>
>>>> - In OldIntegerSolver, there is some code that is commented out which prints more information in case validation fails. I ended up with this:
>>>>
>>>>   if (OldIntegerSolver.this.options.validate && !tmpModel.validate(tmpResult)) {
>>>>     // This should not be possible. There is a bug somewhere.
>>>>     OldIntegerSolver.this.debug("!!!!!!!\n!!!!!!!\n" +
>>>>           "Node solution marked as OPTIMAL, but is actually INVALID/INFEASIBLE/FAILED. Stop this branch!\n" +
>>>>            myKey.toString() + "\n" +
>>>>            OldIntegerSolver.this.toString() +"\n" +
>>>>            tmpModel.toString() +"\n");
>>>>     final GenericSolver tmpDefaultSolver = tmpModel.getDefaultSolver();
>>>>     tmpDefaultSolver.solve();
>>>>     OldIntegerSolver.this.debug(tmpDefaultSolver.toString());
>>>>     return false;
>>>> }
>>>>
>>>> - The output produced by model.options.debug(LinearSolver.class); from this is attached. Please note that the above code calls solve() again on the model. I checked that this second run produces the same debug output and removed it from the log file. The position is marked with "[SNIP...]".
>>>>
>>>> At this point I don't know how to continue, but hopefully this helps you in figuring out things when you have the time.
>>>>
>>>> Cheers & have a nice week,
>>>> Uli
>>>>
>>>> Am 27.01.2015 um 17:56 schrieb Anders Peterson:
>>>>> Most likely the rounding problem/numerical issue is with the LinearSolver.
>>>>>
>>>>> I recently discovered (and fixed) a problem that would cause the ExpressionsBasedModel to call a solver even though it had effectively already determined a solution. This is something that could potentially kick in very often while using the IntegerSolver. The problem is I can't remember exactly what the code change was. It was just something I stumbled upon while working on something else. Did a quick compare with v37 but didn't see it.
>>>>>
>>>>> To summarize what I believe. The actual "rounding issue" is with the LinearSolver, and that problem is still there in the latest development version. The reason I get a different behavior/solution is because the LinearSolver is never invoked for some subproblems. The solution is determined completely using BigDecimal-logic in the ExpressionsBasedModel class.
>>>>>
>>>>> I will not have time to look further at this during the coming week. Eventually I will construct a few test cases from the model you sent me and debug the problem, but I don't have a quick fix.
>>>>>
>>>>> If you want to look at this yourself you can either try to figure out what goes wrong with the LinearSolver or look for that ExpressionsBasedModel change, or both.
>>>>>
>>>>> If you turn on solver debugging you'll get some info regarding what goes on:
>>>>>
>>>>>      model.options.debug(LinearSolver.class);
>>>>>
>>>>> or
>>>>>
>>>>>      model.options.debug(IntegerSolver.class);
>>>>>
>>>>>
>>>>> or set breakpoints and debug the code in ExpressionsBasedModel that presolve and determine which solver to call.
>>>>>
>>>>>
>>>>> /Anders
>>>>>
>>>>>
>>>>>
>>>>>> On 27 jan 2015, at 14:10, Uli Schlachter <Uli...@In...> wrote:
>>>>>>
>>>>>> 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.
>>>>>>
>>>>>> ------------------------------------------------------------------------------
>>>>>> 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.
>>>> <Solve.java><output.txt>------------------------------------------------------------------------------
>>>> 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.
>> <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
>


-- 
"In the beginning the Universe was created. This has made a lot of
  people very angry and has been widely regarded as a bad move."