Farkas certificate
The background for my question is that I was implementing Benders decomposition and run into something strange while working on feasibility cuts. I wanted to use Farkas certificate as extreme ray of a dual however it seems that I needed to change a sense of constraint for a things to work. It did not understand why it is the case so I did some more analysis.
To illustrate a problem and my question I come up with a simpler example that I hope you can comment on.
Let's start with the following problem:
$$
min c^Tx
Ax >= b
x >= 0
$$
And assume that this problem is infeasible. Then vector $y$ is a Farkas certificate iff: $ b^T * y > 0$ and $A^T * y <= 0$. And at the same time it is extreme ray of dual problem. To verify that I formulated two simple LP problem: primal - infeasible and its dual - unbounded:
import gurobipy as grb
import numpy as np
def infeasible():
print("*** Infeasible model ***")
m = grb.Model("model")
m.setParam("InfUnbdInfo", 1)
x = m.addVar(vtype=grb.GRB.CONTINUOUS, name="x", lb=0.0, ub=grb.GRB.INFINITY)
y = m.addVar(vtype=grb.GRB.CONTINUOUS, name="y", lb=0.0, ub=grb.GRB.INFINITY)
# Set objective
m.setObjective(-x + y, grb.GRB.MINIMIZE)
c0 = m.addConstr(-x + y >= 1, "c0")
c1 = m.addConstr(x - y >= 1, "c1")
m.optimize()
m.write("infeasible.lp")
if m.status == grb.GRB.Status.INFEASIBLE:
y = np.array([c0.getAttr("FarkasDual"), c1.getAttr("FarkasDual")])
print(f'farkas certificate={y}')
A = np.array([[-1, 1], [1, -1]])
b = np.array([1, 1])
q = A.transpose().dot(y)
r = b.transpose().dot(y)
print(f'q={q}')
print(f'r={r}')
extreme_ray = np.array([1, 1])
q = A.transpose().dot(extreme_ray)
r = b.transpose().dot(extreme_ray)
z = np.array([0, 0])
print(f'q={q}')
print(f'r={r}')
print(q.transpose().dot(z) < r)
def unbounded():
print("*** Unbounded model ***")
m = grb.Model("model")
m.setParam("InfUnbdInfo", 1)
# Create variables
u = m.addVar(vtype=grb.GRB.CONTINUOUS, name="u", lb=0.0, ub=grb.GRB.INFINITY)
v = m.addVar(vtype=grb.GRB.CONTINUOUS, name="v", lb=0.0, ub=grb.GRB.INFINITY)
# Set objective
m.setObjective(u + v, grb.GRB.MAXIMIZE)
c0 = m.addConstr(-u + v <= -1, "c0")
c1 = m.addConstr(u - v <= 1 , "c1")
m.write("unbounded.lp")
m.optimize()
if m.status == grb.GRB.Status.UNBOUNDED:
print("Ray:", m.getAttr("UnbdRay"))
infeasible()
unbounded()
But what I am getting in this case is Farkas certificate f=[-1, -1] and for dual extreme ray r=[1, 1]. What I do not understand is why $f = -r$ rather than $f = r$. In my understanding it does not fulfill requirements of Farkas certificate. Am I missing something here? Also, would it always be the case that $f = -r$?
P. S. Is there a guide on formatting that can be used to make posts look good?
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
Post is closed for comments.
Comments
1 comment