Small integer programming problem

Specific Domains Optimization (Mathematical)
21

Just some thoughts, both of this should hold

v-u > 0
n_1(v-u) - 1 \leq f(n_1) = n_1 v - \lceil n_1 u \rceil \leq n_1(v-u)

so that for all n_1 \geq \frac{1}{v-u} then f(n_1) \geq 0, so next_lowest shouldn’t be necessary to check from that point on. Same for n_2. Which means that n \leq \max{(\lceil\frac{1}{v-u}\rceil, \lceil\frac{1}{t-s}\rceil)}. What about starting from this value rather than n=1? Didn’t think deeply about this idea actually, so I’m probably wrong, but I think these results should lead to some improvements of the algorithm given by @barucden

22

Your upper bound is correct. However, we are looking for the smallest n, which can be much smaller than the upper bound you identified.

If we started from that upper bound n_\text{max} and then checked n_\text{max} - 1, n_\text{max} - 2, \ldots, we would eventually find some n for which the condition holds. But there could another n' < n for which the condition still holds and we wouldn’t know for sure until we checked all the remaining n-1, n-2, \ldots

Say that P(n) = 1 if \lceil nu \rceil \leq nv for given u<v and otherwise P(n)=0. P(n) is not monotonic. You can find n such that P(n)=1 but P(n-1) = P(n+2) = 0. So you cannot even use binary search or something like that.

1 Like
23

I was going to suggest that once an i,j pair was identified for n==i*a+j*b, you could increment by a or b to the next candidate n and only have to check for n == l*c+k*d. But after working out an example, there appears to be an unbounded memory usage and min check for backtracking from increments of the larger number when iterating candidate n:

a=4 < b=9
4i+9j, i, j
4,     1, 0
8,     2, 0
9,     0, 1 new increment path, checked min(4*3+9*0, 4*0+9*1)
12,    3, 0 backtrack to previous path, n+=3
13,    1, 1 n+=1 because 1 == 9-2*4
16,    4, 0 backtrack, n+=3
17,    2, 1
18,    0, 2 new increment path, checked min(4*5+9*0, 4*3+9*1, 4*0+9*2)
20,    5, 0 backtrack, n+=2
21,    3, 1
22,    1, 2

which as far as I know is only avoidable when either a or b is a multiple of the other, making the diverging increment paths redundant because the sums are equal. When not backtracking, the increments of n are 1 == 9-2*4 when there are 4s to spare, and backtracking becomes less frequent and decreases the increments with more paths, so it’s not saving increments in the long run, either. I imagine other coprimes pairs would have a much larger set of increments, so I can’t simplify this.

2 Likes
24 
a, b = 9, 35
c, d = 6, 25

gg = gcd(b,d)

k = b ÷ gg
h = d ÷ gg

h*b + 0*a
k*d + 0*c

[[[h1,j]'*[b,a] for h1 in h-j:-1:0] for j in 0:h]
[[[k1,j]'*[d,c] for k1 in k-j:-1:0] for j in 0:k]



g = gcd(a,c)

k = a ÷ g
h = c ÷ g

h*a + 0*b
k*c + 0*d

[[[h1,j]'*[a,b] for h1 in h-j:-1:0] for j in 0:h]
[[[k1,j]'*[c,d] for k1 in k-j:-1:0] for j in 0:k]

I propose this example to illustrate the idea.
We start from an upper limit given by
n0 = ha+0b = kc+0d

the other potentially valid values ​​are to be chosen within the vectors provided by the following formulas

[[[h1,j]'*[b,a] for h1 in h-j:-1:0] for j in 0:h]

[[[k1,j]'*[d,c] for k1 in k-j:-1:0] for j in 0:k]

So it would be a matter of comparing, at worst, two ordered vectors of (h+2)(h+1)/2 and (k+2)(k+1)/2 elements

25

Not sure if relevant or a fruitful direction, but just figured I’d note that a relaxed version of the problem, with coefficients i, j, k, l in \mathbb{Z} (instead of \mathbb{Z}_{\geq0}) is solvable by linear algebra, using the Smith normal form.

In particular, the original problem can also be phrased as:

\mathbf{A}\mathbf{v} = \begin{bmatrix} a & b & 0 & 0 \\ 0 & 0 & c & d\end{bmatrix}\begin{bmatrix} i \\ j \\ k \\ l \end{bmatrix} = n\begin{bmatrix} 1 \\ 1 \end{bmatrix}

The integer solutions to this equation, if they exist, can be expressed using the generalized inverse \mathbf{A}^g = \mathbf{T}^{-1}\boldsymbol{\Lambda}^g\mathbf{S}^{-1} constructed from the Smith normal form \mathbf{S}\mathbf{\Lambda}\mathbf{T} = \mathbf{A} with unimodular matrices \mathbf{S} and \mathbf{T} and a diagonal matrix of invariant factors \mathbf{\Lambda}. In particular, the solutions are:

\mathbf{v} = \begin{bmatrix} i \\ j \\ k \\ l \end{bmatrix} = n \mathbf{A}^g \begin{bmatrix} 1 \\ 1\end{bmatrix} + (\mathbf{1} - \mathbf{A}^g\mathbf{A}) \mathbf{t},

with \mathbf{t}\in \mathbb{Z}^4.
One maybe useful thing in the original context, is that integer solutions exist if and only if n \mathbf{A}^g \begin{bmatrix} 1 \\ 1\end{bmatrix} is integral.

For one of the variants noted above, a = 9, b = 35, c = 6, d = 25, this procedure then gives the full set of solutions for i, j, k, l \in \mathbb{Z}:

\begin{bmatrix} i \\ j \\ k \\ l \end{bmatrix} = \begin{bmatrix} 4 \\ -1 \\ -4 \\ 1 \end{bmatrix} n + \begin{bmatrix} -35t_1 - 140t_2 \\ 9t_1 + 36t_2 \\ 25t_3 + 100t_4 \\ -6t_3 - 24t_4 \end{bmatrix}.

From the perspective of this relaxed version of the problem, the original problem then comes down to finding t_i\in \mathbb{Z} such that the above is nonnegative.
(Here, the minimal-n solution seems to be n=18 with t_1, t_2, t_3, t_4 = -6, 2, -5, 2 and i, j, k, l = 2, 0, 3, 0).
This is the intersection of a cone-constraint and a lattice, i.e., a monoid - and a basis for the solutions should then be in principle obtainable from an associated Hilbert basis.

(But, not very clear to me that this is practically very useful for the original un-relaxed problem; computing the Smith normal form is a bit much, unless the gcd relations can somehow help getting it analytically, and computing the Hilbert basis is even worse. Still, sort of fun to see that part of what makes the original problem interesting is the non-negative constraint)

4 Likes
26

That’s my first thought as well. The package Nemo.jl has the LLL algorithm, so it should be possible to solve the shortest vector problem, and other related lattice problems there.

27

I worked out the Smith normal form for A = [a b -c -d] and it turned out, not all that surprisingly, to basically coincide with Bézout’s identity. I’m fairly certain that’s the case here as well. (As noted in other posts, Julia’s gcdx gives you what’s needed to solve for integer solutions for a fixed n.)

2 Likes
28

Following on this thread a bit, I thought it might be fun to compute this Hilbert basis for the specific problem of a, b, c, d = 9, 35, 6, 25. From this, we can get all possible non-negative solutions - not just the minimum one (but also the minimum one).

We can compute the Hilbert basis using Normaliz, accessed via PyCall and PyNormaliz (the Normaliz.jl package isn’t working afaik):

using PyCall
const PyNormaliz = pyimport("PyNormaliz")

# set up problem from where it was left by generalized inverse approach
v = [4, -1, -4, 1]
Q = [-35 -140 0 0; 9 36 0 0; 0 0 25 100; 0 0 -6 -24]
S = hcat(v, Q) # solution space in ijkl is spanned by S*[n, t1, t2, t3, t4]

# compute Hilbert basis for monoid S*[n, t1, t2, t3, t4] >= 0
C = PyNormaliz.Cone(inequalities = S)
C.Compute("HilbertBasis", "DualMode")
nts  = transpose(C.HilbertBasis())
ijkls  = collect(eachcol(S*nts))
ns = nts[1,:]

The possible solutions in n and i,j,k,l are then given by ns and ijkls:

julia> println.(Ref("n = "), ns, Ref(": ijkl = "), ijkls)
n =  18: ijkl = [2, 0, 3, 0]
n =  62: ijkl = [3, 1, 2, 2]
n =  79: ijkl = [1, 2, 9, 1]
n =  81: ijkl = [9, 0, 1, 3]
n = 105: ijkl = [0, 3, 5, 3]
n = 106: ijkl = [4, 2, 1, 4]
n = 114: ijkl = [1, 3, 19, 0]
n = 125: ijkl = [10, 1, 0, 5]
n = 140: ijkl = [0, 4, 15, 2]
n = 149: ijkl = [1, 4, 4, 5]
n = 150: ijkl = [5, 3, 0, 6]
n = 175: ijkl = [0, 5, 0, 7]
n = 175: ijkl = [0, 5, 25, 1]
n = 210: ijkl = [0, 6, 35, 0]
n = 225: ijkl = [25, 0, 0, 9]

Any solution to ai + bj = ck + dl = n (here for a, b, c, d = 9, 35, 6, 25) can now be obtained from the non-negative integer span of the above ijkls.

1 Like