python-zibopt

Author:Ryan J. O’Neil <ryanjoneil@gmail.com> Version:0.7.2-dev Website:http://code.google.com/p/python-zibopt/

Python Interface to the ZIB Optimization Suite

License

This software is released under the GPL 3.0.

Components of the ZIB Optimization Suite which this software links against are distributed by ZIB under the ZIB Academic License. Please see http://zibopt.zib.de/ for more information about this license.

Modeling Interface

These modules and classes constitute the interface typically used by a modeler.

zibopt.scip

This module provides a Python interface to the SCIP mixed integer programming solver of the ZIB optimization suite. It defines two classes for use by the modeler:

• scip.solver: interface to SCIP
• scip.solution: IP solutions returned by solver.minimize/maximize

There are type constants defined for declaring variables:

• BINARY: variable can be either 0 or 1
• INTEGER: variable can take only integer values
• IMPLINT: variable takes only integer values implicitly
• CONTINUOUS: variable can take fractional values

Basic usage of python-zibopt involves constructing a solver, adding variables and constraints to it, then calling minimize or maximize. SCIP varialbles are wrapped in Python variables and can be referenced as such. Note that the value of a given variable for a given solution to an IP is not set in the Python variable itself, but in the solution values. This is because each variable may be able to take on multiple values for an IP.

A simple IP model in ZIMPL might like look:

var x1 integer >= 0 <= 2;
var x2 integer >= 0;
var x3 integer >= 0;

maximize z: x1 + x2 + 2*x3;
subto c: x1 + x2 + 3*x3 <= 3;

Translated to python-zibopt this becomes:

from zibopt import scip
solver = scip.solver()

# All variables have default lower bounds of 0
x1 = solver.variable(scip.INTEGER)
x2 = solver.variable(scip.INTEGER)
x3 = solver.variable(scip.INTEGER)

# x1 has an upper bound of 2
solver += x1 <= 2

# Add a constraint such that:  x1 + x2 + 3*x3 <= 3
solver += x1 + x2 + 3*x3 <= 3

# The objective function is: z = x1 + x2 + 2*x3
solution = solver.maximize(objective=x1 + x2 + 2*x3)

# Print the optimal solution if it is feasible.
if solution:
    print('z  =', solution.objective)
    print('x1 =', solution[x1])
    print('x3 =', solution[x2])
    print('x2 =', solution[x3])
else:
    print('invalid problem')

zibopt.scip.solver

class zibopt.scip.solver(*args, **kwds)

Instantiates a A SCIP mixed integer programming solver with default settings. Parameters:

• quiet=True: turns the SCIP solver output off

Normal behavior is to instantiate a solver, define variables and constraints for it, and then maximize or minimize an objective function.

constrain(constraint)

Adds a constraint back into the solver. Returns None. Parameters:

• constraint: constraint instance to reinstall

constraint(expression)

Adds a constraint to the solver. Returns the constraint. The user can create the constraint out of keyword arguments or algebraically. For instance, the following two statements are equivalent:

solver.constraint(x1 + 2*x2 <= 4)

solver.constraint(
    expression(
        terms = {
            (x1,): 1.0,
            (x2,): 2.0
        },
        upper = 4
    )
)

Parameters:

• expression: python-algebraic expression instance

maximize(*args, **kwds)

Maximizes the objective function and returns a solution instance. Parameters:

• objective: optional algebraic representation of objective function. Can also use variable coefficients.
• solution={}: optional primal solution dictionary. Raises a SolverError if the solution is infeasible.
• time=inf: optional time limit for solving
• gap=0.0: optional gap percentage to stop solving (ex: 0.05)
• absgap=0.0: optional primal/dual gap to stop solving
• nsol=-1: number of solutions to find before stopping

minimize(*args, **kwds)

Minimizes the objective function and returns a solution instance. Parameters:

• objective: optional algebraic representation of objective function. Can also use variable coefficients.
• solution={}: optional primal solution dictionary. Raises a SolverError if the solution is infeasible.
• time=inf: optional time limit for solving
• gap=0.0: optional gap percentage to stop solving (ex: 0.05)
• absgap=0.0: optional primal/dual gap to stop solving
• nsol=-1: number of solutions to find before stopping

unconstrain(constraint)

Removes a constraint from the solver. Returns None. Parameters:

• constraint: constraint instance to remove

variable(vartype=3, coefficient=0, lower=0, **kwds)

Adds a variable to the SCIP solver and returns it. Parameters:

• vartype=CONTINUOUS: type of variable
• coefficient=0: objective function coefficient
• lower=0: lower bound on variable
• upper=+inf: upper bound on variable
• priority=0: branching priority for variable

zibopt.scip.solution

class zibopt.scip.solution(solver)

A solution to a mixed integer program from SCIP. Solution values can be obtained using variable references from the solver:

x1_value = solution[x1]

If a solution is infeasible or unbounded, it will be false when evaluated in boolean context:

if solution:
    # do something interesting

Solutions can be tested for optimality using the solution.optimal boolean. Available solution statuses include:

• solution.optimal: solution is optimal
• solution.infeasible: no feasible solution could be found
• solution.unbounded: solution is unbounded
• solution.inforunbd: solution is either infeasible or unbounded

Solver Settings

Solver settings for things like branching rules are accessible through dictionaries on the solver. For instance, to change settings on the inference branching rule:

solver.branching['inference'].priority = 10000
solver.branching['inference'].maxdepth = -1
solver.branching['inference'].maxbounddist = -1

Heuristcs allow priority, max depth, frequency, and frequency offset (freqofs) to be set:

solver.heuristics['octane'].priority = 500
solver.heuristics['octane'].maxdepth = -1
solver.heuristics['octane'].frequency = 10
solver.heuristics['octane'].freqofs = 5

Node selectors have standard and memory saving priority:

solver.selectors['bfs'].stdpriority = 1000
solver.selectors['bfs'].memsavepriority = 10

Propagotors allow priority and frequencey to be set:

solver.propagators['pseudoobj'].priority = 1000
solver.propagators['pseudoobj'].frequency = 10

Separators have settinsg for priority, maxbounddist, and frequency:

solver.separators['clique'].priority = 10000
solver.separators['clique'].maxbounddist = -1
solver.separators['clique'].frequency = 10000

Priority can also be set on conflict handlers and presolvers:

solver.conflict['logicor'].priority = 10000
solver.presolvers['dualfix'].priority = 10000

Display settings can also be set for solver output. These are useful when passing quiet=False on solver instantiation:

solver = scip.solver()
solver.display['cuts'].priority = 5
solver.display['cuts'].width = 10
solver.display['cuts'].position = 3

See the SCIP documentation for available branching rules, heuristics, any other settings, and what they do.

Internal Classes

These classes are used in implementation of python-zibopt. They may also be useful for more advanced modeling needs, but are more likely to change interfaces.

zibopt.scip.variable

class zibopt.scip.variable(*args, **kwds)

Provides a hashable and orderable Python connector to SCIP variables.

zibopt.scip.constraint

class zibopt.scip.constraint(solver, expr)

Stores bounds and coefficients for problem formulations. Valid constraints for SCIP include linear and bilinear terms. Examples:

solver += 4 * (x + y) * (x + z) <= 10
solver += 3*x**2 - 4*x >= 5*y
solver += 3 <= 4*y <= 5