A numerical method for solving quadratic integer programming problem

Бесплатный доступ

We propose a new numerical method for solving quadratic integer programming problem. The algorithm is based on a special representation of a minimizer of the corresponding objective functional. The problem can be reduced to a special box-constrained integer least squares problem. The advantage of the proposed algorithm is a good computational performance (approximately O(nln(n))operations) shown in numerical experiments, where the number of unknowns can be up to 108. The computational complexity of the algorithm is confirmed experimentally by a large number of numerical experiments. The algorithm consists of 3 steps. At the average, a solution is found at the second step in 83,6% cases, while the third step gives solution in the remaining cases. The algorithm is realized with the use of the Python programming language. The results of numerical experiments can be found at the service GitHubGist. The elaborated software system was used to solve the problem on formation of the optimal order for education institutions in regions of the Russian Federation.

Еще

Nonlinear programming, integer programming, numerical method, optimization

Короткий адрес: https://sciup.org/147232952

IDR: 147232952   |   DOI: 10.14529/mmp190311

Текст научной статьи A numerical method for solving quadratic integer programming problem

Recently, nonlinear integer optimization is of particular interest due to its practical importance. Consider the model problem in the following form:

n2

E (PZX i) -^ min

52 X i min (S,A), i=1

where all parameters are integers. Problem (1) arises in the problem on formation of the optimal order for education institutions in a region (see [1]), which can be reduced to the simpler problem of the form n /   \ 2

i= (Z i) —^ min n

I EA i = E,

X i=1

n where E = 52 Pi — min(S, A) and Zi > 1 are nonnegative integers, Ai, 0 < Ai < E(i = i=1

  • 1,    2, ...,n) , are unknown nonnegative integers.

n - 1

The change of variables A n = 52 A i reduces the problem to a very special case of the i=1

box-constrained integer least squares problem (see [2–4] and the problem on the closest point search in lattices (see the survey [5, 6]), as well as the closest vector problem). General problems of this type are NP-hard (see [7, 8]). However, at present, there exist rather effective methods for solving these problems (see [3, Ch. 8; 6, 9–11] and the bibliography therein). The method proposed below is very simple and actually exact, and allows to involve a large number of the variables. Numerical experiments show an almost linear dependence of the computation time on the number of variables, from O(n) to O(n • ln(n)).

1. Main Results

First of all, we give some theoretical justification of the algorithm. Consider the

minimizer of problem (2) in the form λ i

where the number Z n+1 E (0, to ) is to be determined.

= [в 0, 5 + 0, 5] , e i = (zZ +1) 2 (i = 1, 2,

,,n) ,

Lemma 1. If there exists Z n +1 E (0, to ) such that

n

E = Е в 0, 5 + 0, 5], e i = i=1

к Z n+1) '

then the numbers

A * = [e i 0, 5 + 0, 5], e i =

( _Z_ у

V Z n+J

(i = 1, 2,..., n)

give the minimum of functional (2).

Proof. Represent λ i in the form

A * = e i 0, 5 + 0, 5 - X i , e i =

Z i

Z n+1

(i = 1,2,...,n),

where x i E [0; 1) . Show that

+»I =+A

n for all integers Mi such that ^2 Mi = 0.

i=1

Taking into account (3), present expression (4) as

E 2 A i * M i + /' 2 0

Z2      " ’ i=1           i n E i=1 n

e i M i + M i    2 x i M i + M i

^^ M i i=1

Z i 2

- 2 x i M i + M i 2

> 0,

n

E M i

Z i 2

-

2 X i M i + M i 2

n

+ E yMi- 0, i=1 Z n+1

> 0.

i=1            Z i 2

Since м 2 M i for all integers M i , inequality (5) is valid for all x i E [0; 1) . Therefore,

expression (4) is also valid. This completes the proof.

Consider the function

F (Z n+i ) =

0,5 + 0,5I

which does not increase in the variable Z n+1 and takes nonnegative integer values. Obviously, if Z i = Z , (i,j = 1...n) , then the function F (Z n+1 ) has the jump equal to n at the discontinuity point. Therefore, the function F(Z n +1 ) does not take all integer values. Consequently, depending on the variable Z i , the range of the function F(Z n +1 ) cannot coincide with the set of natural numbers. At the discontinuity point, we have

F(Z n+i ± 0) = c т d, where c, d are nonnegative integers and d >  1 . Since the functions

(• 0,5 + 0,5, i = 1,2,...,n

\ Zn + 1 / are continuous, then the function

0, 5 + 0, 5

is a nonincreasing piecewise constant function taking all natural values when the independent variable run over the nonnegative semi-axis. The sum of these functions is also a nonincreasing piecewise constant function, and takes all nonnegative integers whenever all discontinuity points of these functions are different. Otherwise, this statement is not true. If two discontinuity points coincide, then the module of the jump is not less than 2 at each of these discontinuity points. Let us consider quantity (7) to be equal to a nonnegative integer k . We find that the discontinuity points of functions (8) have the form

Z n+1 = Z i /(2k - 1) 1/2 , (k = 1, 2,..., X .

Two discontinuity points coincide whenever there exist nonnegative integers k and m (for i = j ) that not exceed n and

Z i /(2k 1) 1/2 = Z , /(2m 1) 1/2 , (k = 1,2,..., x, m = 1, 2,..., x ) . (9)

These equalities hold for different pairs of numbers Z i and Z j . Consider the segment [a, b] such that F (a) >  E and F (b) <  E . Function (6) is piecewise constant, and the segment [a, b] has q discontinuity points. Denote these discontinuity points by Z l n +1 , l = 1, 2, ..., q , and enumerate in increasing order with respect to the number l . Consider the following two possible cases.

1. There exists the number l such that F (Z n+1 ) = E for all Z n + l in (Z nl + 1 1 ,Z n +1 ) . By

Lemma 1, the numbers λ i for these numbers Z n +1 .

0, 5 + 0, б] give a solution to problem (2)

nn

In this case, E + a = ^A i and E b = J2 A2, where a and b are nonnegative i=1                       i=1

integers. Note that for m = a + b there exists the jump of the function F at Z^n+1(m = F(Zln+1 — 0) — F(Zln+1 + 0)), and, hence, a, b < m. Consider the problem n2

E (V)   ■ min, i=1 x      7

n a = Ey, i=1

where the numbers y i are nonnegative integers. Consider numbers (10) such that the corresponding functions A 1 (Z n +1 ) has the discontinuity point at Z l n +1 . Assume that these numbers are A 1 , A 2 , ..., A m , else renumber these numbers. The remaining functions A 1 (Z n+1 ) are continuous at this point for t m + 1 .

Lemma 2. In Case 2, the solution to problem (2) can be represented as Ai = Ai — yi, if m yi = 0 for i = m + 1,..., n and yi E {0,1} for i = 1,..., m, a = 22 yi.

i=1

Therefore, problem (2) is reduced to the following problem having the less dimension:

{ m / a 1 - \ 2

E (' min, i=1        7

m a =    yi , i=1

where the minimum is taken over the numbers y i E { 0,1 } .

Proof. Let us show that there exist numbers yi E {0,1} (j = 1, 2, ...,m) such that n /.1x2 m / \ 1 x 2 n /-.1, x 2

.E .® ■ E        -E( ')

n for all integers ci, if —a = ^2 ci. Transform (12) as follows:

i=1

n / \ 1 \ 2 m / \ 1 \ 2 m E ^ + E Zj + E t=m+1 ' t2 j=1 j/ j=1

y) 2

(Z j ) 2

-

2y j^l R 2 + E (Z j ) 2 1=1 VzJ ^=1

(C i ) 2

(Z i ) 2

, 2c i A| + (Z i ) 2 .

By construction,

2A j = Z,ljU ) 2 + 1, j = 1, 2,...,m,

2A i = (ZZZ J-1) +1 2a., i = 1, 2,...,n,

where a i is the fractional part of the quantity 2 rewrite (13) in the form

2 ц ZA +1) y\ Zn +i/      у

. Taking into account (14),

(       y j (f zZ j- ) 2 + 1)      n / A 2 Ci (f Ze- ) 2 + 1 2aJ

(y j )2 _       Z n +^       < e (C i ) 2      yv Z n +1/ ___________ У

(Z j ) 2            (Z j ) 2         1=^ (Z i ) 2 +            (Z i ) 2

i = 1, 2, ..., n, i = 1, 2, ..., n.

which can be transformed as follows:

m

Е j=1

( У з ) 2 - У з

(Z j ) 2

-

m yj j=1

(z n+1 ) 2

(c i ) 2 + c i (1 - 2a . )     £ c i

(Z i ) 2         + (z n+1 ) 2

m

Substitute    yj j=1

= a and ^2 c i = a in (32):

m

Е j=1

(y j ) 2 y j

(z j ) 2

n

5 Е

(c i ) 2 + c i (1 2a i ) ( Zip

The function £ (y j Z y j j=i    j

has a zero global minimum, which is achieved for y j E { 0,1 }

m such that a = ^ Уз■ These numbers yj exist, since a < m. Therefore, the left-hand j=1

side of (15) is removed, while the right-hand side is always nonnegative for all admissible numbers c i .

Lemma 3. The minimum of functional (11) is equal to m /\1\2 stУ

-

a

,

m and is achieved for every set of the numbers yi E {0,1} such that a = ^yi.

i =1

Proof. For example, consider the following set of numbers: y j = 1 for j = 1, 2,..., a and y j = 0 for j = a + 1, ...,m . Consider the objective functional (see (11))

j

2 + s (M-t=j+1 v 7

Transform the expression ab ove and arrive at the quantity

Е ( 2 ( ^ b ) + ( z )j + s ( b-

Substitute (10) in (16) and obtain

α

E 2

2 0,5 + 0,5) y,^

j =1

\

\

Z j 2

/

+(S)

/

m /\1\2 ' Е Z .

i =1

.

Transform (17) and obtain the expression m 1 2 Е ft)

Obviously, this expression is independent minimum of functional (11).

a

^Zn+if- of the numbers

y j , and, therefore, is the

The main result is as follows.

Theorem 1. There exists the number l such that either F (z n +1 ) = E for all z n +1 in (Z n-X , z n +1 ), or F(Zl n +1 - 0) > E and F(Zl n +1 + 0) = F (z n+1 0)

Г/ \ 2

the numbers A i 1 = (zZ ii) ' 0, 5 + 0, 5 give a solution to problem (2) for the numbers

Z n +1 in (z ^+i ,Z n +1) . In the second case, suppose that m is the jump of F at Z l n +1 and A 1 , i = 1, 2, ...,m, are the functions having a discontinuity point at Z l n +1 (otherwise, we

n can renumber). Let a = ^2 A1 — E. Then the minimum of functional (2) is achieved at i-1

the numbers Ai = Ai1 — yi, if yi = 0 for i = m + 1, ...,n, yi E {0,1} for i = 1, ...,m, and m a =    yi .

i-1

  • 2.    Description of Algorithm

First of all, we find the segment containing the necessary discontinuity point z l n +1 .

Lemma 4. Suppose that F(zln+1 — 0) > E and F(zln+1 + 0) < E, then below zn+1 =

n

E zi

\ i -1

\ 2E +

l          above n < zn+1 < zn+1 =

n

E zi

\ J-! \ 2E

.

- n

Proof. F(z l n +1 e ) E for every e >  0 . We have that

n

n

E = 5^ 0, 5 + 0, 5] ^(в 0, 5 + 0

i -1

Hence, we obtain that

i -1

, 5) в = (

Z i l z n +1

-

ε.

l zn+1

-

above

E z n+1

n

E zi

= \ — \ 2E

.

- n

On the other hand,

n

E = ^ [e i 0, 5 + 0, 5] i -1

and, therefore,

n

> V ■ • 0, 5 + 0, 5,ei = ( i-1

Zi zn+1+E

,

below zn+1

n

E zi

= \ i -1

\ 2E +

— < z n+1 + e- n     n +

The number e >  0 is arbitrary. This completes the proof.

Describe main steps of the algorithm.

1. Determine the quantities

a

n

E zi

= \ J-1 \ 2E

-

n

E zi

i -1

— , b = A —----• n      2E + n

If F (a) = E or F (b) = E , then, for the known (by Lemma 1) solution, we have that

A * =

( Za i ) 2 0, 5 + 0, 5 or A * = ( Zb i ) 2 0, 5 + 0, 5 . Otherwise, go to Step 2.

  • 2.    Use the algorithm of the dichotomy method [12]. There are two possible situations.

First, we find Z n+1 such that F (Z n+1 ) = E . Then A * =

Z i

\ Zn +1 /

0, 5 + 0, 5 is a solution

to problem (2). Second, we find an interval (a, b) containing only such discontinuity points of F that F (a + 0) = E + a or F (b 0) = E в , where а, в >  0 are integers. Then go to Step 3.

  • 3.    Find the discontinuity point Z^n +1 of function (6) on the new interval (a, b) . We 2

have that F(Zl n +1 ) >  E . Calculate A i 1 = ZZZr^j 0, 5 + 0, 5 and look for a solution to

problem (2) in the form A * = [A 1 1,..., A a 1, A a +1 ,..., A m ,

..

A } (Z n+i ) , j = 1,

.,А П ] , where the functions

..

.,m have a discontinuity point at Z nn +1 , while the remaining functions

A 1 (Z l n +1 ) , t m + 1 , are continuous at this point.

  • 3.    Realization of Algorithm

In order to realize the proposed algorithm, we use the language “Python” and the service GitHubGist. The service is an open remote control system to verify software and numerical experiments. The algorithm was applied to different sets of data (see Table 1).

Table 1

Numerical experiment scenarios

Number of variables, n

Number of experiments

1

10

500

2

100

500

3

1000

500

4

10000

500

5

100000

500

6

1000000

500

7

10000000

500

8

100000000

500

Analyzing the algorithm, we can note that a solution can be found at every step of the algorithm. Hence, we pay attention to the following two problems.

First, obtain the dependence of the computation time on the number of variables (see Figure). Second, obtain the probability to find a solution at every step of the algorithm (see Table 2).

The results of the numerical experiments and their realizations can be found at

Conclusion

According to Figure, the dependence of the computation time on the number of variables is almost linear and is at most O(n7n(n)) . Also, note that a solution is determined at Step 2 in 83 % cases, while Step 3 gives a solution in the remaining 17 % cases.

10 10л2 1ОлЗ 10л4 10л5 10л6 10л7 Number of unknowns 10л8

0     20000000 40000000 60000000 80000000 100000000

Number of unknowns

Computational complexity of the algorithm

Table 2

Probability to find a solution at every step of the algorithm

Number        of

Number of solutions

Number of solutions

unknowns

determined at Step 2

determined at Step 3

10 1

3288

712

10 2

2861

639

10 3

2479

521

10 4

2076

424

10 5

1670

330

10 6

1247

253

10 7

846

154

10 8

440

60

Average probability

0,836

0,164

Список литературы A numerical method for solving quadratic integer programming problem

  • Татьянкин, В.М. Методы и алгоритмы для управления процессами кадрового обеспечения региона: дис.. канд. техн. наук / В.М. Татьянкин. - Новосибирск, 2017.
  • Buchheim, C. An Exact Algorithm for Nonconvex Quadratic Integer Minimization Using Ellipsoidal Relaxations / C. Buchheim, M. De Santis, L. Palagi, M. Piacentini // SIAM Journal on Optimization. - 2013. - V. 23, № 3. - P. 1867-1889.
  • Buchheim, C. An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming / C. Buchheim, A. Caprara, A. Lodi // Mathematical Programming. - 2012. - V. 135, № 1-2. - P. 369-395.
  • Xiao Wen Chang. Solving Box-Constrained Integer Least Squares Problems / Xiao Wen Chang, Qing Han // IEEE Transactions on Wireless Communications. - 2008. - V. 7, № 1. - P. 277-287.
  • Agrell, E. Closest Point Search in Lattices / E. Agrell, T. Eriksson, A. Vardy, K. Zeger // IEEE Transactions on Information Theory. - 2002. - V. 48, № 8. - P. 2201-2214.
  • Duan Li. Nonlinear Integer Programming / Duan Li, Xiaoling Sun. - New York: Springer Science and Business Media, 2006.
  • Van Emde Boas, P. Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice / P. van Emde Boas. - Amsterdam: University of Amsterdam. - 1981.
  • Axehill, D. Integer Quadratic Programming for Control and Communication. PhD Thesis / D. Axehill. - Linköping: Institutionen för systemteknik, 2008.
  • Lee, J. Mixed Integer Nonlinear Programming / J. Lee, S. Leyffer. - New York; Dordrecht; Heidelberg; London: Springer Science and Business Media, 2012.
  • Hemmecke, R. Nonlinear Integer Programming. Optimization and Control / R. Hemmecke, M. Köppe, J. Lee, R. Weismantel // 50 Years of Integer Programming 1958-2008. - Berlin; Heidelberg: Springer, 2010. - P. 561-618.
  • Borno, M.A. Reduction in Solving Some Integer Least Squares Problems / M.A. Borno. - Montreal: McGill University. - 2011.
  • Мудров, А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль / А.Е. Мудров. - Томск: Раско, 1991.
Еще
Статья научная