commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thorsten Schaefer <em...@thorstenschaefer.de>
Subject [math] Speeding up optimization problem?
Date Sun, 28 Apr 2013 21:14:51 GMT
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. 

Regards,

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


Mime
View raw message