Re: [ojAlgo-user] QuadraticSolver with unsatisfiable constraints

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

I modified the solve-method to be

    void solve() {

        final QuadraticSolver solver = new QuadraticSolver.Builder(model).build();
        final Result result = solver.solve();

        if (result.getSolution() != null) {
            final boolean validated = model.validateSolution(result.getSolution(), solver.options.solutionContext);
            if (result.getState().isNotLessThan(State.FEASIBLE)) {
                final String message = "State: " + result.getState() + ", validated: " + validated;
                Assert.assertTrue(message, validated);
            } else {
                final String message = "State: " + result.getState() + ", validated: " + validated;
                Assert.assertFalse(message, validated);
            }
        } else {
            Assert.assertFalse("No solution but state FEASIBLE", result.getState().isNotLessThan(State.FEASIBLE));
        }
    }

Does that seem correct to you?


Then, when I run the tests I only get a failure (failed test) with test "2", and I get no error (like an NPE).

Tests "2" and "5" takes very long - long enough to suggest that there is something the algorithm can't handle.

I see no problem with test "1", "3", "4" or "6".

Do you agree with this?


Have you tried setting different contexts for "options.solutionContext"? I don't believe the "options.problemContext" affect anything with the QuadraticSolver (yet).

/Anders


On 16 nov 2009, at 16.30, Pierre AUSLAENDER wrote:

> 
> Sure, here it is (and sorry, the NPE was not in the SVD, but in the validateSolution) 
> 
> test1: OK 
> test2: KO with STATE = FAILED, VALIDATION = TRUE 
> test3: KO with NPE in ExpressionBasedModel.validateSolution 
> test4: OK 
> test5: KO with STATE = OPTIMAL, VALIDATION = FALSE 
> test6: KO with NPE in ExpressionBasedModel.validateSolution 
> 
> /* 
>  * (c) Copyright Pictet & Cie 2009 
>  */ 
> package com.pictet.pam.bam.test; 
> 
> import java.math.BigDecimal; 
> import java.util.Arrays; 
> 
> import org.junit.Assert; 
> import org.junit.Test; 
> import org.ojalgo.constant.BigMath; 
> import org.ojalgo.optimisation.Expression; 
> import org.ojalgo.optimisation.State; 
> import org.ojalgo.optimisation.Variable; 
> import org.ojalgo.optimisation.OptimisationSolver.Result; 
> import org.ojalgo.optimisation.quadratic.QuadraticExpressionsModel; 
> import org.ojalgo.optimisation.quadratic.QuadraticSolver; 
> 
> /** 
>  * @author pauslaender 
>  * 
>  */ 
> public class OptimisationSolverTest { 
> 
>         Variable[] vars; 
>         BigDecimal[] point; 
>         QuadraticExpressionsModel model; 
> 
>         /** 
>          * 
>          * @param numberOfVars greater than 6 
>          */ 
>         void setupModel(int numberOfVars) { 
>                 if (numberOfVars < 6) { 
>                         throw new IllegalArgumentException("numberOfVars must be >= 6 !!!"); 
>                 } 
>                 // 
>                 // variables 
>                 // 
>                 vars = new Variable[numberOfVars]; 
>                 vars[0] = new Variable("x0").lower(new BigDecimal(00.0)).upper(new BigDecimal(15.0)); 
>                 vars[1] = new Variable("x1").lower(new BigDecimal(17.0)).upper(new BigDecimal(27.0)); 
>                 vars[2] = new Variable("x2").lower(new BigDecimal(19.0)).upper(new BigDecimal(34.0)); 
>                 vars[3] = new Variable("x3").lower(new BigDecimal(25.0)).upper(new BigDecimal(48.0)); 
>                 vars[4] = new Variable("x4").lower(new BigDecimal(05.0)).upper(new BigDecimal(18.0)); 
>                 vars[5] = new Variable("x5").lower(new BigDecimal(02.0)).upper(new BigDecimal(09.0)); 
>                 for (int i = 6; i < numberOfVars; ++i) { 
>                         vars[i] = new Variable("x" + i).level(BigMath.ZERO); 
>                 } 
>                 // 
>                 // minimise distance to this point 
>                 // 
>                 point = new BigDecimal[numberOfVars]; 
>                 point[0] = new BigDecimal(1.0); 
>                 point[1] = new BigDecimal(25.0); 
>                 point[2] = new BigDecimal(33.0); 
>                 point[3] = new BigDecimal(29.0); 
>                 point[4] = new BigDecimal(9.0); 
>                 point[5] = new BigDecimal(2.0); 
>                 for (int i = 6; i < numberOfVars; ++i) { 
>                         point[i] = new BigDecimal(0.0); 
>                 } 
>                 // 
>                 // model 
>                 // 
>                 model = new QuadraticExpressionsModel(vars); 
>                 // 
>                 // objective function 
>                 // 
>                 { 
>                         Expression e = model.addOffsetExpression("objective", Arrays.asList(point)); 
>                         e.setContributionWeight(BigMath.HALF); 
>                 } 
>                 // 
>                 // sum(xi) = 100.0 
>                 // 
>                 { 
>                         Expression e = model.addSimpleWeightExpression("sum(xi) = 100.0"); 
>                         e.level(BigMath.HUNDRED); 
>                 } 
>                 // 
>                 // x1 + x2 <= 45 
>                 // 
>                 { 
>                         Expression e = model.addEmptyLinearExpression("x1 + x2 <= 45.0"); 
>                         e.setLinearFactor(1, BigMath.ONE); 
>                         e.setLinearFactor(2, BigMath.ONE); 
>                         e.lower(BigMath.ZERO).upper(new BigDecimal(45.0)); 
>                 } 
>                 // 
>                 // x4 - 2*x5 = 0 
>                 // 
>                 { 
>                         Expression e = model.addEmptyLinearExpression("x4 - 2*x5 = 0"); 
>                         e.setLinearFactor(4, BigMath.ONE); 
>                         e.setLinearFactor(5, BigMath.TWO.negate()); 
>                         e.level(BigMath.ZERO); 
>                 } 
>         } 
> 
>         @Test 
>         public void test1() { 
>                 setupModel(6); 
>                 solve(); 
>         } 
> 
>         @Test 
>         public void test2() { 
>                 setupModel(6); 
>                 vars[3].level(new BigDecimal(40.0)); 
>                 vars[4].level(new BigDecimal(18.0)); 
>                 solve(); 
>         } 
> 
>         @Test 
>         public void test3() { 
>                 setupModel(6); 
>                 vars[3].level(new BigDecimal(48.0)); 
>                 vars[4].level(new BigDecimal(18.0)); 
>                 vars[5].level(new BigDecimal(5.0)); 
>                 solve(); 
>         } 
> 
>         @Test 
>         public void test4() { 
>                 setupModel(42); 
>                 solve(); 
>         } 
> 
>         @Test 
>         public void test5() { 
>                 setupModel(42); 
>                 vars[3].level(new BigDecimal(40.0)); 
>                 vars[4].level(new BigDecimal(18.0)); 
>                 solve(); 
>         } 
> 
>         @Test 
>         public void test6() { 
>                 setupModel(42); 
>                 vars[3].level(new BigDecimal(40.0)); 
>                 vars[4].level(new BigDecimal(18.0)); 
>                 vars[5].level(new BigDecimal(5.0)); 
>                 solve(); 
>         } 
> 
>         void solve() { 
>                 QuadraticSolver solver = new QuadraticSolver.Builder(model).build(); 
>                 // QuadraticSolver.DEBUG = true; 
>                 // System.out.println(model); 
>                 Result result = solver.solve(); 
>                 // System.out.println(result); 
>                 // System.out.println(result.getSolution().toListOfElements()); 
>                 boolean validated = model.validateSolution(result.getSolution(), solver.options.solutionContext); 
>                 if (result.getState() == State.OPTIMAL) { 
>                         String message = "State: " + result.getState() + ", validated: " + validated; 
>                         Assert.assertTrue(message, validated); 
>                 } else { 
>                         String message = "State: " + result.getState() + ", validated: " + validated; 
>                         Assert.assertFalse(message, validated); 
>                 } 
>         } 
> 
> } 
> 
> 
> 
> "Anders Peterson" <an...@op...> 
> 16.11.2009 15:42
> Please respond to
> oja...@li...
> 
> To
> oja...@li...
> cc
> Subject
> Re: [ojAlgo-user] QuadraticSolver with unsatisfiable constraints
> 
> 
> 
> Warning: this message has been delivered from outside the Pictet Group. If the content is related to banking matters, please apply the same procedure as for an incoming Fax or letter.
> Attention: Ce message provient de l'extérieur du Groupe Pictet. S'il possède un caractère bancaire, veuillez  le traiter de la même manière qu'un Fax ou une lettre entrante.
> 
> 
> 
> 
> 
> Can you perhaps give me 2 test cases; 1 for the NPE case and 1 for the  
> incorrect state case. /Anders
> 
> 
> On 16 nov 2009, at 14.33, Pierre AUSLAENDER wrote:
> 
> >
> > Hello Anders,
> >
> > Thanks a lot for the swift reply.
> >
> > I 've played with the latest snapshot and here are my findings:
> > - Most of the times now, when the constraints cannot be satisfied,  
> > the solver terminates with the state FAILED, which is what one would  
> > expect, albeit after a great lot of iterations.
> > - Sometimes however, it terminates with the state OPTIMAL, and the  
> > model validation returns FALSE, same as before I took the snapshot.
> > - Sometimes as well, it throws a NPE in the SVD (after saying that  
> > LU is not solvable).
> >
> > I'm trying to build a simple JUnit and send it to you.
> >
> > Kind regards,
> > Pierre
> >
> >
> >
> > "Anders Peterson" <an...@op...>
> > 16.11.2009 12:57
> > Please respond to
> > oja...@li...
> >
> >
> > To
> > oja...@li...
> > cc
> > Subject
> > Re: [ojAlgo-user] QuadraticSolver with unsatisfiable constraints
> >
> >
> >
> > Warning: this message has been delivered from outside the Pictet  
> > Group. If the content is related to banking matters, please apply  
> > the same procedure as for an incoming Fax or letter.
> > Attention: Ce message provient de l'extérieur du Groupe Pictet. S'il  
> > possède un caractère bancaire, veuillez  le traiter de la même  
> > manière qu'un Fax ou une lettre entrante.
> >
> >
> >
> >
> >
> > On 16 nov 2009, at 11.06, Pierre AUSLAENDER wrote:
> >
> > > Hello,
> > >
> > > Thank you for this library, which is a joy to use - once I got over
> > > the lack of documentation.
> > >
> > > I'm using the QuadraticSolver (ActiveSetSolver) on a least squares
> > > minimisation problem, under a set of linear constraints. When the
> > > constraints can be satisfied, it works perfectly. However, when the
> > > constraints cannot be satisfied, the solver still returns with an
> > > OPTIMAL state after a few iterations. I was puzzled until I
> > > discovered the QuadraticSolver.validateSolution(...) methods, which
> > > I can use to effectively test the solution against the constraints.
> > >
> > > Is this the way it is supposed to work, or did I do something wrong?
> > > I would have expected the solver to FAIL instead.
> >
> >
> > I recently fixed a couple of bugs related to this. Get the latest
> > snapshot download from Source Forge, and try if that solves your
> > problem. If it doesn't I'd like you to give me (junit) test case.
> >
> >
> > > As an aside question, there is the following JavaDoc comment on
> > > ExpressionBasedModel.addConstraint(final String aName, ....): Note
> > > that only the first constraint you add will be used by the solver.
> > > What does this comment mean? Is it simply related to the uniqueness
> > > of the constraint name, or has it wider implications?
> >
> >
> > That comment should have been removed. It was only relevant for the
> > now removed/replaced KnapsckSolver. That solver could only use 1
> > constraint - the first one you added. I'll correct the javadoc comment
> > now.
> >
> >
> > /Anders
> >
> >
> >
> > > Thank you,
> > > Pierre
> > >
> > > ________________________________________________________________
> > >
> > > PAM S.A Geneva                           Tel. +41 (0)58 323 3333
> > > 60, route des Acacias                    Fax  +41 (0)58 323 2324
> > > CH-1211 GENEVE 73                        http://www.pictet.com/
> > > ________________________________________________________________
> > >
> > > This document should only be read by those persons to whom it is
> > > addressed  and  is  not intended to be relied upon by any person
> > > without  subsequent written confirmation of its contents. If you
> > > have  received  this  e-mail message in error, please destroy it
> > > and delete it from your computer.
> > > Any  form of  reproduction, dissemination, copying,  disclosure,
> > > modification,  distribution  and/or  publication  of this E-mail
> > > message is strictly prohibited.
> > > ________________________________________________________________
> > >
> > > Pictet reserves the right  to  monitor  and  record business and
> > > personal communications. By  responding to an email or call from
> > > a Pictet  employee  you  are  taken  to  have  consented to such
> > > monitoring and recording.
> > > ________________________________________________________________
> > >
> > >  
> > ------------------------------------------------------------------------------
> > > Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> > > 30-Day
> > > trial. Simplify your report design, integration and deployment - and
> > > focus on
> > > what you do best, core application coding. Discover what's new with
> > > Crystal Reports now.  http://p.sf.net/sfu/bobj-july_______________________________________________
> > > ojAlgo-user mailing list
> > > ojA...@li...
> > > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> >
> >
> > ------------------------------------------------------------------------------
> > Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> > 30-Day
> > trial. Simplify your report design, integration and deployment - and  
> > focus on
> > what you do best, core application coding. Discover what's new with
> > Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> > _______________________________________________
> > ojAlgo-user mailing list
> > ojA...@li...
> > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> >
> >
> >
> > ________________________________________________________________
> >
> > PAM S.A Geneva                           Tel. +41 (0)58 323 3333
> > 60, route des Acacias                    Fax  +41 (0)58 323 2324
> > CH-1211 GENEVE 73                        http://www.pictet.com/
> > ________________________________________________________________
> >
> > This document should only be read by those persons to whom it is
> > addressed  and  is  not intended to be relied upon by any person
> > without  subsequent written confirmation of its contents. If you
> > have  received  this  e-mail message in error, please destroy it
> > and delete it from your computer.
> > Any  form of  reproduction, dissemination, copying,  disclosure,
> > modification,  distribution  and/or  publication  of this E-mail
> > message is strictly prohibited.
> > ________________________________________________________________
> >
> > Pictet reserves the right  to  monitor  and  record business and
> > personal communications. By  responding to an email or call from
> > a Pictet  employee  you  are  taken  to  have  consented to such
> > monitoring and recording.
> > ________________________________________________________________
> >
> > ------------------------------------------------------------------------------
> > Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> > 30-Day
> > trial. Simplify your report design, integration and deployment - and  
> > focus on
> > what you do best, core application coding. Discover what's new with
> > Crystal Reports now.  http://p.sf.net/sfu/bobj-july_______________________________________________
> > ojAlgo-user mailing list
> > ojA...@li...
> > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> 
> 
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> 
> 
> 
> ________________________________________________________________
> 
> PAM S.A Geneva                           Tel. +41 (0)58 323 3333
> 60, route des Acacias                    Fax  +41 (0)58 323 2324
> CH-1211 GENEVE 73                        http://www.pictet.com/
> ________________________________________________________________
> 
> This document should only be read by those persons to whom it is
> addressed  and  is  not intended to be relied upon by any person
> without  subsequent written confirmation of its contents. If you
> have  received  this  e-mail message in error, please destroy it
> and delete it from your computer.
> Any  form of  reproduction, dissemination, copying,  disclosure,
> modification,  distribution  and/or  publication  of this E-mail
> message is strictly prohibited.
> ________________________________________________________________
> 
> Pictet reserves the right  to  monitor  and  record business and
> personal communications. By  responding to an email or call from
> a Pictet  employee  you  are  taken  to  have  consented to such
> monitoring and recording.
> ________________________________________________________________
> 
> 
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july_______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user