Computing Approximate Solutions of Inconsistent Max-Min Fuzzy Relational Equations by Mixed-Integer Programming
Abstract
We study how to compute approximate solutions of inconsistent systems of max-min fuzzy relational equations with respect to the L1 and L2 norms using mixed-integer programming. We assign one error bound to each equation and collect these bounds into a vector. We call this error-bound vector admissible if there exists a right-hand side vector that defines a consistent max-min system with the original matrix and satisfies the prescribed componentwise error bounds relative to the original right-hand side vector. We characterize admissibility and, for every admissible error-bound vector, we explicitly construct such a right-hand side vector and a solution of the resulting consistent system. We also identify, for each equation, column indices that can be discarded from the admissibility criterion. This allows us to reformulate the L1 and L2 approximation problems as equivalent optimization problems over the set of admissible error-bound vectors. We show that the set of admissible error-bound vectors is a finite union of non-empty compact polytopes, and we describe their structure. We then derive an exact mixed-integer linear representation of this set, yielding an exact mixed-integer linear program (MILP) for the L1 problem and an exact mixed-integer quadratic program (MIQP) with a convex quadratic objective for the L2 problem. The results extend to min-max systems, and computational experiments on synthetic data show improved performance of the proposed MIQP formulation compared with two existing formulations on the tested instances.
Related
- A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Approximate Dynamic Programming for Real-time Assignment of Extraboard Transit Operators
- Computing Invariant Reachable Sets through Sum-of-Squares Programming
- Computing Equilibria in Integer Programming Games with Shared Constraints
BibTeX
@misc{baaj2026computing,
title = {{Computing Approximate Solutions of Inconsistent Max-Min Fuzzy Relational Equations by Mixed-Integer Programming}},
author = {Ismaïl Baaj},
howpublished = {HAL},
year = {2026},
month = nov,
url = {https://hal.science/hal-05847442v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Computing Approximate Solutions of Inconsistent Max-Min Fuzzy Relational Equations by Mixed-Integer Programming
AU - Ismaïl Baaj
PY - 2026
DA - 2026/11/01
PB - HAL
UR - https://hal.science/hal-05847442v1
AB - We study how to compute approximate solutions of inconsistent systems of max-min fuzzy relational equations with respect to the L_1 and L_2 norms using mixed-integer programming. We assign one error bound to each equation and collect these bounds into a vector. We call this error-bound vector admissible if there exists a right-hand side vector that defines a consistent max-min system with the original matrix and satisfies the prescribed componentwise error bounds relative to the original right-hand side vector. We characterize admissibility and, for every admissible error-bound vector, we explicitly construct such a right-hand side vector and a solution of the resulting consistent system. We also identify, for each equation, column indices that can be discarded from the admissibility criterion. This allows us to reformulate the L_1 and L_2 approximation problems as equivalent optimization problems over the set of admissible error-bound vectors. We show that the set of admissible error-bound vectors is a finite union of non-empty compact polytopes, and we describe their structure. We then derive an exact mixed-integer linear representation of this set, yielding an exact mixed-integer linear program (MILP) for the L_1 problem and an exact mixed-integer quadratic program (MIQP) with a convex quadratic objective for the L_2 problem. The results extend to min-max systems, and computational experiments on synthetic data show improved performance of the proposed MIQP formulation compared with two existing formulations on the tested instances.
ER -