Automatic Synthesis of Constraints from Examples using Mixed Integer Linear Programming

Tomasz P. Pawlak, Krzysztof Krawiec

Abstract

Constraints form an essential part of most practical search and optimization problems, and are usually assumed to be given. However, there are plausible real-world scenarios in which constraints are not known or can be only approximated, for instance when the process in question is complex and/or noisy. To address such problems, we propose a method that synthesizes constrains from examples of feasible and infeasible solutions. The method can produce linear, quadratic and trigonometric constraints that are guaranteed to separate the feasible and infeasible regions and minimize the number of terms involved. The synthesized constraints are represented symbolically and can be used to simulate, predict or optimize the original process. We assess empirically several characteristics of the method on three benchmarks, in particular the fidelity and the complexity of the synthesized constraints with respect to the actual constraints. We also demonstrate its application to a real-world process of concrete manufacturing. Experiments demonstrate that the method is capable of producing human-readable constraints that reflect well the underlying process and can be used to simulate it.

Access full text

Full text is available at ScienceDirect.

BibTeX

@article{Pawlak20171141,
title = "Automatic synthesis of constraints from examples using mixed integer linear programming ",
journal = "European Journal of Operational Research ",
volume = "261",
number = "3",
pages = "1141 - 1157",
year = "2017",
note = "",
issn = "0377-2217",
doi = "https://doi.org/10.1016/j.ejor.2017.02.034",
url = "http://www.sciencedirect.com/science/article/pii/S037722171730156X",
author = "Tomasz P. Pawlak and Krzysztof Krawiec",
keywords = "Artificial intelligence",
keywords = "Constraint acquisition",
keywords = "Constraint learning",
keywords = "Model induction",
keywords = "Model generation "
}

Supplementary material

The C# source code of the experimental suite presented in the paper is available under conditions of Academic Free License. Visual Studio 2015+ is required to compile binaries from the source. Gurobi Solver 6.5 is required to run the software. This software runs on Mono 4.4+ under Linux.

Run the software using one of the following commands:

Modeling.MP.exe seed=[random_seed] benchmark=Modeling.Common.Benchmarks.[benchmark] samples=[ushort] preference=[C0_parameter] linear=[Boolean] quadratic=[Boolean] trigonometric=[Boolean] MaxConstraints=[int] SimplexIterLimit=[int] MIPNodeLimit=[int] TimeLimit=[seconds] output=[statistics.sqlite]
or:
Modeling.MP.exe seed=[random_seed] problem=[input.csv] preference=[C0_parameter] linear=[Boolean] quadratic=[Boolean] trigonometric=[Boolean] MaxConstraints=[int] SimplexIterLimit=[int] MIPNodeLimit=[int] TimeLimit=[seconds] output=[statistics.sqlite]

« back