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
