# Given an infeasible LP, find an (infeasible) solution that minimize
# the total distance from the constraints. Then solve the obtained MaxFS problem.
#
# (C) 1983-2025 Fair Isaac Corporation

import xpress as xp

p = xp.problem()

x = p.addVariable()
y = p.addVariable()

# Build a very simple problem with pairs of incompatible constraints.

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.optimize()

assert(p.attributes.solstatus == xp.SolStatus.INFEASIBLE)

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

m = p.attributes.rows

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

# Big-M: large-enough constant to relax all constraints (quite conservative
# here).
M = 1e3

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

# Add m new binary columns.

p.addCols([1]*m,  # obj. 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})
)
p.addNames(xp.Namespaces.COLUMN, ['b_{}'.format(i) for i in range(m)], 2, p.attributes.cols - 1)
p.chgColType(range(2, p.attributes.cols), ['B']*m)  # change type to binary
p.optimize()

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