Hi Thorsten,
thanks for the sample code.
Something that may be helpful for you:
You compute the relative action frequencies for each resource and then add
a constraint that they have to be equal to the expected probabilities for
this action in total. This is quite a hard constraint, try to relax it like
that:
// add constraints for action frequencies
for (int action=0; action<numberOfActions; action++) {
constraints.add(new
LinearConstraint(coefficientActionFrequencies[action], Relationship.LEQ,
actionProbabilities[action] + 0.01));
constraints.add(new
LinearConstraint(coefficientActionFrequencies[action], Relationship.GEQ,
actionProbabilities[action] - 0.01));
}
Another observation that I have made, the resources array does contain a
lot of zeros, but when creating the constraint that each resource must have
one action assigned this is not taken into account (my understanding is
that when in the resource array the corresponding entry is 0, this action
can not be assigned to this resource), so I added also this:
if (resources[bucket][action] != 0.0) {
constraintValuesAction[currentIndex] = 1;
}
this means only the actions that are available for this resource are used.
With these changes it runs a bit faster on my machine, but the absolute
values are of course not comparable.
Thomas
On Thu, May 2, 2013 at 8:09 PM, Thorsten Schaefer <[email protected]
> wrote:
> Thanks Thomas for the information so far. It took me some time to create
> an example w/o dependencies, but here is one smaller problem which is
> self-contained:
> http://pastebin.com/7QVMMBpA
>
> Solving it on my laptop takes around 400ms, but as said, there are several
> hundred similar problems to solve and that in many iterations as the input
> (resources and payoffs) change. Note that I first solve the problem
> regularly using simplex, and then round the values to booleans to get a
> heuristic - even though it might not be conform exactly to the restrictions
> its a good enough heuristic for me; if there are faster heuristics for such
> a problem structure I'd be happy to hear them, but as far as I know Integer
> programming is considered harder in general.
> One observation I also made is: if I calculate the problem and then do it
> again with the same input value, giving the optimal solution as an initial
> guess, the runtime doesn't change at all. I suspect that the initial guess
> does not have any impacts on the simplex solver, but it might make sense to
> warn the user about it.
>
> Cheers,
>
> Thorsten
>
>
> On Apr 30, 2013, at 2:43 AM, Thomas Neidhart <[email protected]>
> 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).
> >
> > Could you also attach your example somewhere, so I can take a look at it
> > and maybe provide some more optimization tips?
> >
> > Thanks,
> >
> > Thomas
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: [email protected]
> > For additional commands, e-mail: [email protected]
> >
>
>
