commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Renato Cherullo <cheru...@gmail.com>
Subject [math] Recover final tableau values from SimplexSolver
Date Mon, 09 Sep 2013 19:02:17 GMT
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).

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

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

Best regards,
  Renato C.

PS.: I opened a JIRA issue to track this:
 https://issues.apache.org/jira/browse/MATH-1032

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message