On aggregating two linear diophantine equations
type: Item
instance of: scholarly article
title: On aggregating two linear diophantine equations
zbMATH Open document ID: 0897.11007
DOI: 10.1016/S0166-218X(97)00123-6
author: Nan Zhu
author: Kevin A. Broughan
published in: Discrete Applied Mathematics
publication date: 1998-05-24T00:00:00Z
full work available at URL: dam
review text: Given two diophantine equations \[ \sum_{j\in \mathbb{N}} a_{1j}x_j= b_1,\;\sum_{j\in \mathbb{N}}a_{2j}x_j= b_2, \quad x_j\geq 0\text{ for all }j\in \mathbb{N}= \{1,\dots, n\}, \tag{1} \] the problem is to find relatively prime integers \(t_1,t_2\), so that \[ \sum_{j\in \mathbb{N}} (t_1a_{1j}+ t_2a_{2j})x_j= t_1b_1+ t_2b_2 \tag{2} \] has the same solution set in nonnegative integers as (1). Using the notations \(w_j= c_1a_{2j} c_2a_{1j}\), \(j\in \mathbb{N}\), \(c_1,c_2\) integers not both equal, \(w_0= c_2b_1-c_1b_2\), \(x_0=1\), \(S(X)= S(X;c_1,c_2)= \sum_{j\in \mathbb{N}\cup \{0\}}w_jx_j\), \[ -\infty< L\leq\min_{X\in T}S(X), \qquad \max_{X\in T}S(X)\leq U<+\infty, \tag{3} \] \[ T= \{X: X=(x_1,\dots, x_n) \text{ satisfying }(2)\}, \] the main result is: the system (1) is equivalent to (2) if for arbitrary integers \(c_1,c_2\) not both equal the inequality \(t_1c_1+ t_2c_2> \max\{-L,U\}\) holds, where \(t_1,t_2\) are relatively prime integers and \(L,U\) any values satisfying (3). In general it is difficult to find \(\min S(X)\) and \(\max S(X)\), therefore in the following sections of the paper the main result is used to aggregate (1) under some additional conditions. In some cases the results are better than those given in the literature, i.e., the coefficients in (2) are smaller in the sense of absolute value.
Mathematics Subject Classification ID: 11D04
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 1139442
zbMATH Keywords: linear diophantine equations
zbMATH Keywords: aggregation
zbMATH Keywords: equivalence of systems
reviewed by: Joachim Piehler
MaRDI profile type: Publication
cites work: A note on equivalent systems of linear diophantine equations
cites work: Aggregation of nonnegative integer-valued equations
cites work: A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination
cites work: Sequential and simultaneous aggregation of diophantine equations
cites work: Transformation of integer programs to knapsack problems
cites work: On the reduction method for integer linear programs. II
cites work: Q3214706
cites work: New results on equivalent integer programming formulations
cites work: New results for aggregating integer-valued equations
cites work: Aggregating diophantine equations
cites work: On equivalent knapsack problems
cites work: A new reduction method in integer programming
cites work: Q5682153
cites work: Technical Note—Solving Integer Programming Problems by Aggregating Constraints
cites work: A note on aggregating constraints in integer programming
cites work: Technical Note—Computational Viability of a Constraint Aggregation Scheme for Integer Linear Programming Problems
cites work: Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach
cites work: Q5098083
OpenAlex ID: W2070981113
Recommended article: Sequential and simultaneous aggregation of diophantine equations
Recommended article: Q4133702
Recommended article: Aggregation of linear integer equations
Recommended article: On the number of solutions of certain linear Diophantine equations
Recommended article: On a linear diophantine equation
Recommended article: Q5780119
Recommended article: Q4461520
Recommended article: Q2987090
Recommended article: Q5155524
description: scientific article; zbMATH DE number 1139442