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 > >
