|
Polynomial 0-1 Optimization It is an NP-hard problem to
optimize a polynomial over binary variables, even without further
constraints. This is already true in the quadratic case, where the
problem is equivalent to the maximum cut problem. The maximum cut
problem and the corresponding cut polytope have been investigated
intensively. In our project, we developed a general method that allows
to transfer polyhedral results on the cut polytope to the case of
arbitrary degree. For this, we extend the standard linearization of an
arbitrary polynomial problem such that the corresponding polytope
becomes a face of some slightly larger cut polytope. In particular, the general
separation problem reduces to the separation problem for max cut. The
implementation of this approach within a branch-and-cut framework
yields optimal solutions significantly faster than other methods.
Logic Optimization In a second step, we were able to
generalize these results to arbitrary logic optimization
problems. More precisely, instead of multiplications, we allow
arbitrary binary operators, which may be nested in an arbitrary
way. Special cases include the maximum satisfiability problem and the
problem of deciding equivalence of logical formulae.
Our experiments for max sat show that this approach can outperform
even problem-specific solvers, despite of its very general
nature. Currently, we are evaluating our implementation in the context
of other applications.
|
