Elif Garajová and Milan Hladík. Inside the box: 0-1 linear programming under interval uncertainty. In Y. D. Sergeyev and others, editors, Numerical Computations: Theory and Algorithms. NUMTA 2023, LNCS, pp. 312–319, Springer, Cham, 2025.
[PDF] [gzipped postscript] [postscript] [HTML]
Many practical optimization problems require models that are able to reflect uncertainty or inexactness inherently present in the data. Interval linear programming provides a model for handling uncertain optimization problems, in which one assumes that only lower and upper bounds on the input data are available and the data can be independently perturbed within the intervals determined by the given bounds. Apart from the linear programming models with continuous variables, which have been explored by various authors, intervals also often arise in discrete optimization problems. We adopt the model of integer linear programming with binary variables, in which the constraint matrix, objective vector and right-hand-side vector are affected by interval uncertainty. For this model, only a few works investigating its properties can be found in the literature. In this paper, we discuss the main concepts of feasibility and optimality in the model and discuss their properties. Namely, we address the problem of computing the set and the range of optimal values and characterizing weak optimality of solutions.
@inCollection{GarHla2025a,
author = "Elif Garajov\'{a} and Milan Hlad\'{\i}k",
title = "Inside the box: 0-1 linear programming under interval uncertainty",
editor = "Y. D. Sergeyev and others",
feditor = "Sergeyev, Y. D. and Kvasov, D. E. and Astorino, A.",
sbooktitle = "NUMTA 2023",
booktitle = "Numerical Computations: Theory and Algorithms. NUMTA 2023",
publisher = "Springer",
address = "Cham",
series = "LNCS",
fseries = "Lecture Notes in Computer Science",
volume = "14476",
pages = "312-319",
year = "2025",
doi = "10.1007/978-3-031-81241-5_24",
isbn = "978-3-031-81241-5",
url = "https://link.springer.com/chapter/10.1007/978-3-031-81241-5_24",
bib2html_dl_html = "https://doi.org/10.1007/978-3-031-81241-5_24",
bib2html_dl_pdf = "https://rdcu.be/d5pqr",
abstract = "Many practical optimization problems require models that are able to reflect uncertainty or inexactness inherently present in the data. Interval linear programming provides a model for handling uncertain optimization problems, in which one assumes that only lower and upper bounds on the input data are available and the data can be independently perturbed within the intervals determined by the given bounds. Apart from the linear programming models with continuous variables, which have been explored by various authors, intervals also often arise in discrete optimization problems. We adopt the model of integer linear programming with binary variables, in which the constraint matrix, objective vector and right-hand-side vector are affected by interval uncertainty. For this model, only a few works investigating its properties can be found in the literature. In this paper, we discuss the main concepts of feasibility and optimality in the model and discuss their properties. Namely, we address the problem of computing the set and the range of optimal values and characterizing weak optimality of solutions.",
keywords = "Integer programming; Interval uncertainty; Optimality",
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Nov 07, 2025 16:53:24