Discrete Optimization of Min–Max Violation and its Applications Across Computational Sciences
Cheikh Ahmed, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou · 2025
Read Discrete Optimization of Min–Max Violation and its Applications Across Computational Sciences by Cheikh Ahmed, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13437.txt.
Introduction
Cheikh Ahmed and co-authors define a general optimization problem and a fast solver for it in a 2025 paper. The problem asks for a choice of discrete values that makes the worst broken rule as small as possible. Many fields need that worst-case view, from engineering to computing.
After setting out the math and its key traits, the team built a solver that runs on graphics hardware for speed. They tested it on three unlike tasks: shrinking language models, rebuilding images from slices, and designing electronic filters. The solver beat prior methods on each task, cutting errors and, for filters, nearly halving ripple compared with a leading commercial tool. The code will be released in public.
Catalog record
| CREATOR | Cheikh Ahmed, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13437
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Discrete Optimization of Min–Max Violation and its Applications Across Computational Sciences Cheikh Ahmed, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou Abstract We introduce the Discrete Min–Max Violation (DMMV) as a general optimization problem which seeks an assignment of discrete values to variables that minimizes the largest constraint violation. This context-free mathematical formulation is applicable to a wide range of use cases that have worst‐case performance requirements. After defining the DMMV problem mathematically, we explore its properties to establish a foundational understanding. To tackle DMMV instance sizes of practical relevance, we develop a GPU-accelerated heuristic that takes advantage of the mathematical properties of DMMV for speeding up the solution process. We demonstrate the versatile applicability of our heuristic by solving three optimization problems as use cases: (1) post-training quantization of language models, (2) discrete tomography, and (3) Finite Impulse Response (FIR) filter design. In quantization without outlier separation, our heuristic achieves 14% improvement on average over existing methods. In discrete tomography, it reduces reconstruction error by 16% under uniform noise and accelerates computations by a factor of 6 6 on GPU. For FIR filter design, it nearly achieves 50% ripple reduction compared to using the commercial integer optimization solver, Gurobi. Our comparative results point to the benefits of studying DMMV as a context-free optimization problem and the advantages that our proposed heuristic offers on three distinct problems. Our GPU-accelerated heuristic will be made open-source to further stimulate research on DMMV and its other applications. The code is available at https://anonymous.4open.science/r/AMVM-5F3E/ 1 Introduction Several real‐world engineering and Artificial Intelligence (AI) applications demand minimization of the worst‐case error over a finite set of choices. For example, post‐training quantization of Large Language Models (LLMs) involves choosing between discrete quantized weight and/or activation values ( Zhu et al. 2024 ; Lang, Guo, and Huang 2024 ; Jin et al. 2024 ) ; discrete tomography reconstructions are based on fixed grey‐level intensities ( Batenburg and Sijbers 2011 ) ; and Finite Impulse Response (FIR) filter design enforces a limited set of coefficient values when the hardware is constrained ( Oppenheim and Schafer 2009 ; Rabiner 1971 ) . Classically, worst‐case performance is addressed by continuous minimax \ell_{\infty} approximation ( Sainz et al. 2008 ; Qiu et al. 2017 ) . Given a system of linear equations Ax\approx b , the Chebyshev criterion seeks \min_{x\in\mathbb{R}^{n}}\|Ax-b\|_{\infty}, i.e., minimizing the magnitude of the largest residual error (maximum violation). This framework underpins a wide range of computational problems that can be explored from a continuous optimization standpoint. They include designing digital filters ( McClellan and Parks 1973 ) , developing robust statistical models ( Barrodale and Phillips 1975 ; Yi and Neykov 2024 ) , as well as other applications in mathematics ( Gillis and Shitov 2019 ; Morozov, Zheltkov, and Osinsky 2024 ) , image processing ( Kahl 2005 ) , and signal processing ( Kiambi, Mwangi, and Kamucha 2022 ) . When decision variables are to be chosen from a discrete set (e.g., integer values), continuous optimization theory no longer applies. Despite the ubiquity of discrete-valued decisions, the underlying optimization problem has received only ad-hoc treatments. Existing works either (i) relies on continuousness and deals with discreteness in a post-processing step ( Ito, Suyama, and Hirabayashi 2001 ) , or (ii) uses handcrafted task-specific heuristics ( Jensen 2001 ) . To the best of our knowledge, the literature lacks both a systematic, problem-agnostic analysis of discrete minimax approximation and a scalable, general-purpose algorithm to solve this problem. We therefore introduce the Discrete Min‐Max Violation (DMMV) problem as the natural extension of Chebyshev approximation to discrete domains and propose a competitive solution method for it. Figure 1: One iteration in our AMVM heuristic framework for solving a large-scale DMMV instance. The green components use GPU parallelization. Contributions This paper makes three key contributions. First, we provide a rigorous and context-free definition of the DMMV problem and establish its NP‐hardness. Second, we propose a GPU-accelerated heuristic, Accelerated Maximum Violation Minimizer (AMVM) , based on the adaptive large neighborhood search ( Ropke and Pisinger 2006 ) tailored for scalable solution of DMMV instances (Figure 1 ). Third, we empirically validate the relevance of our approach using comparison with use-case-specific baseline methods from three domains of application: (1) post‐training quantization of LLMs for edge devices ( Zhu et al. 2024 ) , discrete tomography ( Batenburg and Sijbers 2011 ) , and FIR filter design ( Oppenheim and Schafer 2009 ) . Main Results Our AMVM heuristic achieves 14% improvement on average over existing methods for quantization without outlier separation. In discrete tomography, it reduces reconstruction error by 16% under uniform noise and accelerates computations by a factor of 6 on GPU. For FIR filter design, it nearly achieves 50% ripple reduction compared to the commercial discrete optimization solver, Gurobi ( Gurobi Optimization LLC 2025 ) . Background and a brief literature review for each of these three use cases are provided after describing our solution approach. 2 Mathematical Problem Statement The discrete Min-Max violation problem seeks to find values for vector \mathbf{x} out of the discrete set \mathbb{V} to minimize the maximum absolute difference between \mathbf{Ax} and a target vector \mathbf{b} . This is formally expressed using the \ell_{\infty} -norm as: \min_{\mathbf{x}\in\mathbb{V}^{n}}\left\lVert\mathbf{Ax}-\mathbf{b}\right\rVert_{\infty} where A\in\mathbb{R}^{m\times n} is a real-valued matrix, \mathbf{b}\in\mathbb{R}^{m} is a real-valued vector, and \mathbf{x}\in\mathbb{V}^{n} is the vector of decision variables. While the \ell_{\infty} -norm objective is non-linear, the DMMV problem can be reformulated as a Mixed-Integer Linear Program (MILP) . This reformulation is obtained by introducing a single, non-negative continuous variable, t\in\mathbb{R} , which represents the value of the maximum violation. The problem then reduces to: \displaystyle\min_{\mathbf{x},t}\quad \displaystyle t s.t. \displaystyle\mathbf{Ax}-\mathbf{b}\leq t\mathbf{1} \displaystyle\mathbf{Ax}-\mathbf{b}\geq-t\mathbf{1} \displaystyle\mathbf{x}\in\mathbb{V}^{n},\quad t\geq 0. Theorem 1 . The Discrete Min-Max Violation (DMMV) problem is NP-hard. To prove this theorem, we analyze the complexity of the corresponding decision problem, defined as follows. Definition 1 (The Decision Version of DMMV) . Given a matrix A\in\mathbb{R}^{m\times n} , a vector b\in\mathbb{R}^{m} , a finite set of allowed values \mathbb{V}\subset\mathbb{R} , and a threshold t\in\mathbb{R} , the decision problem \text{DMMV}_{\infty} asks if there exists a vector x\in\mathbb{V}^{n} such that \|Ax-b\|_{\infty}\leq t . \textsc{DMMV}_{\infty}=\bigl\{(A,b,\mathbb{V},t)\;\bigm|\;\exists\,x\in\mathbb{V}^{n}:\|Ax-b\|_{\infty}\leq t\bigr\}. We now prove that \text{DMMV}_{\infty} is NP-complete. The NP-hardness of the original DMMV optimization problem follows directly from this result. Proof. (1) Membership in NP. Given an instance (A\in\mathbb{R}^{m\times n},\,b\in\mathbb{R}^{m},\,\mathbb{V}\subset\mathbb{R},\,t\in\mathbb{R}) and a certificate x\in\mathbb{V}^{n} , we compute r=Ax-b\quad\text{in }O(mn)\text{ time} . Then, we compute \max_{1\leq i\leq m}|r_{i}| in O(m) , and check \max_{i}|r_{i}|\leq t . Thus, \textsc{DMMV}_{\infty}\in\mathrm{NP} . (2) NP‐hardness by reduction from Subset‐Sum. Recall the Subset‐Sum problem ( Kleinberg and Tardos 2005 ) : Given a_{1},\dots,a_{n}\in\mathbb{Z}_{>0},\,S\in\mathbb{Z}_{>0}, decide if \sum_{i\in I}a_{i}=S\text{ for some }I\subseteq\{1,\dots,n\}. Construct an instance of \textsc{DMMV}_{\infty} as follows: m=1,\quad D=\{0,1\},\quad A=[a_{1}\;\;a_{2}\;\dots\;a_{n}]\in\mathbb{R}^{1\times n},\quad b=[S]\in\mathbb{R},\quad t=0. Then for any x\in\{0,1\}^{n} , \|Ax-b\|_{\infty}\leq 0\;\Longleftrightarrow\;Ax=b\;\Longleftrightarrow\;\sum_{i=1}^{n}a_{i}x_{i}=S. Hence Subset‐Sum has a solution if and only if \|Ax-b\|_{\infty}\leq 0 . This reduction runs in O(n) time, proving NP‐hardness. (3) Conclusion. We showed that the decision version of \textsc{DMMV}_{\infty} (i.e., asking whether there exists a solution with objective value \leq k ) is in NP and NP‐hard, and hence NP‐complete. It follows that the corresponding DMMV optimization problem is NP‐hard. ∎ 3 Solution Approach To address large-scale instances of the DMMV problem, we