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

The feasiblity pump

Description
Feasibility pump (prototype) using the Xpress Python interface.

Further explanation of this example: 'Xpress Python Reference Manual'

FeasPump_python.zip[download all files]

Source Files





feas_pump.py

#
# Feasibility pump (prototype)
# using the Xpress Python interface
#

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()
p.read('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()

p.lpoptimize()
sol = []
p.getlpsol(x=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
    p.lpoptimize()
    p.getlpsol(x=sol)

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

# Found feasible solution

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

Back to examples browserPrevious exampleNext example