One-class synthesis of constraints for Mixed-Integer Linear Programming with C4.5 decision trees

Patryk Kudła, Tomasz P. Pawlak

Abstract

We propose Constraint Synthesis with C4.5 (CSC4.5), a novel method for automated construction of constraints for Mixed-Integer Linear Programming (MILP) models from data. Given a sample of feasible states of a modeled entity, e.g., a business process or a system, CSC4.5 synthesizes a well-formed MILP model of that entity, suitable for simulation and optimization using an off-the-shelf solver. CSC4.5 operates by estimating the distribution of the feasible states, bounding that distribution with C4.5 decision tree and transforming that tree into a MILP model. We verify CSC4.5 experimentally using parameterized synthetic benchmarks, and conclude considerable fidelity of the synthesized constraints to the actual constraints in the benchmarks. Next, we apply CSC4.5 to synthesize from past observations two MILP models of a real-world business process of wine production, optimize the MILP models using an external solver and validate the optimal solutions with use of a competing modeling method.

Access full text

Full text is available at ScienceDirect.

BibTeX

@article{Kudla2018,
title = "One-class synthesis of constraints for Mixed-Integer Linear Programming with C4.5 decision trees ",
journal = "Applied Soft Computing ",
volume = "68",
number = "",
pages = "1 - 12",
year = "2018",
note = "",
issn = "1568-4946",
doi = "https://doi.org/10.1016/j.asoc.2018.03.025",
url = "https://www.sciencedirect.com/science/article/pii/S1568494618301479",
author = "Patryk Kud\l{}a and Tomasz P. Pawlak",
keywords = "Model acquisition",
keywords = "Constraint synthesis",
keywords = "Mathematical programming",
keywords = "One-class classification",
keywords = "Business process "
}

Supplementary material

The C# source code and datasets are available at GitHub repository.

« back