Re: [ojAlgo-user] solving a linear optimization problem with ojAlgo ?

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

On 5 jan 2008, at 08.28, Andreas Andreakis wrote:

> Hi,
>
> there can be a feasible solution, if a vector v can be expressed as =20=

> a convex combination of the vectors v1,...,vn
>
> like this: v =3D c1*v1+c2*v2+...+cn*vn

Then the "best fit" solution will be feasible (perfect fit).

> My problem is actually: given the vectors v1,,.,vn and given the =20
> vector v, I need to find the coefficients c1,,.,cn which are valid.
> A valid solution exists if v is inside the convex set, which is =20
> spanned by the vectors v1,..,vn.
>
> If the vector v can not be expressed as a convex combination of =20
> v1,,.,vn, that there is no possible solution to this problem.
>
>
> I have already a solution in maple for this, using a Linear =20
> ProgrammingSolver:
> LPSolve(NoUserValue, [NoUserValue, NoUserValue, A, v], assume =3D =20
> nonnegative)[2]
>
> where A is a Matrix containing the vectors v1,..,vn. Where every =20
> vector is a column in the matrix.
> v is a vector (the actual v vector of the description above)

ojAlgo does not have an LP solver, but a QP solver that you should be =20=

able to use in roughly the same way.

> However, I hope to find a java library which is capable of the same ;)

You can do this with ojAlgo, It wont be as easy as with Maple. You =20
have to know and code a little more.

/Anders


> On Jan 5, 2008 1:39 AM, Anders Peterson < anders@> wrote:
> If you you have 50 variables and several hundred equations there
> typically is no feasible solution.
>
> You can get a "best fit" solution using the QR or SVD decompositions
> but those cannot handle the constraints/inequalities that the
> variables must be non-negative. You'll have to invent something to
> handle that.
>
> /Anders
>
> On 4 jan 2008, at 16.51, Andreas Andreakis wrote:
>
> > hi,
> >
> > I want to find a solution to the following problem:
> >
> > (explained by example)
> > 1 *c1 + 4 * c2 + 4* c3 + 4 * c4 =3D 2.5
> > 1 *c1 + 4 * c2 + 1* c3 + 4 * c4 =3D 3.0
> >
> > here the constraints:
> > 1) c1+c2+c3+c4 =3D 1 (of course this could be expressed as an
> > additional equation: c1 + c2 + c3 + c4 =3D 1.0)
> > 2) c1,c2,c3 and c4 are all positive
> >
> > Important is that I need only one and feasible solution, thus the
> > computation should be as fast as possible. So there is no need to
> > search for every possible result.
> > And it needs to work with doubles (not only integers, because some
> > libraries work only with integers)
> >
> > Actually the solution needs to scale for several dozens c=B4s ( =
there
> > will not be only 4 like c1,c2,c3,c4), but more like 50 c1,
> > c2,...,c49, c50
> > And there will not be only two equations (like in the example) but
> > several hundred.
> >
> >
> > So the questions are:
> > 1) can I find a solution using ojAlgo ?
> > 2) how will the performance be ?
> > 3) could you give me a code snipped which is able to compute the
> > given example ? (I will generalize it then myself)
> >
> > kind regards,
> > Andreas
> > =20
> ----------------------------------------------------------------------
> > ---
> > This SF.net email is sponsored by: Microsoft
> > Defy all challenges. Microsoft(R) Visual Studio 2005.
> > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> > _______________________________________________
> > ojAlgo-user mailing list
> > ojA...@li...
> > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
> ----------------------------------------------------------------------=20=

> ---
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2005.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
> ----------------------------------------------------------------------=20=

> ---
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2005.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/=20
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user