Heilbronn triangle problem

From Computational Certification to Exact Coordinates: Heilbronn’s Triangle Problem on the Unit Square Using Mixed-Integer Optimization

  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop a mixed-integer nonlinear programming (MINLP) approach for the classical Heilbronn triangle problem, demonstrating the capability of modern global optimization solvers to tackle challenging combinatorial geometry problems. A symmetry-breaking strategy based on boundary structure yields a substantially stronger model: for n=9, we compute an epsilon-globally optimal point in 15 minutes on a standard desktop … Read more

    Solving the Heilbronn Triangle Problem using Global Optimization Methods

  • Burak Kocuk
  • Amirali Modir
  • Amirhossein Monji
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications Tags , , , ,

    We study the Heilbronn triangle problem, which involves placing \(n\) points in the unit square such that the minimum area of any triangle formed by these points is maximized. A straightforward maximin formulation of this problem is highly non-linear and non-convex due to the existence of bilinear terms and absolute value equations. We propose two … Read more