# An Auxiliary Function Method for Global Minimization in Integer Programming

Authors: Hongwei Lin; Yuping Wang; Xiaoli Wang
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

An auxiliary function method is proposed for finding the global minimizer of integer programming problem. Firstly, we propose a method to transform the original problem into an integer programming with box constraint, which does not change the properties of the original problem. For the transformed problem, we propose an auxiliary function to escape from the current local minimizer and to get a better one. Then, based on the proposed auxiliary function, a new algorithm to find the global minimizer of integer programming is proposed. At last, numerical results are given to demonstrate the effectiveness and efficiency of the proposed method.


---

## Body

## 1. Introduction

Consider the following integer programming problem:(P)min⁡f(x),s.t.gi(x)⩽0,i=1,2,…,l,hi(x)=0,i=l+1,l+2,…,m,x∈Zn,
where Zn is the n-dimensional integer set, and the set S={x∈Zn∣gi(x)⩽0,i=1,2,…,l,hi(x)=0,i=l+1,l+2,…,m} is bounded.Many real-life applications can be modeled as problem (P), such as production planning, scheduling, and operations research problem. The objective functions of most of the problems are nonlinear and have more than one local optimal solutions over feasible region S. This requires the global optimization techniques to find the best solution amongst multiple local optima.Since integer programming problems are generally NP-hard, there are no efficient algorithms with polynomial-time complexity for solving them. Thus, many approximate algorithms have been rapidly developed in recent years, such as greedy search (see [1–4]), simulated annealing (see [5, 6]), genetic algorithm (see [7–9]), tabu search (see [10, 11]), and discrete filled function techniques (see [12–17]). The discrete filled function method is one of the more recently developed global optimization methods to solve integer programming problems. Once a local minimizer has been found by a local search method, the discrete filled function method introduces an auxiliary function to escape from the current local minimizer and to get a better one.At present, the discrete filled function methods mainly focus on the unconstrained integer programming problems, and most of the existing filled functions contain parameters which are needed to adjust. Thus, solving general integer programming problems is difficult, and solving the unconstrained integer programming problems needs much computation. In this paper, we propose an auxiliary function method to solve problem (P). The proposed auxiliary function has no parameters, and the computation of the proposed method is relatively small.The remainder of this paper is organized as follows: Section2 gives some useful notations and definitions. In Section 3, we propose a method to transform the original problem into an integer programming with box constraint. Based on the transformed problem, an auxiliary function is proposed in Section 4, and its properties are also analyzed. An algorithm for solving problem (P) is proposed in Section 5 with several numerical experiments. Some concluding remarks are given in Section 6.


## 2. Preliminaries

In this section, some useful notations and definitions are listed firstly. By estimating the bound ofS, we can find a box region Ω=∏i=1n[Li,Ui] with S⊂Ω. In most practical problems, Ω can be easily estimated or is usually given.LetM be a constant which satisfies
(2.1)M⩾max⁡z∈Sf(z)+1,
and let
(2.2)D={±ei,i=1,2,…,n}
be a direction set, where ei is an n-dimensional unit vector in which the ith component is 1, and the others are 0.Definition 2.1.
x is said to be a vertex of Zn⋂Ω,if and only if, for all d∈D,x+d∈Zn⋂Ω and x-d∉Zn⋂Ω,or x+d∉Zn⋂Ω and x-d∈Zn⋂Ω hold.
The set of vertices ofΩ⋂Zn is denoted as V.Definition 2.2 (see [18]).
For allx∈Z^n⋂Ω,the neighborhood of x is denoted as N(x)={x}⋃{w∈Zn⋂Ω∣w=x+d,d∈D}.Definition 2.3 (see [18]).
A pointx∈Zn⋂Ω is called a local minimizer (maximizer) of f(x) over Zn⋂Ω if for all y∈N(x),f(y)⩾f(x)(f(y)⩽f(x)) holds; a point x∈Zn⋂Ω is called a global minimizer (maximizer) of f(x) over Zn⋂Ω if for all y∈Zn⋂Ω,f(y)⩾f(x)(f(y)⩽f(x)) holds. In addition, if equality does not hold, x is called a strictly local (global) minimizer (maximizer) of f(x).For finding a local minimizer of integer programming, the following local search algorithm is taken in most cases.Local Search Algorithm (see [12])
Step 1.
Choose an initial pointx∈Zn⋂Ω.Step 2.
Ifx is a local minimizer of f(x), then stop; otherwise, find another point y∈N(x) which minimizes f(x) over N(x).Step 3.
Setx:=y, and go to Step 2.


## 3. Transformation of the Original Problem

The local search algorithm usually requires that the search region should be a connected one. However, the feasible region of the original problem may not be connected, so we need to transform the original problem into a simple problem with a connected search region. In order to transform the original problem, we need to define three unary functions firstly:(3.1)g(t)={0,t>0,1,t⩽0,h(t)={1,t=0,0,t≠0,s(t)={0,t=m,1,t<m,
where m is the number of constraints.Consider the following function:(3.2)F(x)=f(x)+(M-f(x))×s(∑i=1lg(gi(x))+∑i=l+1mh(hi(x)))
and the problem
(TP)min⁡F(x),s.t.x∈Ω⋂Zn,
where M is taken to satisfy (2.1). The following theorem will show that problem (TP) does not change the local minimizers of problem (P).Theorem 3.1.
Ifx is a local minimizer of problem (P),  then x is a local minimizer of problem (TP);  in turn, if x is a local minimizer of the problem (TP),  then x is a local minimizer of the problem (P), or F(x)=M.Proof.
Ifx is a local minimizer of the problem (P), then for all y∈N(x)⋂S, one has F(y)=f(y)⩾f(x)=F(x); for y=N(x)∖S and by the definition of M, one has F(y)=M>maxz∈Sf(z)⩾f(x). So F(y)⩾F(x) for all y∈N(x), namely, x is a local minimizer of the problem (TP).
Ifx is a local minimizer of the problem (TP), then for all y∈N(x), one has F(y)>F(x). If F(x)<M, namely, x∈S, then one has f(y)=F(y)>F(x)=f(x) for all y∈N(x)⋂S. So x is a local minimizer of the problem (P).Theorem3.1 shows that problem (P) and problem (TP) have the same minimizers except the infeasible points. If we can find a global minimizer of problem (TP), then problem (P) is solved.In most cases, using the local search algorithm to solve problem (TP) will trap in a local minimizer of problem (TP). We hope to find a method to escape from a local minimizer and to get a better one. Section 4 will give an auxiliary function for solving this problem.


## 4. Auxiliary Function and Its Properties Proof

Letx1* be the current best local minimizer of problem (TP), and define the following two integer sets:(4.1)S1={x∈Ω⋂Zn∣F(x)⩾F(x1*)},S2={x∈Ω⋂Zn∣F(x)<F(x1*)}.To begin with, a unary function is given as follows:(4.2)w(t)={1,t⩾0,t,t<0.Consider the following auxiliary function:(4.3)AF(x,x1*)=11+∥x-x1*∥×w((F(x)-F(x1*))(1+∥x-x1*∥)),
and its properties are analyzed as follows.Theorem 4.1.
AF(x,x1*) has no local minimizer in set S1∖V.By definition ofS1, for all x∈S1∖V, one has F(x)⩾F(x1*), then
(4.4)AF(x,x1*)=11+∥x-x1*∥>0.In order to prove thatx is not a local minimizer of AF(x,x1*), we only need to find a point y0 in N(x) such that AF(y0,x1*)<AF(x,x1*).If there existsy0∈N(x) satisfies F(y0)<F(x1*), then
(4.5)AF(y0,x1*)=F(y0)-F(x1*)<0<AF(x,x1*).
For all y∈N(x) with F(y)⩾F(x1*), since x∉V, there exists y0∈N(x) such that ∥y0-x1*∥>∥x-x1*∥, then
(4.6)AF(y0,x1*)=11+∥y0-x1*∥<11+∥x-x1*∥=AF(x,x1*).Therefore, AF(x,x1*) has no minimizer in the set S1∖V.Theorem 4.2.
If there exists another local minimizerx2* of F(x) such that F(x2*)<F(x1*),  then x2* is also a local minimizer of AF(x,x1*).Proof.
ByF(x2*)<F(x1*), one has
(4.7)AF(x2*,x1*)=F(x2*)-F(x1*)<0.Sincex2* is a local minimizer of F(x), one has F(y)⩾F(x2*) for all y∈N(x2*).WhenF(y)⩾F(x1*), and by (4.3), one has
(4.8)AF(y,x1*)=11+∥x-x1*∥>0>AF(x2*,x1*).WhenF(y)<F(x1*), and by (4.3), one has
(4.9)AF(y,x1*)=F(y)-F(x1*)⩾F(x2*)-F(x1*)=AF(x2*,x1*).Namely,AF(y,x1*)⩾AF(x2*,x1*) for all y∈N(x2*). So, x2* is a local minimizer of AF(x,x1*).Theorem 4.3.
Any local minimizerx¯ of AF(x,x1*) is in set S2 or a vertex of Ω⋂Zn.  If AF(x¯,x1*)<0, then x¯ is not only a local minimizer of F(x) which is better than x1*,  but also a local minimizer of f(x) over S.Proof.
Letx¯ be a local minimizer of AF(x,x1*), and suppose that x¯ is not a vertex of Ω⋂Zn, then there exists an integer i0∈[1,n] (n is the dimension of problem (P)), such that x¯±ei0∈Ω⋂Zn. It can be proved that F(x¯)<F(x1*).
In fact, suppose thatF(x¯)⩾F(x1*) holds.
Ifthereexistsy1∈{x¯±ei0} satisfies F(y1)<F(x1*), then
(4.10)AF(x¯,x1*)=11+∥x¯-x1*∥>0>F(y1)-F(x1*)=AF(y1,x1*).
Otherwise,thereexistsy2∈{x¯±ei0} satisfies ∥y2-x1*∥>∥x¯-x1*∥, then
(4.11)AF(x¯,x1*)=11+∥x¯-x1*∥>11+∥y2-x1*∥=AF(y2,x1*),
which contradicts with the fact that x¯ is a local minimizer of AF(x,x1*), so x¯∈S2.
IfAF(x¯,x1*)<0, we have F(x¯)<F(x1*). In fact, suppose that F(x¯)⩾F(x1*), then
(4.12)AF(x¯,x1*)=11+∥x¯-x1*∥>0,
which contradicts with AF(x¯,x1*)<0.
Suppose thatx¯ is not a local minimizer of F(x), then thereexistsy3∈N(x¯) such that F(x¯)>F(y3) holds. By the definition of AF(x,x1*), one has AF(x¯,x1*)=F(x¯)-F(x1*)>F(y3)-F(x1*)=AF(y3,x1*), which contradicts with the fact that x¯ is a local minimizer of AF(x,x1*).
By the definition ofF(x), we know that F(x¯)<F(x1*)⩽M, then x¯ is a feasible point. By Theorem 3.1, we know that x¯ is a local minimizer of f(x). The proof is completed.From Theorems4.2 and 4.3, it can be seen that S2 contains a minimizer of AF(x,x1*), and when the minimizer x¯ of AF(x,x1*) satisfies AF(x¯,x1*)<0, it is also a local minimizer of F(x) and better than the current local minimizer. It can also be seen that even if x1* is an infeasible local minimizer, a feasible local minimizer of f(x) will be found by an iteration, and there will be no infeasible local minimizer in the subsequent iterations.


## 5. Global Optimization Algorithm Based on New Auxiliary Function

### 5.1. Global Optimization Algorithm

Based on the theoretical analysis in Section4, a global optimization algorithm to solve problem (P) is given as follows.Algorithm 5.1.
Step 0.
Take an initial pointx0∈Ω⋂Zn, a sufficiently large number M.Step 1.
Use the local search algorithm in Section2 to F(x) at x0, obtain a local minimizer x1* of F(x), and set k:=1.Step 2.
LetD={d1,d2,…,d2n}, where di=ei, dn+i=-ei, i=1,2,…,n.Step 3.
Construct the auxiliary function(5.1)AF(x,xk*)=11+∥x-xk*∥×w((F(x)-F(xk*))(1+∥x-xk*∥)).
Let xk,i=xk*+di, set MS=∅, and i:=1.Step 4.
Use the local search algorithm in Section2 to AF(x,xk*) with the initial point xk,i and obtain a local minimizer xk,i* of AF(x,xk*) over Ω⋂Zn. If F(xk,i*)<F(xk*), set MS=MS⋃{xk,i*}. Go to Step 5.Step 5.
Ifi⩾2n, go to Step 6; otherwise, i=:i+1; go to Step 4.Step 6.
IfMS=∅, go to Step 7; otherwise, find a point in MS≠∅ with the smallest function value of F(x) and denote it as xk+1*. Set k:=k+1, and go back to Step 3.Step 7.
Outputxk*.Remarks on the Algorithm
(1)
In Step4, if a local minimizer xk+1* of AF(x,xk*) is found, then xk+1* is a local minimizer of the problem (P). It is different from the discrete filled function method in which the local search algorithm should be employed to F(x) and AF(x,xk*) repeatedly. Therefore, the proposed algorithm can reduce the computational cost.(2)
From the above theorems, we can see that althoughx1* may be an infeasible point, {xi*,i⩾2} are all feasible local minimizers of f(x) over S.(3)
Generally,M must be a sufficiently large number. In the implementation of the proposed algorithm, we first estimate an upper bound Bupper of f(x) over S, then take M=Bupper+1 or directly the upper bound Bupper if it is big enough.


### 5.2. Numerical Experiment

We apply the proposed algorithm to solve the following test problems.Problem 1.
(5.2)min⁡f(x)=(x1-10)3+(x2-20)3,s.t.-(x1-5)2-(x2-5)2+100⩽0-x1+10⩽0,-x2+5⩽0,x∈Ω={x∣0⩽xi⩽100,i=1,2}.
The box Ω has 10201 points. The global minimizer is x*=[15,5]T with f(x*)=-3250.Problem 2.
(5.3)min⁡f(x)=-24×∏i=14xi100,s.t.∑i=14(xi100)2=1,x∈Ω={x∣0⩽xi⩽100,i=1,2,3,4}.
The box Ω has 104060401 points. The global minimizer is x*=[50,50,50,50]T with f(x*)=-1.Problem 3.
(5.4)min⁡f(x)=-25(x1-2)2-(x2-2)2-(x3-1)2-(x4-4)2-(x5-1)2-(x6-4)2,s.t.-(x3-3)2-x4+4⩽0,-(x5-3)2-x6+4⩽0,x1-3x2-2⩽0,-x1+x2-2⩽0,x1+x2-6⩽0,-x1-x2+2⩽0,0⩽x1⩽6,0⩽x2⩽8,0⩽x3⩽5,0⩽x4⩽6,0⩽x5⩽10,0⩽x6⩽10.
The box Ω has 320166 points. The global minimizer is x*=(5,1,5,0,5,10)T with f(x*)=-310.Problem 4 (Colville’s function).
(5.5)min⁡f(x)=100(x2-x12)2+(1-x1)2+90(x4-x32)2+(1-x3)2+10.1[(x2-1)2+(x4-1)2]+19.8(x2-1)(x4-1),s.t.-10≤xi≤10,xiisinteger,i=1,2,3,4.
This box-constrained problem has1.94481×105 feasible points. The global minimizer is x*=[1,1,1,1]T with f(x*)=0.Problem 5 (Goldstein and Price’s function).
(5.6)min⁡f(x)=g(x)h(x),s.t.xi=yi1000,-2000⩽yi⩽2000,yiisinteger,i=1,2,
where g(x)=1+(x1+x2+1)2(19-14x1+3x12-14x2+16x1x2+3x22) and h(x)=30+(2x1-3x2)2(18-32x1+12x12+48x2-36x1x2+27x22).
This box constrained problem has1.6008001×107 feasible points. The global minimizer is x*=[0,-1]T with f(x*)=3.Problem 6 (Beale’s function).
(5.7)min⁡f(x)=[1.5-x1(1-x2)]2+[2.25-x1(1-x22)]2+[2.65-x1(1-x23)]2,s.t.xi=yi1000,-10000⩽yi⩽10000,yiisinteger,i=1,2.
This box-constrained problem has 4.00040001×108 feasible points. The global minimizer is x*=[3,0.5]T with f(x*)=0.Problem 7 (Rosenbrock’s function).
(5.8)min⁡f(x)=∑i=124[100(xi+1-xi2)2+(1-xi)2],s.t.-5⩽xi⩽5,xiisinteger,i=1,2,…,25.
This box-constrained problem has1.08347×1026 feasible points. The global minimizer is x*=[1,1,…,1]T with f(x*)=0.We apply the proposed algorithm to solve the above problems, and numerical results are shown in Tables1 to 5. In these tables, x0 denotes the initial point; x* denotes the last local minimizer of the original objective function; Ef+g denotes the total number evaluations of original function and auxiliary (filled) function.Table 1
Numerical results for Problems1–3.
Problemx0Mx*Ef+g1[25,25]108[15,5]T2632[50,50]108[15,5]T2832[75,75]108[15,5]T30322[25,25,25,25]1[50,50,50,50]T12522[50,50,50,50]1[50,50,50,50]T9172[75,75,75,75]1[50,50,50,50]T136293[0,0,0,0,0,0]1[5,1,5,0,5,10]T93307[3,4,2,3,5,5]1[5,1,5,0,5,10]T62671[6,8,5,6,10,10]1[5,1,5,0,5,10]T96443Table1 gives the results obtained by the proposed algorithm for Problems 1–3.Problems1–3 are with nonlinear objective function and nonlinear constraint functions. It is hard for an algorithm to solve. However, it can be seen from Table 1 that for Problems 1–3, the proposed algorithm can find the global optimal solutions for all these three problems using relatively small number of function evaluations.In order to demonstrate the efficiency of the proposed algorithm, we compare the proposed algorithm with other two discrete filled function methodsDFMA and DFMB ([14, 19]) for Problems 4–7. The results are summarized in Tables 2–5, where DFMA and DFMB denote the discrete filled function methods proposed in [14, 19], respectively, and AFM denotes the proposed auxiliary function algorithm. In implementation of the algorithm, F(x)=f(x) for Problems 4–7.Table 2
Numerical results of Problem4 (M=108).
Algorithmx0x*Ef+gAFM[1,1,0,0]T[1,1,1,1]T3936[1,1,1,1]T[1,1,1,1]T3324[-10,10,-10,10]T[1,1,1,1]T4977[-10,-5,0,5]T[1,1,1,1]T3454[-10,0,0,-10]T[1,1,1,1]T3571[0,0,0,0]T[1,1,1,1]T3539DFMA[1,1,0,0]T[1,1,1,1]T9153[1,1,1,1]T[1,1,1,1]T9123[-10,10,-10,10]T[1,1,1,1]T14543[-10,-5,0,5]T[1,1,1,1]T9248[-10,0,0,-10]T[1,1,1,1]T9285[0,0,0,0]T[1,1,1,1]T9162DFMB[1,1,0,0]T[1,1,1,1]T6523[1,1,1,1]T[1,1,1,1]T6498[-10,10,-10,10]T[1,1,1,1]T8553[-10,-5,0,5]T[1,1,1,1]T6701[-10,0,0,-10]T[1,1,1,1]T6655[0,0,0,0]T[1,1,1,1]T6530Table 3
Numerical results of Problem5 (M=108).
Algorithmx0x*Ef+gAFM[2,-2]T[0,-1]T118743[0,-1]T[0,-1]T83181[-2,-2]T[0,-1]T91850[-0.5,-1]T[0,-1]T86024[1,-1.5]T[0,-1]T113741[1,-1]T[0,-1]T91698DFMA[2,-2]T[0,-1]T268489[0,-1]T[0,-1]T254444[-2,-2]T[0,-1]T270930[-0.5,-1]T[0,-1]T254444[1,-1.5]T[0,-1]T267978[1,-1]T[0,-1]T254444DFMB[2,-2]T[0,-1]T176397[0,-1]T[0,-1]T170351[-2,-2]T[0,-1]T175828[-0.5,-1]T[0,-1]T171831[1,-1.5]T[0,-1]T173889[1,-1]T[0,-1]T173334Table 4
Numerical results of Problem6 (M=108).
Algorithmx0x*Ef+gAFM[10,-10]T[3,0.5]T815212[0.997,-6.867]T[3,0.5]T813561[0,-1]T[3,0.5]T414793[1,1]T[3,0.5]T438751[-2,2]T[3,0.5]T537546[0,0]T[3,0.5]T410793DFMA[10,-10]T[3,0.5]T2189978[0.997,-6.867]T[3,0.5]T2192230[0,-1]T[3,0.5]T2197097[1,1]T[3,0.5]T1356906[-2,2]T[3,0.5]T1356906[0,0]T[3,0.5]T2527711DFMB[10,-10]T[3,0.5]T1430248[0.997,-6.867]T[3,0.5]T1431740[0,-1]T[3,0.5]T1439584[1,1]T[3,0.5]T830822[-2,2]T[3,0.5]T829445[0,0]T[3,0.5]T911090Table 5
Numerical results of Problem7 (M=106).
Algorithmx0x*Ef+gAFM[0,…,0]T[1,…,1]T873553[3,…,3]T[1,…,1]T557111[-5,…,-5]T[1,…,1]T463176[2,-2,…,2,-2,2]T[1,…,1]T576770[3,-3,…,3,-3,3]T[1,…,1]T794156[5,-5,…,5,-5,5]T[1,…,1]T581242DFMA[0,…,0]T[1,…,1]T893881[3,…,3]T[1,…,1]T1317062[-5,…,-5]T[1,…,1]T899485[2,-2,…,2,-2,2]T[1,…,1]T896281[3,-3,…,3,-3,3]T[1,…,1]T1516925[5,-5,…,5,-5,5]T[1,…,1]T1518820DFMB[0,…,0]T[1,…,1]T615173[3,…,3]T[1,…,1]T956979[-5,…,-5]T[1,…,1]T620725[2,-2,…,2,-2,2]T[1,…,1]T617573[3,-3,…,3,-3,3]T[1,…,1]T655048[5,-5,…,5,-5,5]T[1,…,1]T756943For Problem4, it can be seen from Table 2 that all three algorithms can find global optimal solution, but the number of the function evaluations used by proposed algorithm AFM is only about 1/3 of that used by DFMA and only about half of that used by DFMB. For Problems 5 and 6, we can see from Tables 3-4 that all three algorithms can also find global optimal solutions, but the number of function evaluations used by DFMA is more than twice of that used by AFM, and the number of function evaluations used by DFMB is more than 1.5 times of that used by AFM. For Problem 7, it can be seen from Table 5 that the number of function evaluations used by AFM is also much smaller than those used by DFMA and DFMB. These results demonstrate that the proposed algorithm is effective and more efficient than the compared algorithms.


## 5.1. Global Optimization Algorithm

Based on the theoretical analysis in Section4, a global optimization algorithm to solve problem (P) is given as follows.Algorithm 5.1.
Step 0.
Take an initial pointx0∈Ω⋂Zn, a sufficiently large number M.Step 1.
Use the local search algorithm in Section2 to F(x) at x0, obtain a local minimizer x1* of F(x), and set k:=1.Step 2.
LetD={d1,d2,…,d2n}, where di=ei, dn+i=-ei, i=1,2,…,n.Step 3.
Construct the auxiliary function(5.1)AF(x,xk*)=11+∥x-xk*∥×w((F(x)-F(xk*))(1+∥x-xk*∥)).
Let xk,i=xk*+di, set MS=∅, and i:=1.Step 4.
Use the local search algorithm in Section2 to AF(x,xk*) with the initial point xk,i and obtain a local minimizer xk,i* of AF(x,xk*) over Ω⋂Zn. If F(xk,i*)<F(xk*), set MS=MS⋃{xk,i*}. Go to Step 5.Step 5.
Ifi⩾2n, go to Step 6; otherwise, i=:i+1; go to Step 4.Step 6.
IfMS=∅, go to Step 7; otherwise, find a point in MS≠∅ with the smallest function value of F(x) and denote it as xk+1*. Set k:=k+1, and go back to Step 3.Step 7.
Outputxk*.Remarks on the Algorithm
(1)
In Step4, if a local minimizer xk+1* of AF(x,xk*) is found, then xk+1* is a local minimizer of the problem (P). It is different from the discrete filled function method in which the local search algorithm should be employed to F(x) and AF(x,xk*) repeatedly. Therefore, the proposed algorithm can reduce the computational cost.(2)
From the above theorems, we can see that althoughx1* may be an infeasible point, {xi*,i⩾2} are all feasible local minimizers of f(x) over S.(3)
Generally,M must be a sufficiently large number. In the implementation of the proposed algorithm, we first estimate an upper bound Bupper of f(x) over S, then take M=Bupper+1 or directly the upper bound Bupper if it is big enough.


## 5.2. Numerical Experiment

We apply the proposed algorithm to solve the following test problems.Problem 1.
(5.2)min⁡f(x)=(x1-10)3+(x2-20)3,s.t.-(x1-5)2-(x2-5)2+100⩽0-x1+10⩽0,-x2+5⩽0,x∈Ω={x∣0⩽xi⩽100,i=1,2}.
The box Ω has 10201 points. The global minimizer is x*=[15,5]T with f(x*)=-3250.Problem 2.
(5.3)min⁡f(x)=-24×∏i=14xi100,s.t.∑i=14(xi100)2=1,x∈Ω={x∣0⩽xi⩽100,i=1,2,3,4}.
The box Ω has 104060401 points. The global minimizer is x*=[50,50,50,50]T with f(x*)=-1.Problem 3.
(5.4)min⁡f(x)=-25(x1-2)2-(x2-2)2-(x3-1)2-(x4-4)2-(x5-1)2-(x6-4)2,s.t.-(x3-3)2-x4+4⩽0,-(x5-3)2-x6+4⩽0,x1-3x2-2⩽0,-x1+x2-2⩽0,x1+x2-6⩽0,-x1-x2+2⩽0,0⩽x1⩽6,0⩽x2⩽8,0⩽x3⩽5,0⩽x4⩽6,0⩽x5⩽10,0⩽x6⩽10.
The box Ω has 320166 points. The global minimizer is x*=(5,1,5,0,5,10)T with f(x*)=-310.Problem 4 (Colville’s function).
(5.5)min⁡f(x)=100(x2-x12)2+(1-x1)2+90(x4-x32)2+(1-x3)2+10.1[(x2-1)2+(x4-1)2]+19.8(x2-1)(x4-1),s.t.-10≤xi≤10,xiisinteger,i=1,2,3,4.
This box-constrained problem has1.94481×105 feasible points. The global minimizer is x*=[1,1,1,1]T with f(x*)=0.Problem 5 (Goldstein and Price’s function).
(5.6)min⁡f(x)=g(x)h(x),s.t.xi=yi1000,-2000⩽yi⩽2000,yiisinteger,i=1,2,
where g(x)=1+(x1+x2+1)2(19-14x1+3x12-14x2+16x1x2+3x22) and h(x)=30+(2x1-3x2)2(18-32x1+12x12+48x2-36x1x2+27x22).
This box constrained problem has1.6008001×107 feasible points. The global minimizer is x*=[0,-1]T with f(x*)=3.Problem 6 (Beale’s function).
(5.7)min⁡f(x)=[1.5-x1(1-x2)]2+[2.25-x1(1-x22)]2+[2.65-x1(1-x23)]2,s.t.xi=yi1000,-10000⩽yi⩽10000,yiisinteger,i=1,2.
This box-constrained problem has 4.00040001×108 feasible points. The global minimizer is x*=[3,0.5]T with f(x*)=0.Problem 7 (Rosenbrock’s function).
(5.8)min⁡f(x)=∑i=124[100(xi+1-xi2)2+(1-xi)2],s.t.-5⩽xi⩽5,xiisinteger,i=1,2,…,25.
This box-constrained problem has1.08347×1026 feasible points. The global minimizer is x*=[1,1,…,1]T with f(x*)=0.We apply the proposed algorithm to solve the above problems, and numerical results are shown in Tables1 to 5. In these tables, x0 denotes the initial point; x* denotes the last local minimizer of the original objective function; Ef+g denotes the total number evaluations of original function and auxiliary (filled) function.Table 1
Numerical results for Problems1–3.
Problemx0Mx*Ef+g1[25,25]108[15,5]T2632[50,50]108[15,5]T2832[75,75]108[15,5]T30322[25,25,25,25]1[50,50,50,50]T12522[50,50,50,50]1[50,50,50,50]T9172[75,75,75,75]1[50,50,50,50]T136293[0,0,0,0,0,0]1[5,1,5,0,5,10]T93307[3,4,2,3,5,5]1[5,1,5,0,5,10]T62671[6,8,5,6,10,10]1[5,1,5,0,5,10]T96443Table1 gives the results obtained by the proposed algorithm for Problems 1–3.Problems1–3 are with nonlinear objective function and nonlinear constraint functions. It is hard for an algorithm to solve. However, it can be seen from Table 1 that for Problems 1–3, the proposed algorithm can find the global optimal solutions for all these three problems using relatively small number of function evaluations.In order to demonstrate the efficiency of the proposed algorithm, we compare the proposed algorithm with other two discrete filled function methodsDFMA and DFMB ([14, 19]) for Problems 4–7. The results are summarized in Tables 2–5, where DFMA and DFMB denote the discrete filled function methods proposed in [14, 19], respectively, and AFM denotes the proposed auxiliary function algorithm. In implementation of the algorithm, F(x)=f(x) for Problems 4–7.Table 2
Numerical results of Problem4 (M=108).
Algorithmx0x*Ef+gAFM[1,1,0,0]T[1,1,1,1]T3936[1,1,1,1]T[1,1,1,1]T3324[-10,10,-10,10]T[1,1,1,1]T4977[-10,-5,0,5]T[1,1,1,1]T3454[-10,0,0,-10]T[1,1,1,1]T3571[0,0,0,0]T[1,1,1,1]T3539DFMA[1,1,0,0]T[1,1,1,1]T9153[1,1,1,1]T[1,1,1,1]T9123[-10,10,-10,10]T[1,1,1,1]T14543[-10,-5,0,5]T[1,1,1,1]T9248[-10,0,0,-10]T[1,1,1,1]T9285[0,0,0,0]T[1,1,1,1]T9162DFMB[1,1,0,0]T[1,1,1,1]T6523[1,1,1,1]T[1,1,1,1]T6498[-10,10,-10,10]T[1,1,1,1]T8553[-10,-5,0,5]T[1,1,1,1]T6701[-10,0,0,-10]T[1,1,1,1]T6655[0,0,0,0]T[1,1,1,1]T6530Table 3
Numerical results of Problem5 (M=108).
Algorithmx0x*Ef+gAFM[2,-2]T[0,-1]T118743[0,-1]T[0,-1]T83181[-2,-2]T[0,-1]T91850[-0.5,-1]T[0,-1]T86024[1,-1.5]T[0,-1]T113741[1,-1]T[0,-1]T91698DFMA[2,-2]T[0,-1]T268489[0,-1]T[0,-1]T254444[-2,-2]T[0,-1]T270930[-0.5,-1]T[0,-1]T254444[1,-1.5]T[0,-1]T267978[1,-1]T[0,-1]T254444DFMB[2,-2]T[0,-1]T176397[0,-1]T[0,-1]T170351[-2,-2]T[0,-1]T175828[-0.5,-1]T[0,-1]T171831[1,-1.5]T[0,-1]T173889[1,-1]T[0,-1]T173334Table 4
Numerical results of Problem6 (M=108).
Algorithmx0x*Ef+gAFM[10,-10]T[3,0.5]T815212[0.997,-6.867]T[3,0.5]T813561[0,-1]T[3,0.5]T414793[1,1]T[3,0.5]T438751[-2,2]T[3,0.5]T537546[0,0]T[3,0.5]T410793DFMA[10,-10]T[3,0.5]T2189978[0.997,-6.867]T[3,0.5]T2192230[0,-1]T[3,0.5]T2197097[1,1]T[3,0.5]T1356906[-2,2]T[3,0.5]T1356906[0,0]T[3,0.5]T2527711DFMB[10,-10]T[3,0.5]T1430248[0.997,-6.867]T[3,0.5]T1431740[0,-1]T[3,0.5]T1439584[1,1]T[3,0.5]T830822[-2,2]T[3,0.5]T829445[0,0]T[3,0.5]T911090Table 5
Numerical results of Problem7 (M=106).
Algorithmx0x*Ef+gAFM[0,…,0]T[1,…,1]T873553[3,…,3]T[1,…,1]T557111[-5,…,-5]T[1,…,1]T463176[2,-2,…,2,-2,2]T[1,…,1]T576770[3,-3,…,3,-3,3]T[1,…,1]T794156[5,-5,…,5,-5,5]T[1,…,1]T581242DFMA[0,…,0]T[1,…,1]T893881[3,…,3]T[1,…,1]T1317062[-5,…,-5]T[1,…,1]T899485[2,-2,…,2,-2,2]T[1,…,1]T896281[3,-3,…,3,-3,3]T[1,…,1]T1516925[5,-5,…,5,-5,5]T[1,…,1]T1518820DFMB[0,…,0]T[1,…,1]T615173[3,…,3]T[1,…,1]T956979[-5,…,-5]T[1,…,1]T620725[2,-2,…,2,-2,2]T[1,…,1]T617573[3,-3,…,3,-3,3]T[1,…,1]T655048[5,-5,…,5,-5,5]T[1,…,1]T756943For Problem4, it can be seen from Table 2 that all three algorithms can find global optimal solution, but the number of the function evaluations used by proposed algorithm AFM is only about 1/3 of that used by DFMA and only about half of that used by DFMB. For Problems 5 and 6, we can see from Tables 3-4 that all three algorithms can also find global optimal solutions, but the number of function evaluations used by DFMA is more than twice of that used by AFM, and the number of function evaluations used by DFMB is more than 1.5 times of that used by AFM. For Problem 7, it can be seen from Table 5 that the number of function evaluations used by AFM is also much smaller than those used by DFMA and DFMB. These results demonstrate that the proposed algorithm is effective and more efficient than the compared algorithms.


## 6. Concluding Remarks

In this paper, we propose an auxiliary function method for finding the global minimizer of integer programming problems. The auxiliary function can help to escape from a local minimizer and to get a better one. The minimizer of the auxiliary function also is a feasible minimizer of the original problem and better than the current best one obtained. The numerical results show that the proposed algorithm is more effective and efficient than the compared ones.



---

*Source: 402437-2011-11-24.xml*