Method Exact

(1)

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem:

Subgradient Method Approach

S.-L. KIM¹ AND S. KIM² Communicated by D. G. Luenberger

Abstract. One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al.

adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.

Key Words. Integer programming, surrogate dual, nondifferentiable optimization, subgradient method.

1. Introduction

In this paper, we present an algorithm for solving the surrogate dual of an integer programming problem given by

1Senior Member of Engineering Staff, System Engineering Section, Mobile Telecommunications Division, Electronics and Telecommunications Research Institute, Taejon, Korea.

2Professor, Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Taejon, Korea.

363

0022-3239/98/0200-0363$15.00/0 C 1998 Plenum Publishing Corporation

(2)

364 JOTA: VOL. 96, NO. 2, FEBRUARY 1998

where

We assume that problem (P) is feasible and that X is a bounded and finite set which has a relatively simple structure not possessed by the entire problem (P).

For given nonnegative vector peRm, consider a surrogate relaxation problem of (P) defined as follows:

Then, the surrogate dual of problem (P) is given by

where v( •) denotes the optimal objective function value of problem ( • ) . In the surrogate dual (Ds), since the set X is finite, "sup" can be replaced by "max" (Ref. 1). It is evident that

and thus zero may be excluded from the possible vectors solving (Ds). Also, it is clear that

Thus, an arbitrary normalization of the vector i is possible and has the advantage to belong to a compact set. Hence, for the convenient construction of our algorithm, we rewrite the surrogate dual (Ds) as follows:

Hereafter, we will use (Dn) as the surrogate dual of problem (P).

One of the critical issues in the effective use of surrogate relaxation is how to solve the surrogate dual within a reasonable amount of computational time. The surrogate dual is theoretically superior to the Lagrangian dual in view of the duality gap provided (Refs. 2 and 3). Moreover, it is well known that some specially structured problems have zero primal-surrogate

(3)

duality gap (Refs. 2, 4, 5). However, solving the surrogate dual involves a complicating problem, the maximization of a quasiconcave function;

u(S(u)) is a quasiconcave function of n (Ref. 2). Hence, the search for optimal surrogate multipliers is more difficult than that of optimal Lagrange multipliers.

Dyer (Ref. 1), Gavish and Pirkul (Ref. 6), Karwan and Rardin (Ref.

7), and Sarin et al. (Ref. 8) have proposed heuristic or exact algorithms for the surrogate dual. Concerning heuristic algorithms (Refs. 6-8), they may produce bounds which are inferior to those provided by Lagrangian relaxation. Concerning exact algorithms (Refs. 1 and 7), none of the above researchers were able to provide a practical algorithm. That is, either these algorithms were not implemented (Ref. 1) or their computational efficiency is in doubt (Ref. 7). Among these works, the Karwan and Rardin algorithms were based on the analogy between surrogate and Lagrangian duality in integer programming and have gathered new inter- ests in this area.

On improving the Karwan and Rardin study, Sarin et al. suggested algorithms which solve successive Lagrangian duals as subproblems. For solving Lagrangian duals, there exist efficient techniques: the subgradient method (Ref. 9) and its variants (Refs. 9-11); hence, this approach seems to be very promising in its computational efficiency. However, the algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving Lagrangian duals;

therefore, they are not able to provide an exact solution to the surrogate dual.

In developing our algorithm, we follow the approach introduced by Sarin et al. In this paper, we show that the heuristic nature of the Sarin method can be eliminated. Hence, our modified method is an exact algorithm for the surrogate dual. Our algorithm has been implemented and computational experiments have been performed.

In Sections 2 and 3, theoretical results are presented: they play an important role in our algorithm. Our algorithm with its convergence proof is described in Section 4. Computational results are reported in Section 5 for multiconstraint 0-1 knapsack problems and show the practical applicability of our algorithm. Concluding remarks are contained in Section 6.

2. Preliminaries

Let us consider the following two problems and related results, introduced independently, although not exactly in the same manner, by Dyer (Ref. 1) and by Karwan and Rardin (Ref. 7).

(4)

JOTA: VOL. 96, NO. 2, FEBRUARY 1998 366

[For given aeR and teM, the first problem is

For given aeR, the second problem is

Note that problem (D(a)) has the form of a Lagrangian dual. We can easily show that v(D(a)) is monotone increasing and upper semicontinuous.

Furthermore, we have the following results.

Theorem 2.1. (See Refs. 1 and 7.) For given aeR, v(D(a))>0 if and only if v(Dn s)<a.

Corollary 2.1. (See Refs. 1 and 7.) v(Dn) is the minimum aeR such that u(D(a))>0.

With Theorem 2.1 and Corollary 2.1, Sarin et al. developed surrogate dual multiplier search algorithms. Changing a systematically, these algorithms solve problem (D(a)) as a subproblem, which can be described gen- erally as follows: For given ai, solve (D(a,)). If v(D(ai)) >0, then a, is set to an upper bound of v(Dn); take ai+1 which is less than ai, and solve problem (D(ai+ i)). Otherwise, a, is set to a lower bound of v(Dn); take ori+1 which is greater than a,, and solve problem (D(ai+ 1)). This continues until the deviation between the least upper bound and the greatest lower bound is sufficiently small, for example, not greater than a small positive value e.

For solving (D(a)), a nondifferentiable optimization problem, Sarin et al. used the modified subgradient method of Camerini et al. (Ref. 10). How- ever, the modified subgradient method does not always find a descent direction at each step of the method. Moreover, it does not guarantee optimal solutions of (D(a)) without prior knowledge of u(D(a)). This comes from a common drawback of the subgradient method and its variants; see Ref. 12 for details on convergence properties of the subgradient method.

Although it is sufficient to determine whether

(5)

Sarin et al. had no way of checking v(D(a)) > 0 at a finite step. So, for finite termination, their algorithms use an ad-hoc stopping rule in determining v(D(a)) >0, which may result in the unerestimation of u(Dn).

In the next section, we show that it is actually possible to check u(D(c)) >0 at a finite step. This will enable us to develop an exact algorithm for the surrogate dual.

3. Checking whether w(D(a))>0

For given aeR, to solve (D(a)), suppose that we generate a sequence of points {Hk} as follows:

where sk is a stepsize and gk is a subgradient of v(P(a, u)) at p =Hk- For given %eRm, the projection of £ on M, denoted by proj(e), is the unique point in M such that

By \\ • \\, we mean the Euclidean norm. From a special structure of M, we can obtain proj (e) with a small computational burden. A subgradient gk is simply obtained from the fact that, when xka is an optimal solution of (P(a, uk) ) , the vector Axka -b is a subgradient of u(P(a, u)) at n = uk.

If gk = 0, then Hk is an optimal solution of (D(or)). Now, let us assume that

and consider the following stepsize choice rule:

where the parameter wk is less than or equal to v ( P ( a , uk) ) for all k and {wk} is a monotone decreasing sequence bounded from below. Then, we have the following results due to Kim et al. (Ref. 13).

Theorem 3.1. (See Ref. 13, p. 361.) For given aeR, suppose that a sequence {nk} is generated by (1) with the stepsize rule (2) and lim* wk = w>v(D(a)). Then, l i mk - I, v(P(a, Hk)) = w.

Theorem 3.2. (See Ref. 13, p. 363.) For given aeR, suppose that a sequence {uk} is generated by (1) with the stepsize rule (2). Let u* be an

(6)

368 JOTA: VOL. 96, NO. 2, FEBRUARY 1998

optimal solution of (D(a)). Then, we have the following results:

Theorem 3.2 says that, if an upper bound of ||u1-u*|| and a lower bound of ||nk-n|| are available, then we can check whether

within a finite number of steps. Since M is a bounded set, we can simply use the diameter of M as an upper bound of ||u1 -u*|| and zero as a lower bound of | | H k - n * | | . A better bound estimation will save further computational effort. For this better estimation, consider the following notation. For each xeX(a), let us define

If there exists yeM which does not belong to Hxa for some xeX(a), then v(P(a, p))>0. Hence, if v(D(a)) <0, then an optimal solution n* of (D(a)) must belong to Hxa for all xeX(a). Now, for X'<=X(a), let Ha(X'} = CxeX''Hxa. Then, we have the following lemma.

Lemma 3.1. For given aeR, suppose that v(D(a))<0, and let X' be a nonempty subset of X(a). Then, Ha(X')^0 and 0<r2<||uk-u*||2

R2<2, where

and p r o j ( uk on Ha(X')) denotes the projection of nk on Ha (X').

Proof. Suppose that v(D(a)) <,0. Then, n* belongs to Ha(X'). Hence, Ha(X')^0. The first three inequalities are obvious. The last inequality follows from the fact that the distance between any two points in M, a simplex of dimension m —1, is not greater than /2, which is the distance between two extreme points of M. D For the practical computation of Rk and rk, we may use an X' which has only one element xeX(a). In this case,

(7)

and Rk is the maximum of the Euclidean distances from nk to all the extreme points of Ha(X.'). The number of extreme points of Ha(X') is less than m(m + l)/2. Hence, Rk can be computed in polynomial time. In case H^k$H^a(X'), we may use r'^k, the Euclidean distance from u^k to the hyperplane n(Ax-b) = 0, as a substitute for r^k, because r'^k is less than or equal to r^k.

Corollary 3.1. For given a<=R, suppose that a sequence {uk*} is generated by (1) with the stepsize rule (2) and W1 <0. If

then v(D(a))>Wko.

Proof. Suppose that v(D(a))<wk°. Then, we have the following inequalities:

This is a contradiction. D For given aeR, to solve (D(a)), consider a sequence {u} generated by (1) with the stepsize rule (2). The parameter w^k is set to zero until the value of the objective function v(P(a, n^k)) becomes less than or equal to a small positive value €. Let k¹ be the first index such that v(P(a, u^k) ) < €¹. Then, w^k is set to —e² for all k>k¹ where e² is also a small positive value.

Now, we have the following lemma about the sequence {uk}.

Lemma 3.2. The sequence { nk} belongs to one of the following three cases:

(8)

Proof. Suppose that such k1 is not found, i.e.,

If v>(D(a))<0, then from Theorem 3.1,

This is a contradiction. Therefore v(D(a))>0, and from Theorem 3.2(ii),

Suppose that such k1 is found and that

If i>(D(a))<-e2, then from Theorem 3.1,

This is a contradiction. Therefore v>(D(a))>-e2, and from Theorem 3.2(ii),

In Case (a), since v>(D(a))<0, we can set a to a lower bound of u(Dn). In this case, since u(P(a, uk0))<0, the feasible region of (S(uk)) contains no x such that cx<a, and therefore, v(S(nk°)) > a. Hence, we have a better lower bound v ( S ( u k ° ) ) -

In Case (b), we can conclude that v(D(a))>0 from Corollary 3.1 and set a to an upper bound of v(Dn).

In Case (c), u(D(a))>-e2 from Corollary 3.1. Hence, -e2<

v(D(a)) < €1, and we cannot determine whether a is an upper bound or a lower bound of u(Dn). In this case, we try another value of a. In practice, Case (c) rarely occurs for sufficiently small values of el and e2. This will be shown empirically in the computational results of Section 5.

(9)

4. Algorithm

Below, we suggest an algorithm which solves the surrogate dual (Dn):

Step 0. (Initialize.) Choose U1>v(Dⁿ), v1eM, L1 = v(S(v1))<

v(Dⁿ), and e, e1, e²>0. Set i=1.

Step 1. (Check the Terminating Condition.) If U i - L < e , then terminate.

Step 2. (Inner Loop.) Set qi = 0.

Step 2.1. Choose A,- such that 0< S3 < A, < 1 - 54 < 1.

Set ai = A,Uⁱ + (l-L)Li.

Step 2.2 (Solve (D(ai).) Choose n1eM. Set w, = 0, S = 0, and k=1.

Step 2.2.1. (Check i>(D(ai))<0.) Solve ( P ( ai, nk) ) . If v(P(Ai, uk))<0, then go to Step 3.

Step 2.2.2. Obtain a subgradient g^k of v(P(a^t, ju)) at u = p^k. If g^k = 0, then v>(D(ai)) = v(P(a, uk))>0 and go to Step 4.

Step 2.2.3. If v(P(ai, u^k) ) < e¹, then set w^k = -e².

Step 2.2.4. Set n^k+1 = proj(n^k — s^kg^k), with sk from (2) and S = S + r^k( 2 - Y k ) ( v ( P ( aⁱ, u^k) ) - w^k)²/ | | g^k| |².

Step 2.2.5. If S>R²-r^{2 k + 1} and w^k = 0, then go to Step 4.

Step 2.2.6. If S>R²-r^{2 k + 1} and w^k = — e² then set qi = qi+ 1 and go to Step 2.1.

Step 2.2.7. Set k = k + 1 and go to Step 2.2.1.

Step 3. (Update the Lower Bound of u(Dⁿ).) Step 3.1. Solve (S(uk)).

Step 3.2. Set Uⁱ⁺¹ = Uⁱ, L^{i+ 1} = v(S(uk)), v^{i+ 1} = uk, i=i+ 1, and go to Step 1.

Step 4. (Update the Upper Bound of v(Dⁿ).) Set Uⁱ⁺¹ = aⁱ, Li+1 = Li, vi+1, = vi, i = i + 1, and go to Step 1.

In the algorithm, {L} and {Ui] are monotonic sequences of lower and upper bounds of u(Dn), respectively. The sequence {v,} denotes a set of

(10)

points such that L, = u(S(v,)). In Step 0, for any feasible solution x of (P), cx may be a candidate for U1. In this step, very small values are used for e1 and e2. Case (a) described in Section 3 is checked in Step 2.2.1; Case (b) is checked in Step 2.2.5; and Case (c) is checked in Step 2.2.6. The value ql

denotes the number of times that the condition of Step 2.2.6 has been satis- fied during the ith inner loop.

Theorem 4.1. Suppose that qi is finite during each inner loop of the algorithm. Then, the algorithm terminates with Uio - Li< e at a finite iteration i0.

Proof. From the assumption and Lemma 3.2, each inner loop terminates at a finite step. Suppose that the ith inner loop terminates at Step 2.2.1.

Then, Li+1>ai. Hence,

Therefore,

Suppose that the i th inner loop terminates at Step 2.2.2 or Step 2.2.5. Then, Ui+1=Ai. Hence,

Therefore,

From (3) and (4), we can conclude that the algorithm terminates at a finite

iteration i0 with U-L0<e. D

In the above algorithm, suppose that all the elements of the vector c of (P) are integers. Then, any e which is less than one is sufficient in Step 0, and we can obtain the exact value v(Dn) = L,<> at a finite iteration i. In Step 3.1, suppose that x* is an optimal solution of (S(uk)) and satisfies the constraints Ax>b of (P). Then, pk solves (Dn), x* solves (P), and furthermore v(Dn) = v(P).

5. Computational Results

The proposed algorithm has been coded in PASCAL and run using a Hewlett-Packard 9000/825. Test problems are from the multiconstraint

(11)

0-1 knapsack problem (Ref. 6), given by

A is a nonnegative integer m xn matrix, and b and c are positive integer vectors of appropriate dimensions. The applications of this problem include resource allocation, project selection, capital budgeting, cargo loading problems, etc.

In the test, 15 randomly generated problems have been considered. The problem generator is essentially the one used by Karwan and Rardin (Ref.

7). We set a 0.75 density (i.e., fraction of nonzero elements) in the matrix A. Nonzero elements of A were randomly generated from the interval [1, 10].

The vector b was randomly generated from the interval [E/4, 3E/4], where E equals the expected value of the sum of all coefficients in any row of A.

The vector c was randomly generated from the interval [10, 100].

In the algorithm, we set

At the ith inner loop, for computation of Rk and r'k, we used

where x is an optimal solution of (P(a, v,)). Since (P(a, u)) and (S(uk)) are 0-1 knapsack problems, most of the computational time has been devoted to solving these 0-1 knapsack problems.

Computational results are summarized in Tables 1-3. In the tables, U1

and L1 denote the initial upper bound and the initial lower bound of v(Dⁿ), respectively. Iterl and Iter2 stand for the number of events updating the upper bound and the lower bound of v(Dⁿ), respectively. Time denotes the execution CPU time (in seconds, Hewlett-Packard 9000/825) to obtain

Table 1 . Computational results.

Prob.

No.

1 2 3 4 5

U¹

549 180 245 554 350

L, 195 136 142 194 238

Iterl 7 3 4 6 3

Iter2 2 2 2 2 4

Time 0.68 0.88 0.44 0.75 1.05

v(Dn) 287 176 236 298 252

v(P) 258.28 146.74 219.20 260.05 224.09

v(P) 287 180 245 315 317 Problem size: 5 x 10.

(12)

374 JOTA: VOL. 96, NO. 2, FEBRUARY 1998 Table 2. Computational results.

Prob.

No.

6 7 8 9 10

U1

541 259 745 379 540

L1

193 203 353 237 323

Iterl 5 5 6 4 4

Iter2 3 1 3 2 3

Time 1.73 6.24 10.99 4.61 9.31

v(Dns) 334 219 473 284 439

v(P) 323.29 205.59 431.50 255.70 426.33

v(P) 334 226 482 288 439 Problem size : 5 x 20.

Table 3. Computational results.

Prob.

No.

11 12 13 14 15

U1 340 311 411 342 318

L, 142 125 167 126 137

Iterl 1 4 2 4 3

Iter2 3 3 3 2 3

Time 1.84 5.38 4.14 3.86 3.26

v(Dn) 240 240 364 241 284

v(P) 212.84 210.94 346.00 199.75 243.71

v(P) 253 254 364 251 291 Problem size: 10 x 10.

v(Dn). The value v(P) means the optimal objective function value of the linear relaxation of (P). In all of the test problems, Case (c) described in Section 3 has not occurred; i.e., q = 0, for all i. From the tables, we can see that exact surrogate dual values have been computed with a small computational burden. As expected, the computed surrogate dual value u(Dn) is very close to v(P) compared with v(P).

6. Concluding Remarks

We have presented an exact algorithm for solving the surrogate dual of an integer programming problem. In developing the algorithm, we fol- lowed the approach which Sarin et al. introduced in their algorithms for the surrogate dual. We showed that the heuristic stopping criteria in the Sarin method can actually be eliminated. Computational results from our algorithm are encouraging and show the practical applicability of the algorithm to problems in which a more exact surrogate dual value may be helpful.

To use our algorithm more efficiently, we need to find a better technique for computing Rk and rk than that presented in this paper. Moreover, in the computational experiments, most of the time is devoted to solving problem (P(a,u)). Hence, we will obtain more benefits from our algorithm if we

(13)

apply our algorithm to problems which have a special structure such that solving (P(a,u)) is convenient. These two items are interesting future research problems.

References

1. DYER, M. E., Calculating Surrogate Constraints, Mathematical Programming.

Vol. 19, pp. 255-278, 1980.

2. GREENBERG, H. J., and PIERSKALLA, W. P, Surrogate Mathematical Program- ming, Operations Research, Vol. 18, pp. 924-939, 1970.

3. KARWAN, M. H., and RARDIN, R. L., Some Relationships between Lagrangian and Surrogate Duality in Integer Programming, Mathematical Programming, Vol.

17, pp. 320-334, 1979.

4. GLOVER, F., Surrogate Constraint Duality in Mathematical Programming, Opera- tions Research, Vol. 23, pp. 434-451, 1975.

5. RAM, B., and KARWAN, M. H., A Result in Surrogate Duality for Certain Integer Programming Problems, Mathematical Programming, Vol. 43, pp. 103-106,1989.

6. GAVISH, B., and PIRKUL, H., Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality, Mathematical Programming, Vol.

31, pp. 78-105, 1985.

7. KARWAN, M. H., and RARDIN, R. L., Surrogate Dual Multiplier Search Pro- cedures in Integer Programming, Operations Research, Vol. 32, pp. 52-69, 1984.

8. SARIN, S., KARWAN, M. H., and RARDIN, R. L., A New Surrogate Dual Multi- plier Search Procedure, Naval Research Logistics, Vol. 34, pp. 431-450, 1987.

9. POLYAK, B. T, Minimization of Unsmooth Functionals, USSR Computational Mathematics and Mathematical Physics, Vol. 9, pp. 14-29, 1969.

10. CAMERINI, P. M., FRATTA, L., and MAFFIOLI, F., On Improving Relaxation Methods by Modified Gradient Techniques, Mathematical Programming Study, Vol. 3, pp. 26-34, 1975.

11. KIM, S., KOH, S., and AHN, H., Two-Direction Subgradient Method for Non- differentiable Optimization Problems, Operations Research Letters, Vol. 6, pp.

43-46, 1987.

12. KIM, S., and AHN, H., Convergence of a Generalized Subgradient Method for Nondijferentiable Convex Optimization, Mathematical Programming, Vol. 50, pp. 75-80, 1991.

13. KIM, S., AHN, H., and CHO, S.-C, Variable Target Value Subgradient Method, Mathematical Programming, Vol. 49, pp. 359-369, 1991.