Elif Garajová, Milan Hladík, and Miroslav Rada. 0-1 Linear programming under interval uncertainty. Soft Comput., 29(7):3691–3704, April 2025.
[PDF] [gzipped postscript] [postscript] [HTML]
We study the model of an integer linear program with binary variables within the framework of interval programming, which can be used to represent various optimization problems whose input data are affected by interval-valued uncertainty. In the considered model, the inexact or uncertain coefficients of the integer program can be independently perturbed within the given lower and upper bounds. In this paper, we characterize the main properties of 0-1 interval linear programs with respect to feasibility and optimality. Namely, we discuss the feasible and optimal solutions in the weak and in the strong sense, i.e. solutions feasible or optimal for some or for each choice of the interval data. We also address the problem of computing the best and the worst optimal value, as well as the related problem of describing the possibly disconnected set of all optimal values. Due to the dependency problem inherently present in interval programming, we study formulations involving both equations and inequality constraints. Moreover, we prove that for pure 0-1 interval linear programs the standard transformation of splitting an equation constraint into two opposite inequalities preserves the set of (weakly) optimal solutions, which is generally not true for interval linear programs with continuous variables.
@article{GarHla2025b,
author = "Elif Garajov\'{a} and Milan Hlad\'{\i}k and Miroslav Rada",
title = "0-1 Linear programming under interval uncertainty",
journal = "Soft Comput.",
fjournal = "Soft Computing",
volume = "29",
number = "7",
pages = "3691-3704",
month = "April",
year = "2025",
doi = "10.1007/s00500-025-10625-9",
issn = "1432-7643",
issnonline = "1433-7479",
url = "https://doi.org/10.1007/s00500-025-10625-9",
bib2html_dl_html = "https://link.springer.com/article/10.1007/s00500-025-10625-9",
bib2html_dl_pdf = "https://rdcu.be/etC6B",
abstract = "We study the model of an integer linear program with binary variables within the framework of interval programming, which can be used to represent various optimization problems whose input data are affected by interval-valued uncertainty. In the considered model, the inexact or uncertain coefficients of the integer program can be independently perturbed within the given lower and upper bounds. In this paper, we characterize the main properties of 0-1 interval linear programs with respect to feasibility and optimality. Namely, we discuss the feasible and optimal solutions in the weak and in the strong sense, i.e. solutions feasible or optimal for some or for each choice of the interval data. We also address the problem of computing the best and the worst optimal value, as well as the related problem of describing the possibly disconnected set of all optimal values. Due to the dependency problem inherently present in interval programming, we study formulations involving both equations and inequality constraints. Moreover, we prove that for pure 0-1 interval linear programs the standard transformation of splitting an equation constraint into two opposite inequalities preserves the set of (weakly) optimal solutions, which is generally not true for interval linear programs with continuous variables.",
keywords = "Integer programming; Interval uncertainty; Optimality; Transformations",
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Nov 07, 2025 16:53:24