# 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?

Please sign in to leave a comment.

## Comments

0 comments