INVITED TALKS
There will be three invited talks at this year’s conference.
Constraint Programming for Infeasibility Diagnosis in BARON
May 20th, 08:40 – 09:40
Nikolaos Sahindis – John E. Swearingen Professor of Chemical Engineering, Carnegie Mellon University
Joint work with Yash Puranik.
Abstract:
Since its inception in the early 1990s, the BARON global optimization solver was designed as a system that combined constraint programming and mathematical programming techniques for the global solution of algebraic nonlinear and mixed-integer nonlinear optimization problems (NLPs and MINLPs).
In this paper, we discuss recent developments in BARON, aiming to diagnose infeasibilities in nonconvex optimization models. Early work in the optimization literature to address the cause of infeasibilities has shown that the identification of Irreducible Inconsistent Sets (IIS) in a model can help speed up the process of correcting infeasible models. An Irreducible Inconsistent Set is defined as an infeasible set of constraints with every proper subset being feasible. Identifying an IIS provides the modeler with a set of mutual inconsistencies that need to be diagnosed. Currently, efficient implementations for IIS isolation are only available for linear programs (LPs).
We propose a novel approach for IIS identification that is applicable to NLPs and MINLPs. This approach makes use of constraint programming techniques in a computationally inexpensive preprocessing stage to test for infeasibility in subparts of the infeasible model. This stage allows for rapid elimination of a large number of constraints in the model. Further, this preprocessing step itself could be sufficient to eliminate all constraints not part of an IIS for a large number of problems. The reduced model obtained can be filtered with any standard IIS isolation algorithm to obtain an IIS. The benefits of the approach lie in the efficient reduction in the model obtained by the preprocessing stage which leads to speedups in IIS identification. Extensive computational results are presented with an implementation of the proposed preprocessing algorithm in BARON along with four different filtering algorithms: deletion filter, addition filter, addition-deletion filter and depth-first binary search filter.
IntSat: From SAT to Integer Linear Programming
May 21st, 08:40 – 09:40
Robert Nieuwenhuis – Professor of Computer Science, Technical University of Catalonia
Abstract:
One of the most remarkable successes in Artificial Intelligence (AI) and Constraint Programming (CP) is probably the combination of activity-based heuristics and learn- ing that allows Conflict-Driven Clause Learning (CDCL) propositional SAT solvers to solve, fully automatically, large and hard real-world industrial and scientific problems.
On the other hand, extremely powerful tools for Integer Linear Programming (ILP) and Mixed Integer Programming (MIP) exist, based on sophisticated techniques from Operations Research (OR), combining LP relaxations, simplex, branch-and-cut, including specialized cuts, heuristics and presolving methods, an extremely mature technology, with a 475000 times speedup between 1991 and 2012.
Since SAT is the particular case of ILP where all variables are binary (0-1) and constraints have the form x1 + … + xm − y1 … − yn > −n, (usually written as clauses x1 ∨ . . . ∨ xm ∨ y1 ∨ . . . ∨ yn , i.e., disjunctions of literals), some natural questions arise. Why do OR solvers perform so poorly on pure SAT problems? Can CDCL-based techniques also beat OR ones for richer ILP problems than just deciding SAT?
Indeed, an extensive amount of work exists on CDCL-like techniques for Pseudo-Boolean optimization (aka. 0-1 ILP). IntSat goes another step beyond, introducing a CDCL technique for full ILP (arbitrary integer variables, linear constraints and objective). IntSat extends CDCL by taking decisions on bounds (instead of literals), exhaustive bound propagation, and at each conflict it attempts to obtain by cuts a new ILP constraint, use it to backjump, and to learn it. This learning precludes “similar” future conflicts, which are ubiquitous in structured real-world problems (but not in randomly generated ones). IntSat appears to be the first method that is competitive, at least on certain ILP problem classes, with commercial OR tools such as CPLEX and Gurobi.
In this talk we will give an overview of CDCL-based SAT, the difficulties that arise when extending it, the key ideas behind IntSat, and several options between SAT and ILP, including Cutsat. Along the way we will address further questions: How to exploit (and control) learned ILP constraints? Are CDCL-based techniques superior on problems with a combinatorial flavor? Are OR techniques better for the rather numerical ones? We also contribute to the theoretical background: completeness of cut-related inference rules, and infeasibility (or refutation) proof complexity.
Symmetry in Integer Programming
May 22nd, 08:40 – 09:40
Jeff Linderoth – Professor of Industrial and Systems Engineering, University of Wisconsin-Madison
Joint work with Jim Ostrowski, Francois Margot, Fabrizio Rossi,Stefano Smriglio, and Greg Thain.
Abstract:
We will discuss mechanisms for dealing with integer programs that contain a great deal of symmetry. The methods use information encoded in the symmetry group of the integer program to guide the branching decision and prune nodes of the search tree. These methods are adaptations of similar methods used in the constraint programming community, and they have been adapted into commercial integer programming software. We will discuss some recent work on using symmetry to augment the cutting plane procedures of branch-and-cut based solvers, and we will conclude with a brief discussion of using large-scale distributed computing platforms to solve difficult symmetric integer programs.