Re: [ojAlgo-user] QuadraticSolver with unsatisfiable constraints

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

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.
________________________________________________________________

Re: [ojAlgo-user] QuadraticSolver with unsatisfiable constraints

Mathematics, linear algebra and optimisation

Re: [ojAlgo-user] QuadraticSolver with unsatisfiable constraints