Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: issues@commons.apache.org
Message-ID: <1772485358.1244040607578.JavaMail.jira@brutus>
Date: Wed, 3 Jun 2009 07:50:07 -0700 (PDT)
From: "william niedringhaus (JIRA)" <jira@apache.org>
To: issues@commons.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?
In-Reply-To: <1618618080.1243196145543.JavaMail.jira@brutus>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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