<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
mso-fareast-language:EN-CA;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle21
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle22
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle23
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-CA" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">This problem has a bazillion feasible solutions and multiple ways of reaching the maximal value with most of the variables equal to 0.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">For example<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDC = 2000<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDCWETH = -333535.1668545<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">WETHUSDC = -963.31160643566<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">and<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDC = 2000<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDCDAI = -333355.04681602<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">DAIUSDC = -324833.7107381<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Obviously, I need to read up on degeneracy.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Regarding question 2, it makes no difference, a variable not appearing in an equation implicitly has a coefficient of 0.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> Clp <clp-bounces@coin-or.org>
<b>On Behalf Of </b>Lacroix, Robert<br>
<b>Sent:</b> Tuesday, September 8, 2020 5:16 PM<br>
<b>To:</b> clp@list.coin-or.org<br>
<b>Subject:</b> Re: [Clp] getting no results - does this imply degeneracy ?<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Oops, restating with 3 corrections (fixing missing parentheses for the value of USDCDAI, omitted the solution for USDTDAI, and a typo):<o:p></o:p></span></p>
<p class="MsoNormal">----------------------<o:p></o:p></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Apparently it’s not degenerate if you allow some variables to have negative values (I am supposing that you are).<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">I get a feasible solution by hand using the guess-and-fix-it-up approach, not saying it’s optimal, but a far cry from the trivial solution.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">This should be a good starting point for finding the optimal solution.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Giving symbolic names to your gnarly coefficient values:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:10.0pt"> USDC + USDCWETH + USDCDAI + USDCUSDT +
<b>AAA</b> WETHUSDC + <b>BBB</b> DAIUSDC + <b>CCC</b> USDTUSDC = 1<br>
WETHUSDC + WETHDAI + WETHUSDT + <b>DDD</b> USDCWETH + <b>EEE</b> DAIWETH + <b>
FFF</b> USDTWETH = 0<br>
DAIUSDC + DAIWETH + DAIUSDT + <b>GGG</b> USDCDAI + <b>HHH</b> WETHDAI + <b>III</b> USDTDAI = 0<br>
USDTUSDC + USDTWETH + USDTDAI + <b>JJJ</b> USDCUSDT + <b>KKK</b> WETHUSDT + <b>
LLL</b> DAIUSDT = 0<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">AAA</span></b><span style="font-size:10.0pt"> = - 344.142191<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">BBB</span></b><span style="font-size:10.0pt"> = -1.020079<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">CCC</span></b><span style="font-size:10.0pt"> = -0.993586<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">DDD</span></b><span style="font-size:10.0pt"> = -0.002888359217726139<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">EEE</span></b><span style="font-size:10.0pt"> = -0.002953897534741168<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">FFF</span></b><span style="font-size:10.0pt"> = -0.002886918859189835<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">GGG</span></b><span style="font-size:10.0pt"> = -0.974437656908750917<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">HHH</span></b><span style="font-size:10.0pt"> = -336.50626753022552063<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">III</span></b><span style="font-size:10.0pt"> = -0.972658375688681427<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">JJJ</span></b><span style="font-size:10.0pt"> = -1.000424<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">KKK</span></b><span style="font-size:10.0pt"> = -344.313875<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt">LLL</span></b><span style="font-size:10.0pt"> = -1.021948<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">A nontrivial feasible solution is:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDC = 1 - </span><span style="font-size:10.0pt">USDCWETH - USDCDAI - USDCUSDT -
<b>AAA</b> WETHUSDC - <b>BBB</b> DAIUSDC - <b>CCC</b> USDTUSDC = </span><span style="mso-fareast-language:EN-US">9.17873530387486<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">DAIUSDC = -4<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">DAIUSDT = -1 / <b>LLL</b> = 0.978523369095101<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">DAIWETH = 1<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDCDAI = (2 + 0.0214766309049) /
<b>GGG</b> = -2.07450586148088<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDCUSDT = (-<b>KKK</b> WETHUSDT - 0.001220405837704) /
<b>JJJ</b> = 1718.7954222119<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDCWETH = 4 / <b>DDD</b> = -1384.86929722993<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDTDAI = -2 / <b>III</b> = 2.05622040583768<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDTUSDC = 1<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">USDTWETH = -2 - 0.055 = -2.055<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">WETHDAI = 2 / <b>HHH</b> = -0.005943425704011<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">WETHUSDC = 1 - 0.002987829729894 = 0.997021270270106<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">WETHUSDT = -5 - WETHDAI = -4.99405647439599<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">resulting constraint values:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">1.0 + 1.0E-14<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">0.0 - 9.0090E-9<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">0.0 - 2.2204E-16<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">0.0 - 1.0436E-13<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">The way I’ve presented it, you can see how I created a coarse solution in integers using reciprocals of coefficients (because the RHS are integers) and then fine-tuned 4 variables.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> Clp <<a href="mailto:clp-bounces@coin-or.org">clp-bounces@coin-or.org</a>>
<b>On Behalf Of </b>Edgar A<br>
<b>Sent:</b> Monday, September 7, 2020 4:26 PM<br>
<b>To:</b> <a href="mailto:clp@list.coin-or.org">clp@list.coin-or.org</a><br>
<b>Subject:</b> [Clp] getting no results - does this imply degeneracy ?<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<table class="MsoNormalTable" border="0" cellpadding="0">
<tbody>
<tr>
<td style="background:white;padding:.75pt .75pt .75pt .75pt">
<pre><span style="color:black">_______________________________________________________________________<o:p></o:p></span></pre>
<pre><span style="color:black">BE CAUTIOUS WITH THIS EMAIL: This message originated outside Manitoba Hydro. Verify all links and attachments from unknown senders before opening. Search 'email security' on mpower for details. <o:p></o:p></span></pre>
<pre><span style="color:black">_______________________________________________________________________<o:p></o:p></span></pre>
</td>
</tr>
</tbody>
</table>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">Two part question - my math is a bit rusty on the nuances of OR , been a few years.
<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">1) I'm trying out CLP and have this generated LP table<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">max USDC<br>
subject to<br>
USDC + USDCWETH + USDCDAI + USDCUSDT - 344.142191 WETHUSDC - 1.020079 DAIUSDC - 0.993586 USDTUSDC = 1<br>
WETHUSDC + WETHDAI + WETHUSDT - 0.002888359217726139 USDCWETH - 0.002953897534741168 DAIWETH - 0.002886918859189835 USDTWETH = 0<br>
DAIUSDC + DAIWETH + DAIUSDT - 0.974437656908750917 USDCDAI - 336.50626753022552063 WETHDAI - 0.972658375688681427 USDTDAI = 0<br>
USDTUSDC + USDTWETH + USDTDAI - 1.000424 USDCUSDT - 344.313875 WETHUSDT - 1.021948 DAIUSDT = 0<br>
bounds<br>
USDC <= 2000<br>
end<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">Now running it in own cpp code, <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"> ClpSimplex model;<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"> model.primal();<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">I get:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">USDC: 1<br>
USDCWETH: 0<br>
USDCDAI: 0<br>
USDCUSDT: 0<br>
WETHUSDC: 0<br>
DAIUSDC: 0<br>
USDTUSDC: 0<br>
WETHDAI: 0<br>
WETHUSDT: 0<br>
DAIWETH: 0<br>
USDTWETH: 0<br>
DAIUSDT: 0<br>
USDTDAI: 0<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">Question: What does this imply? Does it mean there is degeneracy in the solution space? I also tried `model.dual()` but same results. Ought I to use something other than `ClpSimplex`? I suspected there might
be an issue for the numerical percision, that is, to use the latest which I see there is `long double`, but that code hasn't been released under the tarball release here (<a href="https://www.coin-or.org/download/source/Clp/">https://www.coin-or.org/download/source/Clp/</a>)
(I'm using latest at this time which is 1.17.6, appreciate if newer version released with long double be uploaded, yes i know about the build from source coinbrew, etc but had trouble with it, prefer this tarball approach)
<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">2) What about the occasions when a pairing does not exist, is it sufficient to simply leave out that variable, or add the variable but with coefficient of 0? In the examples I've seen, only the diagonal contains
no value. <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">Thank you <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt"><o:p> </o:p></span></p>
</div>
</div>
</div>
</body>
</html>