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

摘要

We propose Constraint Synthesis with C-4.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 C-4.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. (C) 2018 Elsevier B.V. All rights reserved.