jaanos
commented
7 years ago Najprej, funkciji za ILP je ime MixedIntegerLinearProgram (torej e namesto i v drugi besedi). Druga stvar je ta, da enakost določiš z == namesto z =.
Pazi še, kako podajaš omejitve - če hočeš podati omejitev za vsako vozlišče (kot v prvi omejitvi), to naredi s for zanko - list comprehension lahko uporabiš samo znotraj sum. Podobno naredi pri ostalih dveh omejitvah za vsako barvo.
Pri zadnji omejitvi dodaj parameter labels = False k metodi G.edges, da ti ne bo vračalo oznak povezav (ki te tukaj ne zanimajo). Pazi še na to, da se lahko posamezna barva pri sosednjih vozliščih pojavi največ enkrat - vsota je torej največ 1.
Jaz sem poskušala napisati ILP za iskanje kromatičnega števila, vendar mi vedno javlja neko napako in ne vem kaj je narobe.
p = MixedIntigerLinearProgram(maximization = False) x = p.new_variable(binary = True) y = p.new_variable(binary = True) p.set_objective(sum(y[k] for k in range(n))) p.add_constraint((sum(x[i,k] for k in range(n)) for i in range(n)) = 1) for i in G.vertices(): p.add_constraint(((x[i,k]-y[k]) for k in range(n)) <= 0) for i,j in G.edges(): p.add_constraint(((x[i,k] + x[j,k]) for k in range(n)) <=0) p.solve()