[Clp] getting no results - does this imply degeneracy ?

Tue Sep 8 18:15:53 EDT 2020

Oops, restating with 3 corrections (fixing missing parentheses for the value of USDCDAI, omitted the solution for USDTDAI, and a typo):
----------------------
Apparently it’s not degenerate if you allow some variables to have negative values (I am supposing that you are).
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.
This should be a good starting point for finding the optimal solution.

Giving symbolic names to your gnarly coefficient values:

   USDC + USDCWETH + USDCDAI + USDCUSDT + AAA WETHUSDC + BBB DAIUSDC + CCC USDTUSDC = 1
   WETHUSDC + WETHDAI + WETHUSDT  + DDD USDCWETH + EEE DAIWETH + FFF USDTWETH = 0
   DAIUSDC + DAIWETH + DAIUSDT + GGG USDCDAI + HHH WETHDAI + III USDTDAI = 0
   USDTUSDC + USDTWETH + USDTDAI + JJJ USDCUSDT + KKK WETHUSDT + LLL DAIUSDT = 0
AAA = - 344.142191
BBB = -1.020079
CCC = -0.993586

DDD = -0.002888359217726139
EEE = -0.002953897534741168
FFF = -0.002886918859189835

GGG = -0.974437656908750917
HHH = -336.50626753022552063
III = -0.972658375688681427

JJJ = -1.000424
KKK = -344.313875
LLL = -1.021948

A nontrivial feasible solution is:

USDC = 1 - USDCWETH - USDCDAI - USDCUSDT - AAA WETHUSDC - BBB DAIUSDC - CCC USDTUSDC = 9.17873530387486

DAIUSDC = -4
DAIUSDT = -1 / LLL = 0.978523369095101
DAIWETH = 1

USDCDAI = (2 + 0.0214766309049) / GGG = -2.07450586148088
USDCUSDT = (-KKK WETHUSDT - 0.001220405837704) / JJJ = 1718.7954222119
USDCWETH = 4 / DDD = -1384.86929722993

USDTDAI = -2 / III = 2.05622040583768
USDTUSDC = 1
USDTWETH = -2 - 0.055 = -2.055

WETHDAI = 2 / HHH = -0.005943425704011
WETHUSDC = 1 - 0.002987829729894 = 0.997021270270106
WETHUSDT = -5 - WETHDAI = -4.99405647439599

resulting constraint values:
1.0 + 1.0E-14
0.0 - 9.0090E-9
0.0 - 2.2204E-16
0.0 - 1.0436E-13

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.

From: Clp <clp-bounces at coin-or.org<mailto:clp-bounces at coin-or.org>> On Behalf Of Edgar A
Sent: Monday, September 7, 2020 4:26 PM
To: clp at list.coin-or.org<mailto:clp at list.coin-or.org>
Subject: [Clp] getting no results - does this imply degeneracy ?

_______________________________________________________________________

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.

_______________________________________________________________________
Two part question - my math is a bit rusty on the nuances of OR , been a few years.

1) I'm trying out CLP and have this generated LP table

max USDC
subject to
   USDC + USDCWETH + USDCDAI + USDCUSDT - 344.142191 WETHUSDC - 1.020079 DAIUSDC - 0.993586 USDTUSDC = 1
   WETHUSDC + WETHDAI + WETHUSDT - 0.002888359217726139 USDCWETH - 0.002953897534741168 DAIWETH - 0.002886918859189835 USDTWETH = 0
   DAIUSDC + DAIWETH + DAIUSDT - 0.974437656908750917 USDCDAI - 336.50626753022552063 WETHDAI - 0.972658375688681427 USDTDAI = 0
   USDTUSDC + USDTWETH + USDTDAI - 1.000424 USDCUSDT - 344.313875 WETHUSDT - 1.021948 DAIUSDT = 0
bounds
  USDC <= 2000
end

Now running it in own cpp code,

  ClpSimplex model;
      model.primal();

I get:

USDC: 1
USDCWETH: 0
USDCDAI: 0
USDCUSDT: 0
WETHUSDC: 0
DAIUSDC: 0
USDTUSDC: 0
WETHDAI: 0
WETHUSDT: 0
DAIWETH: 0
USDTWETH: 0
DAIUSDT: 0
USDTDAI: 0

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 (https://www.coin-or.org/download/source/Clp/) (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)

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.

Thank you

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