Novel constraint synthesis methods for integer programs

点击翻译按钮获取中文摘要

Integer Programming is a broadly applicable mathematical modelling technique that looks for integral solutions to systems of linear inequalities. The standard integer programming benchmark suite MIPLIB includes applications from scheduling (academic timetables, trains, airline crews, nurse/doctor rostering), computational systems biology, water system planning, vehicle routing, and statistical disclosure control. Integer programming models are processed by sophisticated solvers, primarily based on branch-and-bound and the incremental addition of constraints called cutting planes. Many problems of interest remain out of reach: 286 of the 1065 MIPLIB collection are unsolved as of this writing. In this proposal new techniques for solving and modelling (i.e. constructing sets of constraints for) integer programs are explored under the umbrella of constraint synthesis i.e. generating constraints from high level input. The proposed techniques promise to extend the reach of existing solvers to new problem classes. A set of candidates is called a coreset (or set of core points) for some problem if solving the problem on this set gives the same answer as considering the entire search space. Recently several authors have developed coreset methods for solving integer programs based on input symmetry; problem symmetries occur in practice when relabellings of the input yield equivalent problem structure. This equivalent problem structure causes repeated work for branching solvers, and state of the art commercial and research solvers make efforts to break the symmetries in various ways. Instead of seeing symmetry as a problem, coreset techniques seek to exploit it to solve integer programs faster. In the most direct approach, core points are enumerated and tested individually. Current research on core points for integer programming is mainly focused on bounding the number core points (or the number of equivalence classes). I propose to explore a new approach based on outer approximation, in particular based on the synthesis of constraints that describe the set of core points. This has the potential to make new classes of integer programs solvable, and is of interest to both solver writers and practitioners (i.e. people with integer programs to solve). While integer programming is a very general problem solving method, the process of modelling, or constructing input for a solver can be challenging, and the tractability of an instance can depend on the skill (and luck) of the modeller. I propose to develop a compiler to synthesize constraints from a simple procedural description of the feasible points. Based on recent work in extended formulations, this represents a kind of dual to the standard procedural approach of generating the constraints directly. We plan to integrate the new modelling tool into an existing algebraic (declarative) modelling language to make it available to practitioners in a solver independent way.