Obtaining the Maximum and Minimum and their Orders, Ordering and the Histogram of an Array of Real Numbers with a MILP Model

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Downloads (Pure)

Abstract

In a previous work we solved the same problem with real numbers with limited precision, but we did not consider the possibility of repetitions. In this paper we used a new, simpler and more efficient approach where the coherence between the original set and the ordered set is guaranteed by an auxiliary indexed binary variable and two sets of constraints that implement the restriction to a binary variable, a linearization technique developed in a previous work [1]. We also obtained the order in the original set of each element of the ordered set, the maximum(s) and minimum(s) and their orders with another auxiliary indexed binary variable and two sets of constraints and obtained the histogram of the original set of real numbers. Then we presented some examples of computational experiments that show that this new approach is more efficient in terms of runtime and memory usage. Finally we point as the improvement of the histogram calculation as the near future work.
Original languageEnglish
Title of host publicationProceedings of APMOD 2016
Publication statusPublished - 2016

Fingerprint

Mixed Integer Linear Programming
Histogram
Binary Variables
Auxiliary Variables
Ordered Set
Linearization Techniques
Model
Computational Experiments
Restriction

Cite this

@inproceedings{e1dded60e9614a849ae2ccfcb16fd42e,
title = "Obtaining the Maximum and Minimum and their Orders, Ordering and the Histogram of an Array of Real Numbers with a MILP Model",
abstract = "In a previous work we solved the same problem with real numbers with limited precision, but we did not consider the possibility of repetitions. In this paper we used a new, simpler and more efficient approach where the coherence between the original set and the ordered set is guaranteed by an auxiliary indexed binary variable and two sets of constraints that implement the restriction to a binary variable, a linearization technique developed in a previous work [1]. We also obtained the order in the original set of each element of the ordered set, the maximum(s) and minimum(s) and their orders with another auxiliary indexed binary variable and two sets of constraints and obtained the histogram of the original set of real numbers. Then we presented some examples of computational experiments that show that this new approach is more efficient in terms of runtime and memory usage. Finally we point as the improvement of the histogram calculation as the near future work.",
author = "Fonseca, {Jos{\'e} Barahona da}",
year = "2016",
language = "English",
booktitle = "Proceedings of APMOD 2016",

}

Obtaining the Maximum and Minimum and their Orders, Ordering and the Histogram of an Array of Real Numbers with a MILP Model. / Fonseca, José Barahona da.

Proceedings of APMOD 2016. 2016.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Obtaining the Maximum and Minimum and their Orders, Ordering and the Histogram of an Array of Real Numbers with a MILP Model

AU - Fonseca, José Barahona da

PY - 2016

Y1 - 2016

N2 - In a previous work we solved the same problem with real numbers with limited precision, but we did not consider the possibility of repetitions. In this paper we used a new, simpler and more efficient approach where the coherence between the original set and the ordered set is guaranteed by an auxiliary indexed binary variable and two sets of constraints that implement the restriction to a binary variable, a linearization technique developed in a previous work [1]. We also obtained the order in the original set of each element of the ordered set, the maximum(s) and minimum(s) and their orders with another auxiliary indexed binary variable and two sets of constraints and obtained the histogram of the original set of real numbers. Then we presented some examples of computational experiments that show that this new approach is more efficient in terms of runtime and memory usage. Finally we point as the improvement of the histogram calculation as the near future work.

AB - In a previous work we solved the same problem with real numbers with limited precision, but we did not consider the possibility of repetitions. In this paper we used a new, simpler and more efficient approach where the coherence between the original set and the ordered set is guaranteed by an auxiliary indexed binary variable and two sets of constraints that implement the restriction to a binary variable, a linearization technique developed in a previous work [1]. We also obtained the order in the original set of each element of the ordered set, the maximum(s) and minimum(s) and their orders with another auxiliary indexed binary variable and two sets of constraints and obtained the histogram of the original set of real numbers. Then we presented some examples of computational experiments that show that this new approach is more efficient in terms of runtime and memory usage. Finally we point as the improvement of the histogram calculation as the near future work.

M3 - Conference contribution

BT - Proceedings of APMOD 2016

ER -