More Web Proxy on the site http://driver.im/

research-article

Optimal constraints aggregation method for ILP

Author:

Pierre-Louis PoirionAuthors Info & Claims

Volume 262, Issue C

Pages 148 - 157

https://doi.org/10.1016/j.dam.2019.02.014

Published: 15 June 2019 Publication History

Abstract

In this paper we give a new aggregation method for Integer Linear Program (ILP), that allows to reduce the number of constraints of any ILP. In particular, we study the aggregation of non-negative systems of linear Diophantine equations. We prove that an aggregated system of minimum size can be constructed in polynomial time. We also study the minimum size of the coefficients of the aggregated problem.

References

[1]

Bach E., Shallit J.O., Algorithmic Number Theory: Efficient Algorithms, vol. 1, MIT press, Cambridge, US, 1996.

[2]

Benchimol P., Desaulniers G., Desrosiers J., Stabilized dynamic constraint aggregation for solving set partitioning problems, European J. Oper. Res. 223 (2) (2012) 360–371.

[3]

Borosh I., Flahive M., Treybig B., Small solutions of linear Diophantine equations, Discrete Math. 58 (3) (1986) 215–220.

[4]

Bradley G.H., Transformation of integer programs to knapsack problems, Discrete Math. 1 (1) (1971) 29–45.

[5]

Bradley G.H., Hammer P.L., Wolsey L., Coefficient reduction for inequalities in 0–1 variables, Math. Program. 7 (1) (1974) 263–282.

[6]

Chvátal V., Hammer P.L., Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1977) 145–162.

[7]

Elhallaoui I., Metrane A., Soumis F., Desaulniers G., Multi-phase dynamic constraint aggregation for set partitioning type problems, Math. Program. 123 (2) (2010) 345–370.

[8]

Glover F., Babayev D.A., New results for aggregating integer-valued equations, Ann. Oper. Res. 58 (3) (1995) 227–242.

[9]

Glover F., Woolsey R.E.D., Aggregating diophantine equations, Z. Oper. Res. 16 (1) (1972) 1–10.

[10]

Kannan R., Polynomial-time aggregation of integer programming problems, J. ACM 30 (1) (1983) 133–145.

[11]

Kendall K.E., Zionts S., Technical note–solving integer programming problems by aggregating constraints, Oper. Res. 25 (2) (1977) 346–351.

[12]

Ky V.K., Poirion P.L., Liberti L., Gaussian random projections for Euclidean membership problems, Discrete Appl. Math. 253 (2019) 93–102.

[13]

Onyekwelu D.C., Computational viability of a constraint aggregation scheme for integer linear programming problems, Oper. Res. 31 (4) (1983) 795–801.

[14]

Rosenberg I.G., Aggregation of equations in integer programming, Discrete Math. 10 (2) (1974) 325–341.

[15]

Schrijver A., Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1998.

Digital Library

[16]

Wilf H.S., Generatingfunctionology, Elsevier, 2013.

[17]

Wilson J.M., A method for reducing coefficients in integer linear inequalities, Naval Res. Logist. Q. 30 (1) (1983) 49–57.

Index Terms

Optimal constraints aggregation method for ILP
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming

Index terms have been assigned to the content through auto-classification.

Recommendations

Exact solution approach for a class of nonlinear bilevel knapsack problems

We study a class of nonlinear bilevel knapsack problems. The upper-level objective is a nonlinear integer function of both the leader's and the follower's decision variables. At the lower level the follower solves a linear binary knapsack problem, where ...
Fractional knapsack problems

The fractional knapsack problem to obtain an integer solution that maximizes a linear fractional objective function under the constraint of one linear inequality is considered. A modification of the Dinkelbach's algorithm [3] is proposed to exploit the ...
A surrogate relaxation based algorithm for a general quadratic multi-dimensional knapsack problem

In this paper, we develop a framework to solve a General Quadratic Multi-dimensional Knapsack Problem using surrogate relaxation. This paper exploits the fact that a continuous single constraint quadratic knapsack problem can be solved by inspection by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 262, Issue C

Jun 2019

203 pages

ISSN:0166-218X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 15 June 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents