commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject Re: [math] Recover final tableau values from SimplexSolver
Date Mon, 09 Sep 2013 20:37:59 GMT
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.

> 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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message