Re: [ojAlgo-user] Quadratic Program fails

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

After writing that I felt I had to investigate how large problems ojAlgo can handle...

Problems structured as in your test case are easy to solve because the inequality constraints doesn't actually affect the solution.

dim=2 =>
	OPTIMAL in 0.042362s
dim=4 =>
	OPTIMAL in 6.18E-4s
dim=8 =>
	OPTIMAL in 6.97E-4s
dim=16 =>
	OPTIMAL in 0.001164s
dim=32 =>
	OPTIMAL in 0.003616s
dim=64 =>
	OPTIMAL in 0.021859s
dim=128 =>
	OPTIMAL in 0.026166s
dim=256 =>
	OPTIMAL in 0.02064s
dim=512 =>
	OPTIMAL in 0.073304s
dim=1024 =>
	OPTIMAL in 0.508432s
dim=2048 =>
	OPTIMAL in 3.590416s
dim=4096 =>
	OPTIMAL in 24.111358s
dim=8192 =>
	OPTIMAL in 186.600192s
dim=16384 =>
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at org.ojalgo.array.PrimitiveArray.<init>(PrimitiveArray.java:326)


If you start adding inequality constraints that actually affect the solution performance will be very different, and if in fact the inequalities make the problem infeasible the algorithm may not be able to recognize that.

/Anders


On 9 jan 2014, at 22:29, Anders Peterson <an...@op...> wrote:

> On 9 jan 2014, at 21:55, Nico Potyka <Nic...@gm...> wrote:
> 
>> Thanks again and sorry for wasting your time. For some reason, there is no exception thrown on my computer and executing the code yields "FAILED". However, after switching to a column vector my general implementation works perfectly fine.  
> 
> Yes, the solver swallowed the exception, but did output it to the console. You displayed the solver state using System.out.println(); Didn't you see the exception there?
> 
> 
>> I took your advice, but I need to perform some matrix operations to determine Q in general and therefore prefered the following example from the unit tests. Furthermore, the problems can become quite large. In fact, most interesting problem instances have hundreds of variables and I can easily construct examples with thousands or millions of variables. Therefore I figured that generating a variable object for each optimization variable might not be the best way to go. But I will give it a try.
> 
> ExpressionsBasedModel is "sparse" it only stores the nonzero problem parameters, so it's not as bad as you may think. The solvers are "dense".
> 
> The general advice would be to initially use ExpressionsBasedModel and then maybe switch to a specific solver if necessary and possible.
> 
> ojAlgo's quadratic solver cannot handle millions of variables! 20000 or so would be an absolute limit and I imagine it will struggle with numerical and performance issues long before that. I don't know where the practical limit is - it depends on your specific case. The largest successful cases I know of has hundreds of variables (not thousands). Please let me know how large models you manage to solve.
> 
> /Anders
> 
> 
> 
>> Best regards 
>> Nico
>> 
>> 
>> 
>> 
>> 
>> Gesendet: Donnerstag, 09. Januar 2014 um 21:07 Uhr
>> Von: "Anders Peterson" <an...@op...>
>> An: "ojAlgo ojAlgo" <oja...@li...>
>> Betreff: Re: [ojAlgo-user] Quadratic Program fails
>> When I run that code I get an ArrayIndexOutOfBoundsException, and that's because "C" should be a column vector rather than a row vector.
>> 
>> Had you taken my advice and used ExpressionsBasedModel this wouldn't have happened. That class actually does something for you:
>> 
>> 1) You can model your problems without worrying about specific solver requirements.
>> 2) It knows which solver to use.
>> 3) It knows how to use that solver.
>> 4) It has a presolver that tries to simplify the problem before invoking a solver (sometimes it turns out there is no need to invoke a solver at all).
>> 5) When/if needed it scales problem parameters, before creating solver specific data structures, to minimize numerical problems in the solvers.
>> 6) It's the only way to access the integer solver.
>> 
>> /Anders
>> 
>> 
>> On 9 jan 2014, at 16:53, Nico Potyka <Nic...@gm...> wrote:
>> 
>>> Hi,
>>> 
>>> I tried to use ojAlgo to implement a norm minimization problem, but the solver fails even for very simple instances. The following example is one particular simple instance. Q is the identity matrix, C the zero vector. The constraints express that the solution is a probability function (AE for normalization and AI for non-negativity). Q is positive definite and the solution should be (0.5, 0.5), but qSolver fails.
>>> 
>>> 
>>> PrimitiveDenseStore tmpQ = PrimitiveDenseStore.FACTORY.rows(new double[][]{{1, 0},{0, 1}});
>>> PrimitiveDenseStore tmpC = PrimitiveDenseStore.FACTORY.rows(new double[][]{{0, 0}});
>>> 
>>> PrimitiveDenseStore tmpAE = PrimitiveDenseStore.FACTORY.rows(new double[][]{{1, 1}});
>>> PrimitiveDenseStore tmpBE = PrimitiveDenseStore.FACTORY.rows(new double[][]{{1}});
>>> 
>>> PrimitiveDenseStore tmpAI = PrimitiveDenseStore.FACTORY.rows(new double[][]{{-1, 0}, {0, -1}});
>>> PrimitiveDenseStore tmpBI = PrimitiveDenseStore.FACTORY.rows(new double[][]{{0}, {0}});
>>> 
>>> QuadraticSolver qSolver = new QuadraticSolver.Builder(tmpQ, tmpC).equalities(tmpAE, tmpBE).inequalities(tmpAI, tmpBI).build();
>>> 
>>> Optimisation.Result tmpResult = qSolver.solve();
>>> System.out.println(tmpResult.getState());
>>> 
>>> 
>>> Is there something wrong in my code or is there a problem with the quadratic solver?
>>> 
>>> Thanks
>>> Nico
>>> 
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> ojAlgo-user mailing list
>>> ojA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]
>>> 
>>> 
>> 
>> 
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today.
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]
>> _______________________________________________
>> ojAlgo-user mailing list
>> ojA...@li...
>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]
>> 
>> ------------------------------------------------------------------------------
>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>> Critical Workloads, Development Environments & Everything In Between.
>> Get a Quote or Start a Free Trial Today. 
>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>> _______________________________________________
>> ojAlgo-user mailing list
>> ojA...@li...
>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user