Ok, I just pushed my code to the fork at https://github.com/cherullo/commons-math. Merging with SolutionCallback was straightforward, and the standard tests passed. I already saw issues in the new code, but right now I'd like your opinion on the current interface (ie. public SimplexSolution optimizeExtra(OptimizationData...)). It doesn't seem to fit well with the rest. Thoughts?
[]s Renato C. On Wed, Nov 20, 2013 at 1:21 PM, Renato Cherullo <cheru...@gmail.com> wrote: > Hi guys, > > It's been a while since I raised this issue. I actually solved this and I > want to contribute it back. > I implemented a new public method in SimplexSolver called optimizeExtra, > that returns a SimplexSolution containing: > > 1) PointValuePair solution; > The optimal solution. > > 2) HashMap<LinearConstraint, ExtraConstraintInfo> extraConstraintInfo; > A mapping of the user created LinearConstraints to a class containing > the constraint's RHS sensitivity and shadow price. > > 3) CoefficientBounds[] coefficientSensitivity; > The sensitivity of each coefficient in the objective function. > > I believe that the code is good, mathematically speaking, because I > checked the results (both manually and automatically) against another > library. > But, since this was done in a certain problem domain, there may still be > bugs in untested scenarios. > Unfortunately, I can't bring those automated tests without bringing a lot > of code related to that domain. We also checked the results after some > post-processing that could mask some very palpable errors, making those > tests unsuitable for general testing. > I'll implement new end-to-end tests. > > I just created a fork at https://github.com/cherullo/commons-math. I'll > email you guys as soon as I finish merging my changes so we can discuss > this further. > > I saw that the SolutionCallback was implemented. Since my approach also > has it's merits, I'll try my best to merge both. > Comments are welcome :-) > > []s Renato C. > > > > > > > > > On Tue, Sep 10, 2013 at 2:42 AM, Thomas Neidhart < > thomas.neidh...@gmail.com> wrote: > >> On 09/09/2013 10:37 PM, Thomas Neidhart wrote: >> > On 09/09/2013 09:02 PM, Renato Cherullo wrote: >> >> Hi all, >> >> >> >> I need to implement a way to recover some important information from >> >> SimplexSolver's final tableau. >> >> I'll start by the shadow price, which seems very straight forward. If I >> >> understand it correctly, I must: >> >> 1- Store the original LinearConstraints in the same order as the >> normalized >> >> constraints. >> >> The LinearConstraintSet stores the constraints in a HashSet, so care >> >> must be taken to ensure ordering. >> >> 2- After the optimization, given a constraint, I must determine the >> >> tableau's column relative to the constraint's slack variable and >> return the >> >> value on the objective function row. >> >> The column index should be getSlackVariableOffset() plus the number >> of >> >> LEQ and GEQ constraints present in the original constraints list >> before the >> >> given constraint. >> >> >> >> I'm kinda new to the Simplex method, so this may be wrong too. Looking >> at >> >> the code, I think that the logic in (2) should be implemented in >> >> SimplexSolver, but I'm not sure about (1), since: >> >> >> >> A- SimplexSolver doesn't store the SimplexTableau instance used during >> >> optimization. Since SS is immutable, it really shouldn't. So I must >> return >> >> the shadow price of every constraint along the optimal PointValuePair, >> >> creating another overload of the doOptimize method (or some other new >> >> method). >> > >> > There are related requests from other users (see MATH-970), which want >> > to retrieve the best solution found so far in case the optimization >> > reaches the iteration limit. Right now it is not possible to retrieve >> > the last computed tableau but we will need to change that in some way. >> > >> > When we have this, adding a method to retrieve the index of the slack >> > variable should be trivial. >> >> One way to achieve this without breaking the current API would be to >> define a separate OptimizationData object that acts as a callback: >> >> e.g. SolutionCallback, with an interface like this: >> >> updateTableau(SimplexTableau t) >> >> this callback will be called every iteration step and can be provided in >> the call to optimize. >> >> The last solution can be retrieved from the tableau via getSolution(). >> >> Thomas >> >> >> B- I'm not confident enough that iterating a HashSet is fully >> >> deterministic, nothing in the contracts says so. If it's really not >> >> deterministic, then I'd have to copy the original constraints in the >> same >> >> foreach-loop that builds the normalized constraints list inside >> >> SimplexTableau (from the HashSet in LinearConstraintSet). Normalization >> >> happens in the normalizeConstraints method, and it returns a List right >> >> into the final "constraints" field. To have both lists populated in the >> >> same loop and placed in final fields, the loop would have to be in the >> >> constructor. Kinda ugly... >> > >> > the iteration order for a HashSet is still deterministic (as long as you >> > do not modify the set itself of course), but only inside a running vm. >> > Running the same example might lead to different results for different >> > vms, thus I was proposing to change the LinearConstraintSet to use a >> > LinkedHashSet internally as it will simplify analyzing and debugging >> > problems reported by users. >> > >> > btw. the constraints were provided as a plain list prior to the >> > refactoring that resulted in the current API available in the optim >> package. >> > >> >> So, any comments about the Simplex method and coding will be greatly >> >> appreciated. >> >> I'm a mathematician and programmer (much more the later than the >> former), >> >> but I'm not well versed in Java's idiosyncrasies, and I'm new to >> >> participating in the FOSS community. I want to do this, and so any >> guidance >> >> will be appreciated :-) >> > >> > Welcome to the commons community! >> > >> > Before starting to create patches, you might want to read the developers >> > guide: >> > >> > http://commons.apache.org/proper/commons-math/developers.html >> > >> > If you other questions, do not hesitate to raise them on the >> mailinglist. >> > >> > Thomas >> > >> >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org >> For additional commands, e-mail: dev-h...@commons.apache.org >> >> >
