[Clp] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[John Forrest]

 From what I understand, your problem has many more constraints than 
variables.

So if you have 20K variables and 100K constraints then at least 80K 
constraints will be redundant in the optimal solution.  The idea of the 
example is that you solve the problem with a few (? 20K) constraints.  
This will be much faster than with the full problem.  Then you can see 
(maybe with some problem specific knowledge) which constraints to drop 
and which to add.  As long as the objective value increases this is a 
finite algorithm, which has been shown to work well in many instances.

You could also solve the dual of your problem.

John forrest

On 31/08/16 20:33, usa usa wrote:
> Hi, John,
>
> I have run the code and do not understand how it can be used to reduce 
> the number of constraints in my problem.
>
> Any guidance would be appreciated.
>
> thanks
>
> On Wed, Aug 31, 2016 at 1:29 PM, John Forrest 
> <john.forrest at fastercoin.com <mailto:john.forrest at fastercoin.com>> wrote:
>
>     Look at Clp/examples/dualCuts.cpp - you should be able to adapt it.
>
>     John Forrest
>
>
>     On 31/08/16 17:10, usa usa wrote:
>>
>>     Hi,
>>
>>     I need to build a large scale LP model and solve it by CLP.
>>
>>     In the model, there is a kind of constraint like:
>>
>>     Max: sum of (constantValueP_i* decVarX_i) from i=1 toN
>>
>>     s.t.
>>
>>     decVarT + sum of (decVarK_i ) from i=1 to I = N<=[sum of
>>     (constantValueP_i* decVarX_i)from i=1 toN ] * constantQ
>>
>>
>>     [sum of (constantValueE_i* decVarX_i)from i=1 toN ] <= [sum of
>>     (constantValueE_i )from i=1 toN ] * constantD
>>
>>
>>     decVarK_1 >= sum of (constantValue_1_i* decVarX_i) from i=1 toN -
>>
>>     decVarT
>>
>>
>>     decVarK_2 >= sum of (constantValue_2_i* decVarX_i) from i=1 toN -
>>     decVarT
>>
>>
>>     …
>>
>>
>>     decVarK_L >= sum of (constantValue_j_i* decVarX_i) from i=1 toN -
>>     decVarT
>>
>>     Decision variables:
>>
>>     decVarT , 0 <= decVarX_i <= 1, decVarK_i >= 0
>>
>>     The problem is that the number of constraints ofdecVarK_i for i=1
>>     to L and L can be very large, e.g. 100,0000.
>>
>>     It means that it will have 100,000 constraints in the LP, which I
>>     want to avoid.
>>
>>     How to combine them so that I can reduce the size of the LP model
>>     meanwhile keeping all constraints satisfied ?
>>
>>     thanks
>>
>>
>>
>>     _______________________________________________
>>     Clp mailing list
>>     Clp at list.coin-or.org <mailto:Clp at list.coin-or.org>
>>     https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=S3UeV4Wu5yHELjmWBTDl-eRIeWOSeDtcdfAfTnhn-HU&s=tU_XGRYlmWymVflxTZzAzfVHknXPfwEvd-Sv1KZv2rc&e=
>>     <https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=S3UeV4Wu5yHELjmWBTDl-eRIeWOSeDtcdfAfTnhn-HU&s=tU_XGRYlmWymVflxTZzAzfVHknXPfwEvd-Sv1KZv2rc&e=>  
>
>     _______________________________________________ Clp mailing list
>     Clp at list.coin-or.org <mailto:Clp at list.coin-or.org>
>     https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=dsAhYgYMFA3lB0slzjj1tRzNWYmsEVkEtULxrYaBfxE&m=OZ7lNGHhz6hncr0dJo35lLoUkFeHcQJj8l5Yd4riBoE&s=QuGUkAd8wEzd7ttcfSt6F7QUcUo8o9NtPe9DXXByuc4&e=
>     <https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=dsAhYgYMFA3lB0slzjj1tRzNWYmsEVkEtULxrYaBfxE&m=OZ7lNGHhz6hncr0dJo35lLoUkFeHcQJj8l5Yd4riBoE&s=QuGUkAd8wEzd7ttcfSt6F7QUcUo8o9NtPe9DXXByuc4&e=>
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=GBxmGypQEe6nyH5QIajEjc2n2Fs8xjDnLsGHFPH8EdQ&s=FqmwsBhTAKH6XVOvmHjYG6sG6rhvu72kaec0vUhc3_Y&e=

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20160831/2fa9ffb9/attachment-0001.html>