facet-defining inequality

A polyhedral study of multivariate decision trees

  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Theory, Polyhedra Tags , ,

    Decision trees are a widely used tool for interpretable machine learning. Multivariate decision trees employ hyperplanes at the branch nodes to route datapoints throughout the tree and yield more compact models than univariate trees. Recently, mixed-integer programming (MIP) has been applied to formulate the optimal decision tree problem. To strengthen MIP formulations, it is crucial … Read more

    New Inequalities for Finite and Infinite Group Problems from Approximate Lifting

  • Yanjun Li
  • Jean-Philippe P. Richard
  • Lisa A. Miller
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , , , ,

    In this paper, we derive new families of piecewise linear facet-defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem are two- and three-slope facet-defining inequalities as well as the first family of four-slope facet-defining inequalities. The new … Read more