On 11/20/2013 05:43 PM, Renato Cherullo wrote: > 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?
I think you committed a bit too much - try to remove the target directory. Thomas > []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 >>> >>> >> > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
