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

[usa usa]

Hi,

I have tried to solve the LP with Dual Simplex in CLP but ran out of
memory.

Why "at least 80K constraints will be redundant in the optimal solution" ?

In my LP model, each constraint of

       decVarK_L >= sum of (constantValue_j_i  * decVarX_i) from i=1 to  N
- decVarT

will introduce a new decision variable called decVarK_j and j can be from 1
to L. Here L can be 100k.

Any help would be appreciated.

thanks




On Wed, Aug 31, 2016 at 3:51 PM, John Forrest <john.forrest at fastercoin.com>
wrote:

> 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
> > 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 to  N
>>
>> s.t.
>>
>>       decVarT + sum of (decVarK_i ) from i=1 to I = N  <=  [sum of
>> (constantValueP_i  * decVarX_i)  from i=1 to  N ] * constantQ
>>
>>
>>       [sum of (constantValueE_i  * decVarX_i)  from i=1 to  N ] <= [sum
>> of (constantValueE_i )  from i=1 to  N ] * constantD
>>
>>
>>       decVarK_1 >= sum of (constantValue_1_i  * decVarX_i) from i=1 to  N
>> -
>>
>> decVarT
>>
>>
>>       decVarK_2 >= sum of (constantValue_2_i  * decVarX_i) from i=1 to  N
>> - decVarT
>>
>>
>>       …
>>
>>
>>       decVarK_L >= sum of (constantValue_j_i  * decVarX_i) from i=1 to  N
>> - decVarT
>>
>>
>>
>> Decision variables:
>>
>> decVarT , 0 <= decVarX_i <= 1, decVarK_i >= 0
>>
>>
>>
>> The problem is that the number of constraints of   decVarK_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 listClp at list.coin-or.orghttps://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 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=OZ7lNGHhz6hn
>> cr0dJo35lLoUkFeHcQJj8l5Yd4riBoE&s=QuGUkAd8wEzd7ttcfSt6F7QUcU
>> o8o9NtPe9DXXByuc4&e=
>
> _______________________________________________
> Clp mailing listClp 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=
>
>
> _______________________________________________
> 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=dsAhYgYMFA3lB0slzjj1tRzNWYmsEV
> kEtULxrYaBfxE&m=eViRg2B4Pgchlz0FaWBC97oeeTt-Xj2diYbULBuZDss&s=
> 7jSnFUXoI3SgBrx0LXs5qvDunOXL5xGs7q-rTgd_uSs&e=
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20160831/e698fbe4/attachment.html>