Minimizing distance from constraints

#!/bin/env python

import xpress as xp

#
# Example: given an infeasible LP, find an (infeasible) solution that minimize the total distance from the constraints
#
# Then solve the MaxFS problem

x = xp.var ()
y = xp.var ()

# build a very simple problem with pairs of incompatible constraints

p = xp.problem ()

p.addVariable (x,y)

lhs1 = 2*x + 3*y
lhs2 = 3*x + 2*y
lhs3 = 4*x + 5*y

p.addConstraint (lhs1 >= 6, lhs1 <= 5)
p.addConstraint (lhs2 >= 5, lhs2 <= 4)
p.addConstraint (lhs3 >= 8, lhs3 <= 7)

p.solve ()

assert (p.getProbStatus () == xp.lp_infeas)

# We verified the problem is infeasible. Add one binary for each
# constraint to selectively relax them.

m = p.attributes.rows

sign = []
p.getrowtype (sign, 0, m-1) # get the signs of all constraints: 'E', 'L', or
                            # 'G'. Note that this example only works with
                            # inequality constraints only

M = 1e3  # big-M, large-enough constant to relax all constraints (quite conservative here)

matval = [M]*m
for i in range (m):
    if sign[i] == 'L':
        matval[i] = -M

# Add m new binary columns

p.addcols ([1]*m,                                  # objective coefficients (as many 1s as there are constraints)
           range(m+1),                             # cumulative number of terms in each column: 0,1,2,...,m as there is one term per column
           range(m), matval,                       # pairs (row_index, coefficient) for each column
           [0]*m, [1]*m,                           # lower, upper bound (binary variables, so {0,1})
           ['b_{}'.format(i) for i in range (m)],  # names are b_i, with i is the constraint index
           ['B']*m)                                # type: binary

p.solve ()

# Print constraints constituting a Maximum Feasible Subsystem

b = p.getSolution (range (p.attributes.cols - m, p.attributes.cols))

maxfs = [i for i in range (m) if b[i] > 0.5]

print ('MaxFS has ', len (maxfs), 'constraints:', maxfs)