commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "william niedringhaus (JIRA)" <j...@apache.org>
Subject [jira] Commented: (MATH-268) 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?
Date Wed, 03 Jun 2009 14:50:07 GMT

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


Mime
View raw message