Sage algoritem

[NabergojV]

Zanima me zakaj mi vrže napako pri algoritmu v Sage-u. Prilagam link in kodo.

https://cocalc.com/projects/71d53eb6-050f-4a7c-8002-d2b9d7e70b76/files/2017-11-21-201822.sagews?session=default

︠6b781b77-aa09-43c3-abcd-bb703da29876s︠ program = MixedIntegerLinearProgram(maximization=False,solver="GLPK") vzamemo = program.new_variable(binary=True)

program.set_objective(sum(P[i] * vzamemo[i] for i in I))

I=[1,2,3,4,5] P= [3,4,6,2,1] W = [1,1,2,3,4] C=5

n=len(I) Csez=[] for i in range(n): Csez[i]=C-W[i] end indeks= 0 vsota= 0 while(vsota<= C): indeks=indeks + 1 vsota=vsota+ I[W[indeks]] end kriticen=indeks

W = program.new_variable(integer=True, nonnegative=True,[1,1,2,3,4]) P = program.new_variable(integer=True, nonnegative=True)

program.add_constraint(sum(W[i] vzamemo[i] for i in I) <= C) program.add_constraint(sum(min(W[j],C[i]+1)vzamemo[j] for j in I and i!=j)+ min(W[kriticen],C[i]+1)*vzamemo[i] >= C[i]+1 for i in I and i<=kriticen)

program.solve()

︡d996ebd0-f233-4a70-b88c-ef023f9b259d︡{"stderr":"Error in lines 3-3\nTraceback (most recent call last):\n File \"/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py\", line 1009, in execute\n exec compile(block+'\n', '', 'single') in namespace, locals\n File \"\", line 1, in \n File \"/ext/sage/sage-8.0/local/lib/python2.7/site-packages/sage/misc/functional.py\", line 565, in symbolic_sum\n return sum(expression, *args)\n File \"\", line 1, in \nIndexError: list index out of range\n"}︡{"done":true}︡

[jaanos]

Najprej, predlagam, da kodo kar naložiš na repozitorij, saj bo tako najlažje pregledovati in slediti spremembam. Če želita, lahko kodo na CoCalcu naredita javno dostopno (glej prvi odgovor pri marinasirk/Shortest-matching#2); če pa kodo vključuješ v issue, jo postavi v ustrezen blok, npr.

```sage
koda
```

Kako bo issue izgledal, lahko pred objavo preveriš s klikom na zavihek Preview.

Kar se samega programa tiče, bo treba najprej poskrbeti, da bo P definiran že pred določitvijo ciljne funkcije, saj se tam uporablja. Ker je I seznam indeksov, bo treba začeti z 0 - lahko uporabiš kar I = range(5). Seznamu Csez potem ni mogoče dodajati elementov na še neobstoječa mesta - lahko jih dodajaš z append, ali pa celoten seznam generiraš v eni vrstici s

Csez = [C-x for x in W]

Konstante W in P, ki jih že imaš definirane, potem prepišeš s spremenljivkami - tega nočeš narediti, saj izgubiš že definirane konstante, polega tega pa dobljeni program ne bi bil linearen, saj v omejitvah te spremenljivke množiš. Novi definiciji W in P torej pobriši.

Prva omejitev potem deluje, za drugo pa sklepam, da si hotela nekaj takega:

for i in range(kriticen+1):
    program.add_constraint(sum(min(W[j],Csez[i]+1)*vzamemo[j] for j in I if i!=j) + min(W[kriticen],Csez[i]+1)*vzamemo[i] >= Csez[i]+1)

Za vsak i od 0 do kriticen je tukaj torej ena omejitev - C (število) sem nadomestil s Csez (seznam - ali je tako prav?). Če hočeš pri zanki for filtrirati glede na nek pogoj, uporabi if namesto and.

[NabergojV]

Najlepša hvala za Vaš odgovor! Ali je potrebno, da nama algoritem vrne tudi seznam predmetov? Zanima me še kako potem uvozim podatke iz R-a v CoCalc ter kako jih integriram v algoritem? Videla sem csv reader na sage-u. Ali si pomagam s tem? Zanima me še, če obstaja kakšna funkcija, ki bi merila čas delovanja algoritma pri obsežnejših seznamih predmetov? Iskala sem po googlu, ampak nisem našla nič pametnega.. Najlepša hvala za Vaš odgovor! https://cocalc.com/projects/71d53eb6-050f-4a7c-8002-d2b9d7e70b76/files/2017-11-21-201822.sagews?session=default

[jaanos]

Ja, algoritem naj prebere seznam izbranih predmetov iz rešitve (program.get_values(vzamemo)).

Za prenos podatkov med R in Sage bo najbrž res najbolje uporabiti obliko CSV - datoteko lahko naložiš na CoCalc in potem prebereš s knjižnico csv za Python.

Za merjenje časa lahko pred ukaz postaviš %time, npr.

%time program.solve()

[NabergojV]

Popravila sem, kot ste rekli. Zanima me, če sem pravilno definirala funkcijo MCMKP_MIP, če se to sploh da. Pa še branje csv datotek, če sem prav definirala.

Najlepša hvala za Vaš odgovor!!

https://cocalc.com/projects/71d53eb6-050f-4a7c-8002-d2b9d7e70b76/files/algoritem.sagews?session=default

[jaanos]

Žal mi zgornja povezava ne deluje - prosim te, če naložiš kodo na GitHub, ali pa objaviš zvezek na CoCalc (glej marinasirk/Shortest-matching#2).

[NabergojV]

Naloženo na github.

[jaanos]

Sem odprl pull request #5 s popravki, tako da ga lahko pridružiš, pa naložiš novo kodo na CoCalc. Preveri seveda, ali je vse v redu.

Branje datoteke CSV izgleda v redu. Predpostavljam, da tvoja datoteka example.csv izgleda nekako tako:

0,3,1
1,4,1
2,6,2
3,2,3
4,1,4

Ena opomba glede %time - ta ti res izvede ukaz in izpiše trajanje, a ne pusti nobene posledice (ukaz se izvede v izolaciji). Če imaš tako v funkciji vrstico %time program.solve(), ti izpiše čas reševanja, sam program pa ostane nerešen in nato program.get_values(vzamemo) vrne same ničle. Zato se %time ne uporablja znotraj funkcij, pač pa raje celoten algoritem izvedeš s %time, da dobiš rezultat in celoten čas izvajanja.

[NabergojV]

Da csv izgleda tako, le da je vmes ";" ne pa ",". Ali moram kaj spremeniti? Še nekaj me zanima, v popravkih ste maximization spremenili iz False v True? Zakaj je to tako? Najlepša hvala!!

[jaanos]

Da bo pravilno bralo CSV s podpičji, je treba pri csv.reader podati še parameter delimiter = ';'. Parameter maximization pa naj seveda ostane na False - sem zamešal z običajnim problemom nahrbtnika, kjer maksimiziramo ceno.

[NabergojV]

Aha ok! Najlepša hvala! Če želim, da mi funkcija MCMKP_MIP vrne tudi čas trajanja izvanjanja, ali to samo vključim v return... return(program.solve(),program.get_values(vzamemo), %time MCMKP_MIP)?

[jaanos]

To ne bo delovalo, saj lahko %time uporabiš le na začetku vrstice. Če želiš čas shraniti v spremenljivko, si pomagaj s knjižnico time, npr.

from time import time
s = time()
resitev = MCMKP_MIP(C,P,W)
t = time()
trajanje = t-s # trajanje v sekundah

Še to: parameter delimiter = ';' podaj pri csv.reader, ne pri open.

[NabergojV]

Ok najlepša hvala! Ali lahko vstavim tole znotraj funkcija MCMKP_MIP? Vrže mi napako ko skušam preprost problem rešiti s tole funkcijo... Posodobila sem na githubu in dodala preprost problem

[NabergojV]

Sem popravila! Najlepša hvala za Vaše odgovore in rešitve!