Re: [math] Speeding up optimization problem?

[Thomas Neidhart <th...@gmail.com>]

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