Algorithms – Optimization Online

Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

Published: 2025/10/14

(Mixed) Integer Linear Programming, Combinatorial Optimization, Meta Heuristics algorithm design, Algorithms, Heuristic Discovery, Knowledge Discovery, Large Language Models (LLMs), MIP, optimization, Single Machine Total Tardiness Scheduling

TitleDiscovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling Authorsİbrahim Oğuz Çetinkaya^1; İ. Esra Büyüktahtakın^1*; Parshin Shojaee^2; Chandan K. Reddy^2 Affiliations^1 Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, USA^2 Department of Computer Science, Virginia Tech, Arlington, VA, USA Abstract: Our study contributes to the scheduling and combinatorial optimization … Read more

A general merit function-based global convergent framework for nonlinear optimization

Published: 2024/12/05

Thiago Siqueira Santos

Nonlinear Optimization Algorithms, complexity, global convergence, inexact restoration, numerical experiments, sequential quadratic programming

In this paper, we revisit the convergence theory of the inexact restoration paradigm for non-linear optimization. The paper first identifies the basic elements of a globally convergent method based on merit functions. Then, the inexact restoration method that employs a two-phase iteration is introduced as a special case. A specific implementation is presented that is … Read more

Efficient Approximation Quality Computation for Sandwiching Algorithms for Convex Multicriteria Optimization

Published: 2023/10/05, Updated: 2025/01/23

Ina Lammel

Karl-Heinz Küfer

Philipp Süss

Convex Optimization, Multi-Criteria Optimization Algorithms, multicriteria optimization, polyhedral approximation, quality indicator

Computing the approximation quality is a crucial step in every iteration of Sandwiching algorithms (also called Benson-type algorithms) used for the approximation of convex Pareto fronts, sets or functions. Two quality indicators often used in these algorithms are polyhedral gauge and epsilon indicator. In this article, we develop an algorithm to compute the polyhedral gauge … Read more

A Voronoi-Based Mixed-Integer Gauss-Newton Algorithm for MINLP Arising in Optimal Control

Published: 2022/12/02

(Mixed) Integer Nonlinear Programming, Control Applications, Nonlinear Systems and Least-Squares Algorithms, mixed-integer optimal control problems

We present a new algorithm for addressing nonconvex Mixed-Integer Nonlinear Programs (MINLPs) where the cost function is of nonlinear least squares form. We exploit this structure by leveraging a Gauss-Newton quadratic approximation of the original MINLP, leading to the formulation of a Mixed-Integer Quadratic Program (MIQP), which can be solved efficiently. The integer solution of the … Read more

Global Convergence of Algorithms Under Constant Rank Conditions for Nonlinear Second-Order Cone Programming

Published: 2021/10/22, Updated: 2022/04/16

Constrained Nonlinear Optimization, Second-Order Cone Programming Algorithms, constant rank, constraint qualifications, global convergence, second-order cone programming

In [R. Andreani, G. Haeser, L. M. Mito, H. Ramírez C., Weak notions of nondegeneracy in nonlinear semidefinite programming, arXiv:2012.14810, 2020] the classical notion of nondegeneracy (or transversality) and Robinson’s constraint qualification have been revisited in the context of nonlinear semidefinite programming exploiting the structure of the problem, namely, its eigendecomposition. This allows formulating the … Read more