Das Problem Kreuz ist im Internet abrufbar: IBM CPLEX ForumCPLEX: Benders Zersetzung mit quadratischem Term in der Outer-Optimierung
Ich versuche, ein zweistufigen Optimierungsproblem mit Bieger Zersetzung zu lösen. Das grundlegende Problem wie folgt aussieht:
min_x (f (x) + min_u (g (u)))
wobei g (u) ein lineares Programm, das für einen festen Wert der äußeren Entscheidung gelöst werden kann, Variable x. f (x) ist eine Funktion, die linear in x ist. Ich implementierte den spezifischen Code mit der CPLEX-Python-API, indem ich Callbacks einsetzte und Constraints im laufenden Betrieb unter Verwendung der Callbacks generierte. Die Ergebnisse sind wie erwartet.
Jetzt ist das Problem leicht modifiziert und f (x) ist eine Funktion, die quadratisch in x ist. Das Problem beendet jedoch, dass keine Lösung vorhanden ist, und die Rückrufe werden nie aufgerufen. Dies ist überraschend, da ich keinen Grund finde, warum eine Lösung nicht existieren sollte. Als ich versuchte, den Code zu debuggen, stellte ich fest, dass die Callback-Funktion für die Schnittgenerierung nach der Funktion "mipopt (env, lp)" aufgerufen wurde, wenn das Ziel nicht quadratisch war, aber jetzt nicht aufgerufen wird. Die grundlegende Struktur des Problems wird als Bild angehängt. Der einzige Unterschied in den beiden Problemen (der eine linear und der andere quadratisch) ist das Vorhandensein des x0^2-Terms im Objektiv.
Der Code für das Master-Problem ist:
def createMasterProblem(x,u,budget,alpha,beta)
cpx.objective.set_sense(cpx.objective.sense.minimize)
for i in range(numNodes):
varName = "x."+str(i)
q.append(cpx.variables.get_num())
cpx.variables.add(obj = [alpha[i]],
lb = [0.0], ub = [1], types = ["I"],
names = [varName])
varName = "u"
u.append(cpx.variables.get_num())
cpx.variables.add(obj = [1],
lb = [-cplex.infinity],
ub = [cplex.infinity],
types = ["C"],
names = [varName])
#add the budget constraint
theVars = []
theCoeffs = []
for i in range(numNodes):
theVars.append(x[i])
theCoeffs.append(1)
cpx.linear_constraints.add(lin_expr = [cplex.SparsePair(theVars,theCoeffs)],
senses = ["E"], rhs = [budget])
#create the quadratic part of the objective function
qmat = [[[0, 1, 2, 3], [beta, 0.0, 0.0, 0.0]],
[[0, 1, 2, 3], [0.0, 0.0, 0.0, 0.0]],
[[0, 1, 2, 3], [0.0, 0.0, 0.0, 0.0]],
[[0, 1, 2, 3], [0.0, 0.0, 0.0, 0.0]]]
cpx.objective.set_quadratic(qmat)
Eines der Themen, die mich wirklich, dass ist überrascht, wenn Koeffizienten aller quadratischen Terme auf 0 gesetzt sind, im Wesentlichen das Problem machen das gleiche wie zuvor, selbst dann solve() gibt eine Nachricht mit der Meldung "No Solution Exists" zurück.