commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <>
Subject Re: [math] Recover final tableau values from SimplexSolver
Date Tue, 10 Sep 2013 05:42:09 GMT
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().


>> 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:
> If you other questions, do not hesitate to raise them on the mailinglist.
> Thomas

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message