congress.datalog.arithmetic_solvers module

class congress.datalog.arithmetic_solvers.LpLang

Bases: object

Represent (mostly) linear programs generated from Datalog.

class Expression(*args, **meta)

Bases: object

arguments()
operator()
tuple()
exception LpConversionFailure(message=None, **kwargs)

Bases: congress.exception.CongressException

MIN_THRESHOLD = 1e-05
arith_to_lt_zero(expr)

Returns Arith expression equivalent to expr but of the form A < 0.

Parameters

expr – is an Expression

Returns

an expression equivalent to expr but of the form A < 0.

create_intermediate(exp)

Given expression, create var = expr and return (var, var=expr).

flatten(exp, indicator=True)

Remove toplevel embedded and/ors by creating new equalities.

Parameters

  • exp – is an Expression of the form var = (arith11 ^ … ^ arith1n) | … | (arithk1 ^ … ^ arithkn) where arithij is either a variable or an arithmetic expression where the degenerate cases are permitted as well.

  • indicator – controls whether the method Returns a single variable (with supporting expressions) or it Returns an expression that has operator with (flat) arguments

Returns

a collection of expressions each of one of the following forms: var1 = var2 * … * varn var1 = var2 + … + varn var1 = arith

Returns

(new-expression, supporting-expressions)

freshVar(**meta)
indicator_to_pure_lp(exp, bounds)

Translate exp into LP constraints without indicator variable.

Parameters

  • exp – is an Expression of the form var = arith

  • bounds – is a dictionary from variable to its upper bound

Returns

[EXP] if it is of the wrong form. Otherwise, translates into the form y = x < 0, and then returns two constraints where upper(x) is the upper bound of the expression x:

-x <= y * upper(x)
x < (1 - y) * upper(x)

Taken from section 7.4 of http://www.aimms.com/aimms/download/manuals/ aimms3om_integerprogrammingtricks.pdf

classmethod isAnd(thing)
classmethod isArith(thing)
classmethod isBoolArith(thing)
classmethod isConstant(thing)
classmethod isEqual(thing)
classmethod isNotEqual(thing)
classmethod isOr(thing)
classmethod isVariable(thing)
classmethod makeAnd(*args, **meta)
classmethod makeArith(*args, **meta)
classmethod makeBoolVariable(*args, **meta)
classmethod makeEqual(arg1, arg2, **meta)
classmethod makeExpr(obj)
classmethod makeIntVariable(*args, **meta)
classmethod makeNotEqual(arg1, arg2, **meta)
classmethod makeOr(*args, **meta)
classmethod makeVariable(*args, **meta)
operator_to_constructor(operator)

Given the operator, return the corresponding constructor.

pure_lp(exp, bounds)

Rewrite EXP to a pure LP problem.

Parameters

exp – is an Expression of the form var = (arith11 ^ … ^ arith1n) | … | (arithk1 ^ … ^ arithkn) where the degenerate cases are permitted as well.

Returns

a collection of expressions each of the form: a1*x1 + … + an*xn [<=, ==, >=] b.

pure_lp_term(exp, bounds)

Rewrite term exp to a pure LP term.

Parameters

exp – is an Expression of the form (arith11 ^ … ^ arith1n) | … | (arithk1 ^ … ^ arithkn) where the degenerate cases are permitted as well.

Returns

(new-exp, support) where new-exp is a term, and support is a expressions of the following form. a1*x1 + … + an*xn [<=, ==, >=] b.

remove_and_or(exp)

Translate and/or operators into times/plus arithmetic.

Parameters

exp – is an Expression that takes one of the following forms. var [!]= term1 ^ … ^ termn var [!]= term1 | … | termn var [!]= term1 where termi is an indicator variable.

Returns

an expression equivalent to exp but without any ands/ors.

remove_and_or_term(exp)
upper_bound(expr, bounds)

Returns number giving an upper bound on the given expr.

Parameters

  • expr – is an Expression

  • bounds – is a dictionary from tuple versions of variables to the size of their upper bound.

classmethod variables(exp)
class congress.datalog.arithmetic_solvers.PulpLpLang

Bases: congress.datalog.arithmetic_solvers.LpLang

Algorithms for translating LpLang into PuLP library problems.

MIN_THRESHOLD = 1e-05
problem(optimization, constraints, bounds)

Return PuLP problem for given optimization and constraints.

Param

optimization is an LpLang.Expression that is either a sum or product to minimize.

Param

constraints is a collection of LpLang.Expression that each evaluate to true/false (typically equalities)

Param

bounds: is a dictionary mapping LpLang.Expression variable tuples to their upper bounds.

Returns a pulp.LpProblem.

pulpify(expr, variables, values)

Return PuLP version of expr.

Param

expr is an Expression of one of the following forms. arith arith = arith arith <= arith arith >= arith

Param

vars is a dictionary from Expression variables to PuLP variables

Returns a PuLP representation of expr.