[ https://issues.apache.org/jira/browse/MATH268?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel&focusedCommentId=12715941#action_12715941
]
william niedringhaus commented on MATH268:

Yes, the starting solutions are provably feasible. Each constraint is of form (for lin expr
X)
X >= 0  fudgeFactor
The objective function minimizes a weighted sum of the fudgeFactor's (each >= 0).
Up front, I know a pretty good solution for the (non  fudgeFactor) variables that makes the
LP provably feasible, so long as I set the fudgeFactors sufficiently big (I have an algorithm
to do this).
Because the matrix is big but very sparse, and has a recursive structure, I plan to divide
it into halves, quarters, eighths, etc. I solve all the little LP's fast, work my way up
the binary tree. At each step, I can use the solution to the two halfsize LPs to form an
evercloserto optimal starting feasible solution for the full size LP, because only a very
few constraints in the full LP involve variables that occur in both halfLPs.
Although general LP's runtime is proportional to the cube of the problem size, I'm hoping
to run in something more like (n squared log n).
But, I need an (open source) LP algorithm that can be told where to start. I've tried GNU's
glpk (LPKit) (using the Java wrapper), but it does not appear to have this feature. Any ideas?
Thanks for your help on this,
Bill
> about your java simplex alg, can I input a solution known to be nearoptimal (to speed
it up)? Can I do so even for the dual simplex?
> 
>
> Key: MATH268
> URL: https://issues.apache.org/jira/browse/MATH268
> Project: Commons Math
> Issue Type: Wish
> Environment: linux or Windows XP
> Reporter: william niedringhaus
>

This message is automatically generated by JIRA.

You can reply to this email to add a comment to the issue online.
