On 01/17/2013 04:21 PM, Gilles Sadowski wrote: > Hi Thomas. > > On Thu, Jan 17, 2013 at 03:59:20PM +0100, Thomas Neidhart wrote: >> On Thu, Jan 17, 2013 at 3:52 PM, Gilles Sadowski < >> gil...@harfang.homelinux.org> wrote: >> >>> On Thu, Jan 17, 2013 at 02:28:56PM +0100, Thomas Neidhart wrote: >>>> Hi, >>>> >>>> by investigating a recent issue (MATH-930), I discovered that the newly >>>> introduced LinearConstraintSet stores the constraints internally in a >>>> HashSet. >>>> This leads to undeterministic behavior as the iteration order of >>>> constraints is not fixed (especially between different JRE versions). >>>> >>>> TBH, I never reviewed this change and I am a bit surprised to see it. >>> Imho >>>> there is no need to have a Set here, and would prefer to change this to a >>>> list implementation. >>> >>> -1 >>> Unless the order of iteration is a requirement of the mathematical >>> description of the algorithm. >>> If so: >>> * This requirement should appear prominently in the Javadoc.[1] >>> * Please discard the rest of this mail. >>> If not, then the order is only an implementation detail (IOW, with infinite >>> precision, the solution would not change with different iteration orders), >>> I would be cautious to rely on a specific implementation of the container >>> used to store input data. >>> >>> Maybe that the behaviour described in MATH-930 indicates an inherent >>> weakness of the algorithm (or too stringent requirements); if so, the >>> better >>> solution is probably not to rely on whether side-effects are visible or >>> not. >>> >>> Also, I note that in the (deprecated) package >>> "o.a.c.m.optimization.linear", >>> the constraints are passed to "optimize" as a >>> Collection<LinearConstraint> >>> IIUC, the same behaviour could thus be produced by a user who'd call >>> optimize several times, passing the same set of constraints but stored in a >>> different order in the Collection. >>> >> >> Hi Gilles, >> >> yes I understand your concerns, and the problem is two-fold: >> >> * make the algorithm behave deterministic in all environments >> (I do not want to spend each time 1 day debugging why it works in one >> case or another) > > I can understand; but the suggested fix is not a fix (IIUC), it only hides > the problem. > >> * fix the obvious numerical stability problem with certain ordering of >> constraints >> >> Although before the parameter was passed as a Collection, most people >> actually used a List or something similar. >> At least you had control over it, > > I think that this is called "false sense of security". > In this instance you run a program in its unstable regime, and feel secure > that the List container will not show you how untrustworthy the result is. > >> now it is just a HashSet, inside a CM >> class which you can not control. > > As an implementation detail, this is all for the better. > >> So I would really prefer to at least change it to a LinkedHashSet with >> deterministic iteration order, and investigate further the other problem. > > Feel free to use whatever in order to investigate, but don't bury the > problem by changing the implementation. IMHO, it is a _feature_ if the > current implementation uncovered a numerical bug. > > If we do not have the resources to dig further into the real problem, we can > circumscribe it by indicating which interval of epsilon values are > considered trustworthy (and declining all resposibility if user try pushing > the implementation too far).
Well, I do disagree. I do not want to have a situation where users get different results with each run. I want to have deterministic behavior for deterministic algorithms. Yes, there are numerical stability issues, which in this case can be treated by relaxing the convergence criteria as the user did. Otoh, we should have thorough testing where a permutation of the linear constraints could be a useful addition to detect more such issues. For such a flexible tool like the SimplexSolver, there will always be problems where the solution is difficult to find, and will require some tuning. Even octave (using the very good and mature glpk library) did not find the optimal solution in this case. Thomas --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
