FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

The feasiblity pump

Feasibility pump (prototype) using the Xpress Python interface.

Further explanation of this example: 'Xpress Python Reference Manual'[download all files]

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.[download]

# Feasibility pump (prototype)
# using the Xpress Python interface
# (C) Fair Isaac Corp., 1983-2021

from __future__ import print_function

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()'test.lp')

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

vtype = []                   # create empty vector
p.getcoltype(vtype, 0, n-1)  # obtain variable type ('C', for continuous)

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

V = p.getVariable()

sol = []
roundsol = getRoundedSol(sol, I)
slack = []
p.calcslacks(roundsol, slack)
rtype = []
p.getrowtype(rtype, 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 = [xp.var() for i in I]

p.addVariable(y)  # add variables for new objective
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

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

# Found feasible solution

print('feasible solution:', roundsol[:n])

Back to examples browserPrevious exampleNext example