commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject Re: [math] Speeding up optimization problem?
Date Tue, 30 Apr 2013 22:32:22 GMT
On 04/30/2013 07:43 AM, Thomas Neidhart wrote:
> On 04/28/2013 11:14 PM, Thorsten Schaefer wrote:
>> Hello, 
>>
>> I just started using common math and have a performance issue with the optimization
algorithm, hoping to be able to speed it up in some way, even if this reduces the accuracy
of the results.
>>
>> My problem is as follows:
>> There are n resources and m actions that can be performed for each resource. Each
combination of action/resource has a specific payoff, which I want to maximize. I linearized
the data into rows of size (n*m). An index i has the semantics of resource=n/i and action=n%i.
Each entry in a row must be non-negative, so I added a the respective constraint to the Optimization
data. Furthermore, the sum of all actions for any resource needs to be 1, which are n additional
constraints I have. Also, any type of action needs to be performed with a relative frequency
of x% (additional constraint). And finally there are constraints for the limited number of
resources.
>> I used the SimplexSolver and can find a working solution within about half a second
(the size of the problem n*m is somewhere about 2500). The problem is, that I need to perform
the calculation very frequently and its currently too slow. I wonder if there is a way to
restrict the number of iterations for example or tell the solver to return a solution even
if there might be way better after a certain number of iterations? I tried the MaxIter constraint,
which leads only to a TooManyIterations exception without being able to retrieve the result
found so far. I also tried to initialize the solver with different epsilon values, but either
it took the same amount of iterations (and time) or it finished with a NoFeasableSolutionException.
>> So my question is if there is a way to get non-optimal solutions, but those quicker?
>> If it would speed up the solution finding process, I could live with a solution where
we restrict the possible results to booleans, i.e., an action for any resource is either performed
never or always. 
> 
> Hi Thorsten,
> 
> at the moment there is no way to get the best solution so far, if the
> maximum number of iterations has been reached.
> 
> We could add a feature like this (as already several other people have
> requested it).

btw. I have created an issue for this:

https://issues.apache.org/jira/browse/MATH-970

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org


Mime
View raw message