IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v16y2018i1d10.1007_s10288-017-0344-4.html
   My bibliography  Save this article

Block rearranging elements within matrix columns to minimize the variability of the row sums

Author

Listed:
  • Kris Boudt

    (Vrije Universiteit Brussel (VUB)
    Vrije Universiteit Amsterdam)

  • Edgars Jakobsons

    (ETH Zürich)

  • Steven Vanduffel

    (Vrije Universiteit Brussel (VUB))

Abstract

Several problems in operations research, such as the assembly line crew scheduling problem and the k-partitioning problem can be cast as the problem of finding the intra-column rearrangement (permutation) of a matrix such that the row sums show minimum variability. A necessary condition for optimality of the rearranged matrix is that for every block containing one or more columns it must hold that its row sums are oppositely ordered to the row sums of the remaining columns. We propose the block rearrangement algorithm with variance equalization (BRAVE) as a suitable method to achieve this situation. It uses a carefully motivated heuristic—based on an idea of variance equalization—to find optimal blocks of columns and rearranges them. When applied to the number partitioning problem, we show that BRAVE outperforms the well-known greedy algorithm and the Karmarkar–Karp differencing algorithm.

Suggested Citation

  • Kris Boudt & Edgars Jakobsons & Steven Vanduffel, 2018. "Block rearranging elements within matrix columns to minimize the variability of the row sums," 4OR, Springer, vol. 16(1), pages 31-50, March.
    • Handle: RePEc:spr:aqjoor:v:16:y:2018:i:1:d:10.1007_s10288-017-0344-4
    DOI: 10.1007/s10288-017-0344-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-017-0344-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-017-0344-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wang, Bin & Wang, Ruodu, 2011. "The complete mixability and convex minimization problems with monotone marginal densities," Journal of Multivariate Analysis, Elsevier, vol. 102(10), pages 1344-1360, November.
    2. Mokotoff, Ethel, 2004. "An exact algorithm for the identical parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 152(3), pages 758-769, February.
    3. Carole Bernard & Don McLeish, 2016. "Algorithms for Finding Copulas Minimizing Convex Functions of Sums," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-26, October.
    4. Mauro Dell'Amico & Manuel Iori & Silvano Martello & Michele Monaci, 2008. "Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 333-344, August.
    5. E. G. Coffman & M. Yannakakis, 1984. "Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum," Mathematics of Operations Research, INFORMS, vol. 9(3), pages 384-390, August.
    6. Boland, Philip J. & Proschan, Frank, 1988. "Multivariate arrangement increasing functions with applications in probability and statistics," Journal of Multivariate Analysis, Elsevier, vol. 25(2), pages 286-298, May.
    7. Mauro Dell’Amico & Silvano Martello, 1995. "Optimal Scheduling of Tasks on Identical Parallel Processors," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 191-200, May.
    8. Embrechts, Paul & Puccetti, Giovanni & Rüschendorf, Ludger, 2013. "Model uncertainty and VaR aggregation," Journal of Banking & Finance, Elsevier, vol. 37(8), pages 2750-2764.
    9. Dell'Amico, Mauro & Martello, Silvano, 2005. "A note on exact algorithms for the identical parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 160(2), pages 576-578, January.
    10. Wen-Lian Hsu, 1984. "Approximation Algorithms for the Assembly Line Crew Scheduling Problem," Mathematics of Operations Research, INFORMS, vol. 9(3), pages 376-383, August.
    11. Antonio Frangioni & Emiliano Necciari & Maria Grazia Scutellà, 2004. "A Multi-Exchange Neighborhood for Minimum Makespan Parallel Machine Scheduling Problems," Journal of Combinatorial Optimization, Springer, vol. 8(2), pages 195-220, June.
    12. Carole Bernard & Ludger Rüschendorf & Steven Vanduffel & Jing Yao, 2017. "How robust is the value-at-risk of credit risk portfolios?," The European Journal of Finance, Taylor & Francis Journals, vol. 23(6), pages 507-534, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Carole Bernard & Oleg Bondarenko & Steven Vanduffel, 2021. "A model-free approach to multivariate option pricing," Review of Derivatives Research, Springer, vol. 24(2), pages 135-155, July.
    2. Bernard, Carole & Kazzi, Rodrigue & Vanduffel, Steven, 2020. "Range Value-at-Risk bounds for unimodal distributions under partial information," Insurance: Mathematics and Economics, Elsevier, vol. 94(C), pages 9-24.
    3. Jose Blanchet & Henry Lam & Yang Liu & Ruodu Wang, 2020. "Convolution Bounds on Quantile Aggregation," Papers 2007.09320, arXiv.org, revised Sep 2024.
    4. Nabil Bouamara & Kris Boudt & S'ebastien Laurent & Christopher J. Neely, 2023. "Sluggish news reactions: A combinatorial approach for synchronizing stock jumps," Papers 2309.15705, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Carole Bernard & Oleg Bondarenko & Steven Vanduffel, 2018. "Rearrangement algorithm and maximum entropy," Annals of Operations Research, Springer, vol. 261(1), pages 107-134, February.
    2. Guopeng Song & Roel Leus, 2022. "Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3059-3079, November.
    3. Rico Walter & Alexander Lawrinenko, 2020. "A characterization of optimal multiprocessor schedules and new dominance rules," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 876-900, November.
    4. Absalom E Ezugwu & Olawale J Adeleke & Serestina Viriri, 2018. "Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times," PLOS ONE, Public Library of Science, vol. 13(7), pages 1-23, July.
    5. Bernard, Carole & Kazzi, Rodrigue & Vanduffel, Steven, 2020. "Range Value-at-Risk bounds for unimodal distributions under partial information," Insurance: Mathematics and Economics, Elsevier, vol. 94(C), pages 9-24.
    6. Jose Blanchet & Henry Lam & Yang Liu & Ruodu Wang, 2020. "Convolution Bounds on Quantile Aggregation," Papers 2007.09320, arXiv.org, revised Sep 2024.
    7. Takaaki Koike & Liyuan Lin & Ruodu Wang, 2022. "Joint mixability and notions of negative dependence," Papers 2204.11438, arXiv.org, revised Jan 2024.
    8. Carole Bernard & Don McLeish, 2016. "Algorithms for Finding Copulas Minimizing Convex Functions of Sums," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-26, October.
    9. Daniel Kowalczyk & Roel Leus, 2017. "An exact algorithm for parallel machine scheduling with conflicts," Journal of Scheduling, Springer, vol. 20(4), pages 355-372, August.
    10. Mauro Dell'Amico & Manuel Iori & Silvano Martello & Michele Monaci, 2008. "Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 333-344, August.
    11. Carole Bernard & Oleg Bondarenko & Steven Vanduffel, 2021. "A model-free approach to multivariate option pricing," Review of Derivatives Research, Springer, vol. 24(2), pages 135-155, July.
    12. Carole Bernard & Ludger Rüschendorf & Steven Vanduffel & Ruodu Wang, 2017. "Risk bounds for factor models," Finance and Stochastics, Springer, vol. 21(3), pages 631-659, July.
    13. Hofert Marius & Memartoluie Amir & Saunders David & Wirjanto Tony, 2017. "Improved algorithms for computing worst Value-at-Risk," Statistics & Risk Modeling, De Gruyter, vol. 34(1-2), pages 13-31, June.
    14. Giovanni Puccetti & Pietro Rigo & Bin Wang & Ruodu Wang, 2019. "Centers of probability measures without the mean," Journal of Theoretical Probability, Springer, vol. 32(3), pages 1482-1501, September.
    15. Tuitman, Jan & Vanduffel, Steven & Yao, Jing, 2020. "Correlation matrices with average constraints," Statistics & Probability Letters, Elsevier, vol. 165(C).
    16. Rico Walter & Martin Wirth & Alexander Lawrinenko, 2017. "Improved approaches to the exact solution of the machine covering problem," Journal of Scheduling, Springer, vol. 20(2), pages 147-164, April.
    17. Hofert, Marius & McNeil, Alexander J., 2015. "Subadditivity of Value-at-Risk for Bernoulli random variables," Statistics & Probability Letters, Elsevier, vol. 98(C), pages 79-88.
    18. Bassem Jarboui & Saber Ibrahim & Abdelwaheb Rebai, 2010. "A new destructive bounding scheme for the bin packing problem," Annals of Operations Research, Springer, vol. 179(1), pages 187-202, September.
    19. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    20. Roberto Fontana & Elisa Luciano & Patrizia Semeraro, 2021. "Model risk in credit risk," Mathematical Finance, Wiley Blackwell, vol. 31(1), pages 176-202, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:aqjoor:v:16:y:2018:i:1:d:10.1007_s10288-017-0344-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.