Constraint Integer Programming in Sage

Now that version 4.6.2 of Sage is out which contains the new Mixed Integer Programming interface that Nathann (mainly) and I (a little bit) wrote, I took the time to get my SCIP interface enough into shape to open a ticket on Sage’s bugtracker for it.For those who don’t know SCIP, here’s how its developers describe it:

“SCIP is currently one of the fastest non-commercial mixed integer programming (MIP) solvers. It is also a framework for Constraint Integer Programming andbranch-cut-and-price. It allows total control of the solution process and the access of detailed information down to the guts of the solver.”

The new interface to SCIP is on the C-level and thus supports some of the advanced features SCIP has. For example, it supports the following constraints:

  • linear constraints,
  • quadratic constraints,
  • set covering, packing and partitioning,
  • AND, XOR and OR constraints, and
  • logical OR constraints.

There is no reason that this list isn’t complete other than that I was too lazy to write e.g. the knapsack constraint. However, adding this is pretty straight forward (hint, hint). I also added support for setting/getting/reading/writing SCIP parameters:

sage: from sage.libs.scip.scip import SCIP
sage: scip = SCIP()
sage: scip['display/verblevel'] = 0
sage: scip['display/verblevel']
0
sage: scip.write_parameters("foo.cfg")

Of course, the interface is also compatible with Sage’s highlevel MixedIntegerProgramming class, such that it can be used as a backend for all functions that make use of Mixed Integer Programming in Sage already (such as Graph theoretic questions). Finally, the interface also has an interface for reading and solving polynomial systems of equations mod p (I wouldn’t hold my breath for solving mod p with p > 2 though, this is very inefficient).

sage: sr = mq.SR(1,1,1,4,gf2=True,polybori=True)
sage: F,s = sr.polynomial_system()
sage: scip = SCIP()
sage: m1 = scip.read_polynomial_system_mod2(F)
sage: scip.solve()
0
sage: for x in F.ring().gens():
....:     print x,scip.get_variable_value(m1.down(x))
....:
k100 1.0
k101 1.0
k102 1.0
k103 0.0
x100 1.0
x101 0.0
x102 0.0
x103 0.0
w100 1.0
w101 1.0
w102 1.0
w103 1.0
s000 1.0
s001 1.0
s002 0.0
s003 0.0
k000 1.0
k001 0.0
k002 1.0
k003 0.0
sage: F.groebner_basis()
[k100 + 1, k101 + k003 + 1, k102 + k003 + 1, k103 + k003,
x100 + 1, x101 + k003, x102, x103, w100 + 1, w101 + k003 + 1,
w102 + 1, w103 + k003 + 1, s000 + 1, s001 + k003 + 1, s002, s003,
k000 + 1, k001 + k003, k002 + 1]



There are some issues with this interface though:

  • some stuff simply isn’t done yet, e.g. printing of quadratic constraints
  • it crashes horribly under OSX (help by someone who runs & cares about OSX would be highly appreciated)

Btw. this interface was also used in our paper  Cold Boot Key Recoveryby Solving Polynomial Systems with Noise.

Advertisements

2 thoughts on “Constraint Integer Programming in Sage”

  1. Dear Martin,

    did you do some further work on SCIP or do you know of someone else who continued your work? Just recently, I got to know Sage and must say that I quite like it.
    I am a PhD student at ZIB, working on SCIP and SoPlex and we just created our own basic python interfaces. An integration into Sage would b very interesting!

    All the best
    Matthias

    1. Hi Matthias, I didn’t continue and as far as I know no one else picked up this work. That said, you should probably send an e-mail to [sage-devel] to ask. I’d also be happy to help, it’s good to see that you guys are interested in integration.

      Cheers,
      Martin

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s