The feasiblity pump

# Feasibility pump - algorithm implementation using the Xpress Python interface.
#
# (C) 1983-2025 Fair Isaac Corporation

import xpress as xp

def getRoundedSol(sol, I):
    rsol = sol[:]
    for i in I:
        rsol[i] = round(sol[i])
    return rsol

def computeViol(p, viol, rtype, m):
    for i in range(m):
        if rtype[i] == 'L':
            viol[i] = -viol[i]
        elif rtype[i] == 'E':
            viol[i] = abs(viol[i])
    return max(viol[:m])

p = xp.problem()
p.readProb('Data/test.lp')

n = p.attributes.cols  # Number of columns.
m = p.attributes.rows  # Number of rows.
N = range(n)

vtype = p.getColType(0, n-1)  # Obtain variable type ('C', for continuous).

I = [i for i in N if vtype[i] != 'C']  # Discrete variables.

V = p.getVariable()

p.lpOptimize()
sol = p.getSolution()
roundsol = getRoundedSol(sol, I)
slack = p.calcSlacks(roundsol)
rtype = p.getRowType(0, m - 1)

# If x_I is the vector of integer variables and x_I* is its LP value,
# the auxiliary problem is:
#
# min |x_I - x_I*|_1
# s.t. x in X
#
# where X is the original feasible set. Add new variables y and set
# their sum as the objective, then define the l1 norm with the
# constraints:
#
# y_i >= x_i - x_i*
# y_i >= - (x_i - x_i*)

y = [p.addVariable() for i in I]

p.setObjective(xp.Sum(y))  # Objective.

# RHS to be configured later.
defPenaltyPos = [y[i] >= V[I[i]] for i in range(len(I))]
defPenaltyNeg = [y[i] >= - V[I[i]] for i in range(len(I))]

p.addConstraint(defPenaltyPos, defPenaltyNeg)

slackTol = 1e-4

while computeViol(p, slack, rtype, m) > slackTol:

    # Modify definition of penalty variable.
    p.chgRHS(defPenaltyPos, [-roundsol[i] for i in I])
    p.chgRHS(defPenaltyNeg, [roundsol[i] for i in I])

    # Reoptimize.
    p.lpOptimize()
    sol = p.getSolution()

    roundsol = getRoundedSol(sol, I)
    slack = p.calcSlacks(roundsol)

# Found feasible solution.
print('Feasible solution:', roundsol[:n])