FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Modeling PseudoBoolean Optimization problems with MIP

Description
A solver of PseudoBoolean optimization problems (PBO) that translates a problem into a MIP and solves it.

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

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

example_gencons_pbo.py

"""
This example builds a Pseudoboolean optimization solver that uses
the Xpress Optimizer library's General Constraints

c.f. http://www.cril.univ-artois.fr/PB16/
http://www.cril.univ-artois.fr/PB16/format.pdf
Parser loosely based on http://www.cril.univ-artois.fr/PB16/parser/SimpleParser.cc
(c) 2020 Fair Isaac Corporation
"""

import sys
import re
import xpress as xp

class Term:
def __init__(self, cons, conj):
"""
:param cons: coefficient
:param conj: list of variables in the product
"""
self.constant = cons
self.conjunction = conj

class Constraint:
def __init__(self, trms, sns, r):
"""

:param trms: List of terms in the constraint
:param sns: Sense
:param r: RHS
"""
self.terms = trms
self.sense = sns
self.rhs = r

def ignore_ws(fh):
"""
Skip whitespaces.
:param fh: file object
:return:
"""
while True:
if ch == ' ':
continue
else:
move_back(fh)
break

"""

:param fh: file object
:return: coefficient before a term in an expression
"""
constant = ''
while True:
if ch == 'x' or ch == '~' or ch == ' ' or ch == ';':
move_back(fh)
break
else:
constant += ch
return float(constant) if constant != '' else 1.0

def move_back(fh):
"""
move file ptr one step back
:param fh: file object
:return:
"""
fh.seek(fh.tell() - 1)

"""
:param fh: file object
:return: variable as string
"""
if ch != 'x':
print("Error. No variable identifier after negation at fpos {}".format(fh.tell() - 1))
sys.exit(-1)
index = ''
while True:
if ch == ' ':
move_back(fh)
break
index += ch
if index == ' ':
print("Error. No index after identifier at fpos {}".format(fh.tell() - 1))
sys.exit(-1)
return 'x' + index

"""
read the terms in a conjunction
:param fh: file object
:return: list of variables (with negations identified by '~' preceding the variable)
"""
conj = []
while True:
ignore_ws(fh)
if ch == '+' or ch == '-' or ch == '=' or ch == '<' or ch == '>' or ch == ';':
move_back(fh)
break
if ch == '~':
else:
move_back(fh)
return conj

"""
read the entire term of an expression
:param fh: file object
:return: term of an expression, including the constant
"""
ignore_ws(fh)
if conj is []:
print("Error. Term returned zero or constant at pos {}".format(fh.tell()))
sys.exit(0)
return Term(constant, conj)

def get_objective(fh):
"""
get the objective term
:param fh: file object
:return: objective sense, list of terms in the objective
"""
o_terms = []
o_sense = None
ch = ''
while True:
if ch == '*':
else:
break
if ch == 'm':
o_sense = ch + s
while True:
ignore_ws(fh)
if ch == ';':
break
else:
move_back(fh)
o_terms.append(term)

return o_sense, o_terms

def get_constraint(fh):
"""
:param fh: file object
:return: list of constraint objects
"""
cons = []
c_sense = ''
c_rhs = None
c_expr = []

while True:
ignore_ws(fh)
if ch == '\n':
break
elif ch == ';':
cons.append(Constraint(c_expr, c_sense, c_rhs))
if len(cons) % 10000 == 0:
c_sense = ''
c_rhs = None
c_expr = []
elif ch == '*':
elif ch == '>':
c_sense = '>='
ignore_ws(fh)
elif ch == '<':
c_sense = '<='
ignore_ws(fh)
elif ch == '=':
ignore_ws(fh)
c_sense = '='
else:
move_back(fh)
c_expr.append(term)

return cons

def build_expr(terms, variables):
"""

:param terms: List of Term objects in the expression
:param variables: Xpress variables expressed in a dictionary
:return: Xpress expression
"""
expr = None
for term in terms:
coeff = term.constant
conjunction = term.conjunction
if len(conjunction) == 1:  # linear
expr = coeff * variables[conjunction[0]] if expr is None else expr + coeff * variables[conjunction[0]]
else:
conj_terms = []
for item in conjunction:
if item.startswith('~'):
conj_terms.append(1 - variables[item[1:]])
else:
conj_terms.append(variables[item])
expr = coeff * xp.And(*conj_terms) if expr is None else expr + coeff * xp.And(*conj_terms)
return expr

if __name__ == '__main__':
if len(sys.argv) != 2:
print('A MIP-based Pseudoboolean solver')
print('Usage: python example_gencons_pbo_solver.py <filename.opb>')
sys.exit(-1)
else:
fname = sys.argv[1]
try:
with open(fname, 'r') as pbo:
pat = re.compile(r'#variable= (\d+)\s+#constraint= (\d+)')
match = re.search(pat, line)
if match:
n_vars = int(match.group(1))
n_cons = int(match.group(2))
print(line)
else:
print('Problem metadata not provided on line 1')
sys.exit(-1)
pbo.seek(0)
obj_sense, obj_terms = get_objective(pbo)
constraints = get_constraint(pbo)
# Create the problem
p = xp.problem()
# Define the variables
var_keys = ['x{}'.format(i) for i in range(1, n_vars + 1)]
x = {i: xp.var(vartype=xp.binary) for i in var_keys}
if len(obj_terms) > 1:
obj_expr = build_expr(obj_terms, x)
xp_sense = xp.minimize if obj_sense == 'min' else xp.maximize
p.setObjective(obj_expr, sense=xp_sense)
for constraint in constraints:
cons_expr = build_expr(constraint.terms, x)
rhs = constraint.rhs
sense = constraint.sense
# print(cons_expr, sense, rhs)
if sense == '<=':
elif sense == '>=':