symbolic computation

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 an optimize-then-refine framework for the classical Heilbronn triangle problem that integrates global mixed-integer nonlinear programming with exact symbolic computation. A novel symmetry-breaking strategy, together with the exploitation of structural properties of determinants, yields a substantially stronger optimization model: for n=9, the problem can be solved to certified global optimality in 15 minutes on … Read more

    Linear Programming using Limited-Precision Oracles

  • Ambros Gleixner
  • Daniel E. Steffy
    • Categories Linear Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations … Read more