Nedelujoč CLP v CoCalc

Kolikor vidim, je glavna težava v tem, da metode new_variable večinoma ne kličeta, pač pa jo samo priredite neki Pythonovi spremenljivki. Ta metoda vrne objekt, ki ga lahko indeksirata in tako dobita ustrezno spremenljivko v CLP. Spremenljivko lahko dobita tudi z indeksiranjem samega CLP p.

Mimogrede, svetujem, da naredita funkcijo, ki sprejme seznam kvadratov (ali pa vsaj seznam njihovih velikosti). Nekako tako bi potem šlo:

def packing(kvadrati): # zaenkrat seznam dolžin stranic
    p = MixedIntegerLinearProgram(maximization=False)
    x = p.new_variable() # x[i] bo x-koordinata levega roba i-tega kvadrata
    y = p.new_variable() # y[i] bo y-koordinata spodnjega roba i-tega kvadrata
    p.set_objective(p['z']) # spremenljivko p['z'] bo treba omejiti navzdol z največjo uporabljeno koordinato
    for i, d in enumerate(kvadrati): # i je indeks, d je dolžina stranice
        p.add_constraint(x[i] >= 0)  # želimo nenegativne koordinate
        p.add_constraint(y[i] >= 0) 
        p.add_constraint(x[i] + d <= p['z']) # omejimo p['z'] z največjo pokrito koordinato
        p.add_constraint(y[i] + d <= p['z'])
        ...
    z = p.solve() # rešimo CLP in dobimo vrednost ciljne funkcije
    xx = p.get_values(x) # dobimo vrednosti koordinat
    yy = p.get_values(y)
    return (z, [(xx[i], yy[i], d) for i, d in enumerate(kvadrati)]) # vrnemo max koordinato ter seznam koordinat in stranic kvadratov

Za osnovni primer (stranice od 1 do n) potem kličeta packing(range(1, n+1)).

Poleg tega v (celoštevilskem) linearnem programu ne moreta pogojev kar ločevati z or - potrebno bo to ustrezno modelirati. Če želita, da velja vsaj eden od naštetih pogojev, bo potrebno za vsakega uvesti spremenljivko, od katere vrednosti je odvisno, ali mora pogoj veljati, ter zahtevati, da je vsota teh spremenljivk takšna, da mora veljati vsaj eden od pogojev. V vajinem primeru bi torej lahko npr. uvedli binarno spremenljivko a[i, j] (že na začetku lahko rečeta a = p.new_variable(binary=True), kasneje pa jo samo ustrezno indeksirata), katere vrednost 1 pomeni, da je i-ti kvadrat levo od j-tega - treba bo nastaviti tako omejitev, ki bo v tem primeru enakovredna želeni omejitvi, če pa je a[i, j] == 0, pa vedno velja (in podobno še npr. b[i, j] za vertikalno urejenost). Potem lahko zahtevata, da za vsaka dva kvadrata velja vsaj en od teh pogojev:

    for i, j in Combinations(range(len(kvadrati)), 2): # vsi neurejeni pari indeksov
        p.add_constraint(a[i, j] + a[j, i] + b[i, j] + b[j, i] >= 1)

Mimogrede, zgornji pogoj lahko posplošita tudi na primer, ko je lahko vsaka točka pokrita tudi več kot enkrat.

Petja-Murnik / Consecutive-square-packing

Nedelujoč CLP v CoCalc #3