<div dir="ltr"><div><div><div><div><div><div>Hi, <br><br></div>I have tried to solve the LP with Dual Simplex in CLP but ran out of memory. <br><br></div>Why "at least
80K constraints will be redundant in the optimal solution" ? <br><br></div>In my LP model, each constraint of <br> <br> <span></span>decVarK_L >= sum of
(constantValue_j_i<span> </span>* decVarX_i)
from i=1 to<span> </span>N - decVarT<br><br></div>will introduce a new decision variable called decVarK_j and j can be from 1 to L. Here L can be 100k.<br><br></div>Any help would be appreciated.<br><br></div>thanks <br><div><div><div><br><br><div> <br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Aug 31, 2016 at 3:51 PM, John Forrest <span dir="ltr"><<a href="mailto:john.forrest@fastercoin.com" target="_blank">john.forrest@fastercoin.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">
<div>From what I understand, your problem
has many more constraints than variables.<br>
<br>
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.<br>
<br>
You could also solve the dual of your problem.<br>
<br>
John forrest<div><div class="gmail-h5"><br>
<br>
On 31/08/16 20:33, usa usa wrote:<br>
</div></div></div>
<blockquote type="cite"><div><div class="gmail-h5">
<div dir="ltr">
<div>
<div>
<div>Hi, John, <br>
<br>
</div>
I have run the code and do not understand how it can be used
to reduce the number of constraints in my problem. <br>
<br>
</div>
Any guidance would be appreciated. <br>
<br>
</div>
thanks</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Aug 31, 2016 at 1:29 PM, John
Forrest <span dir="ltr"><<a href="mailto:john.forrest@fastercoin.com" target="_blank">john.forrest@fastercoin.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote">
<div>
<div>Look at Clp/examples/dualCuts.cpp - you should be
able to adapt it.<br>
<br>
John Forrest
<div>
<div><br>
<br>
On 31/08/16 17:10, usa usa wrote:<br>
</div>
</div>
</div>
<blockquote type="cite">
<div>
<div>
<div dir="ltr">
<p>Hi, </p>
<p> </p>
<p>I need to build a large scale LP model and
solve it by CLP.</p>
<p> </p>
<p>In the model, there is a kind of constraint
like: </p>
<p><span> </span></p>
<p>Max: sum of (constantValueP_i<span> </span>*
decVarX_i) from i=1 to<span> </span>N</p>
<p>s.t. </p>
<p><span> </span>decVarT + sum of (decVarK_i
) from i=1 to I = N<span> </span><=<span>
</span>[sum of (constantValueP_i<span> </span>*
decVarX_i)<span> </span>from i=1 to<span> </span>N
] * constantQ</p>
<p><span><br>
</span></p>
<p><span> </span>[sum of (constantValueE_i<span>
</span>* decVarX_i)<span> </span>from i=1 to<span>
</span>N ] <= [sum of (constantValueE_i )<span>
</span>from i=1 to<span> </span>N ] *
constantD</p>
<p><span><br>
</span></p>
<p><span> </span>decVarK_1 >= sum of
(constantValue_1_i<span> </span>* decVarX_i)
from i=1 to<span> </span>N - <br>
</p>
<p>decVarT</p>
<p><span><br>
</span></p>
<p><span> </span>decVarK_2 >= sum of
(constantValue_2_i<span> </span>* decVarX_i)
from i=1 to<span> </span>N - decVarT</p>
<p><span><br>
</span></p>
<p><span> </span>…</p>
<p><span><br>
</span></p>
<p><span> </span>decVarK_L >= sum of
(constantValue_j_i<span> </span>* decVarX_i)
from i=1 to<span> </span>N - decVarT</p>
<p> </p>
<p>Decision variables: </p>
<p>decVarT , 0 <= decVarX_i <= 1, decVarK_i
>= 0</p>
<p> </p>
<p>The problem is that the number of constraints
of<span> </span>decVarK_i for i=1 to L and L
can be very large, e.g. 100,0000. </p>
<p> </p>
<p>It means that it will have 100,000 constraints
in the LP, which I want to avoid. </p>
<p> </p>
<p>How to combine them so that I can reduce the
size of the LP model meanwhile keeping all
constraints satisfied ? </p>
<p> </p>
<p>thanks</p>
</div>
<br>
<fieldset></fieldset>
<br>
</div>
</div>
<pre>______________________________<wbr>_________________
Clp mailing list
<a href="mailto:Clp@list.coin-or.org" target="_blank">Clp@list.coin-or.org</a>
<a href="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=" target="_blank">https://urldefense.proofpoint.<wbr>com/v2/url?u=http-3A__list.coi<wbr>n-2Dor.org_mailman_listinfo_<wbr>clp&d=CwICAg&c=Ngd-ta5yRYsqeUs<wbr>EDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&<wbr>r=js2M0T-3OIMIVDvokcKjokJbk0F8<wbr>QOCd0mT4FsVFE88&m=<wbr>S3UeV4Wu5yHELjmWBTDl-eRIeWOSeD<wbr>tcdfAfTnhn-HU&s=tU_XGRYlmWymVf<wbr>lxTZzAzfVHknXPfwEvd-Sv1KZv2rc&<wbr>e=</a>
</pre>
</blockquote>
<p>
</p>
</div>
______________________________<wbr>_________________
Clp mailing list
<a href="mailto:Clp@list.coin-or.org" target="_blank">Clp@list.coin-or.org</a>
<a href="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=" rel="noreferrer" target="_blank">https://urldefense.proofpoint.<wbr>com/v2/url?u=http-3A__list.coi<wbr>n-2Dor.org_mailman_listinfo_<wbr>clp&d=CwICAg&c=Ngd-ta5yRYsqeUs<wbr>EDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&<wbr>r=dsAhYgYMFA3lB0slzjj1tRzNWYms<wbr>EVkEtULxrYaBfxE&m=OZ7lNGHhz6hn<wbr>cr0dJo35lLoUkFeHcQJj8l5Yd4riBo<wbr>E&s=QuGUkAd8wEzd7ttcfSt6F7QUcU<wbr>o8o9NtPe9DXXByuc4&e=</a>
</blockquote></div>
</div>
<fieldset></fieldset>
</div></div><pre><div><div class="gmail-h5">______________________________<wbr>_________________
Clp mailing list
<a href="mailto:Clp@list.coin-or.org" target="_blank">Clp@list.coin-or.org</a>
</div></div><a href="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=" target="_blank">https://urldefense.proofpoint.<wbr>com/v2/url?u=http-3A__list.<wbr>coin-2Dor.org_mailman_<wbr>listinfo_clp&d=CwICAg&c=Ngd-<wbr>ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLx<wbr>WPA_2Wlc4&r=js2M0T-<wbr>3OIMIVDvokcKjokJbk0F8QOCd0mT4F<wbr>sVFE88&m=<wbr>GBxmGypQEe6nyH5QIajEjc2n2Fs8xj<wbr>DnLsGHFPH8EdQ&s=<wbr>FqmwsBhTAKH6XVOvmHjYG6sG6rhvu7<wbr>2kaec0vUhc3_Y&e=</a>
</pre>
</blockquote><p>
</p></div><br>______________________________<wbr>_________________<br>
Clp mailing list<br>
<a href="mailto:Clp@list.coin-or.org">Clp@list.coin-or.org</a><br>
<a href="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=eViRg2B4Pgchlz0FaWBC97oeeTt-Xj2diYbULBuZDss&s=7jSnFUXoI3SgBrx0LXs5qvDunOXL5xGs7q-rTgd_uSs&e=" rel="noreferrer" target="_blank">https://urldefense.proofpoint.<wbr>com/v2/url?u=http-3A__list.<wbr>coin-2Dor.org_mailman_<wbr>listinfo_clp&d=CwICAg&c=Ngd-<wbr>ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLx<wbr>WPA_2Wlc4&r=<wbr>dsAhYgYMFA3lB0slzjj1tRzNWYmsEV<wbr>kEtULxrYaBfxE&m=<wbr>eViRg2B4Pgchlz0FaWBC97oeeTt-<wbr>Xj2diYbULBuZDss&s=<wbr>7jSnFUXoI3SgBrx0LXs5qvDunOXL5x<wbr>Gs7q-rTgd_uSs&e=</a><br>
<br></blockquote></div><br></div></div></div></div></div></div>