A mixed integer linear programming formulation for low discrepancy consecutive k-sums permutation problem

Authors

  • Milena Bogdanović Pedagogical Faculty, Vranje
  • Zoran Maksimović Military Academy, Belgrade
  • Ana Simić Faculty of Mathematics, Belgrade
  • Jelisavka Milošević FASPER, Belgrade

DOI:

https://doi.org/10.2298/YJOR160104005B

Keywords:

Mixed integer linear programming, Permutations with low discrepancy consecutive k-sums

Abstract

In this paper, low discrepancy consecutive k-sums permutation problem is considered. A mixed integer linear programing (MILP) formulation with a moderate number of variables and constraints is proposed. The correctness proof shows that the proposed formulation is equivalent to the basic definition of low discrepancy consecutive k-sums permutation problem. Computational results, obtained on standard CPLEX solver, give 88 new exact values, which clearly show the usefulness of the proposed MILP formulation.

References

Anstee, R., Ferguson, R., and Griggs J.R., “Permutations with low discrepancy consecutive k sums”, Journal of Combinatorial Theory- Series A, 100 (2002) 302-321.

Stefanović, M., “Permutations with small variations of subsequent k-sums”, Faculty of Mathematics, University of Belgrade, Master thesis, (2010) (in Serbian).

Stefanović, M., and Živković, M., “Permutations with constrained consecutive k-sums- Some special cases”, The IPSI BgD Transactions on Internet Research, 11(1) (2015) 19-22.

Downloads

Published

2017-02-01

Issue

Vol. 27 No. 1 (2017)

Section

Research Articles

License

Copyright (c) 2017 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.