[
https://issues.apache.org/jira/browse/MATH-268?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12715941#action_12715941
]
william niedringhaus commented on MATH-268:
-------------------------------------------
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 half-size LPs to form an ever-closer-to 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 half-LPs.
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 near-optimal
> (to speed it up)? Can I do so even for the dual simplex?
> --------------------------------------------------------------------------------------------------------------------------------------
>
> Key: MATH-268
> URL: https://issues.apache.org/jira/browse/MATH-268
> 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.
