AI in Society, Science, and Technology
Refine
Document Type
- Article (78)
- In Proceedings (56)
- ZIB-Report (16)
- In Collection (2)
- Master's Thesis (2)
- Research data (1)
Language
- English (155)
Keywords
Institute
- AI in Society, Science, and Technology (155)
- Mathematical Algorithmic Intelligence (38)
- Mathematical Optimization (12)
- Applied Algorithmic Intelligence Methods (6)
- Network Optimization (6)
- Modeling and Simulation of Complex Processes (4)
- Numerical Mathematics (3)
- Computational Nano Optics (2)
- Digital Data and Information for Society, Science, and Culture (1)
- Mathematical Optimization Methods (1)
This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition’s format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems.
In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT.