A Simplicial Algorithm for Concave Minimization and
Its Performance as a Heuristic Tool
Takahito Kuno∗ and Yoshiyuki Shiguro†
Graduate School of Systems and Information Engineering
University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan
July 2007

Abstract
In this paper, we develop a kind of branch-and-bound algorithm for solving concave minimization problems. We show that the algorithm converges to an optimal
solution of this multiextremal global optimization problem, and that it generates
a high-quality heuristic solution even if it is forced to terminate. Therefore, thealgorithm can be used in two ways, as an exact algorithm and as a heuristic tool.
We also report some numerical results of a comparison with an existing algorithm,
and show the performance as a heuristic tool.
Key words: Global optimization, concave minimization, branch-and-bound algorithm, simplicial algorithm, heuristic algorithm.

1

Introduction

Since the pioneer work of Tuy [17], various algorithms have been proposed to solve
concave minimization problems, where a concave function f is minimized globally on apolyhedral subset D of Rn . If the objective function f is linear, the problem is just a
linear program and can be solved in polynomial time [2]. In the nonlinear case, however,
the only clue to a globally optimal solution is that it exists among vertices of the feasible
set D. Since the maximum number of vertices of D is exponential in n [3], it is easy to
imagine how difficult the problem is to solve. In fact, it is known to be NP-hard in thesense of computational complexity, even when f is quadratic and D is a box [16].
The most popular method for solving this global optimization problem is the branchand-bound, commonly used in solving integer programs. However, while the latter∗†

E-mail: takahito@cs.tsukuba.ac.jp
Current affiliation: Software Knowledge Incorporated, Tokyo 107-0052, Japan

1

textbook_bb-5

incumbent value

-5.5

-6

-6.5

1

10

100
483
log( # iterations)

1000

3897

10000

Figure 1: Changes in the incumbent value in the simplicial algorithm.

reduces to a set of obvious subproblems as branching continues, the concave minimization
problem does not in general. As a consequence, the branch-and-bound algorithm often
exhibits long-tail convergence, as is shown in Figure 1. This figure demonstrates how
the incumbent value is updated while a concave quadratic minimization problem of 20
nonlinear variables is solved using a simplicial algorithm [4], a variant of the branch-andbound algorithm contained in any textbook on global optimization (see e.g., [5, 8, 18]).
The algorithm takes 3, 897 iterations for this particular instance, but it actually obtains
a globally optimal solution in 483 iterations. All the rest of the iterations are spent onlyin checking its optimality.
It is true that many applications require a globally optimal solution in high-precision,even at the expense of long-tail convergence as in the above branch-and-bound algorithm.
Meanwhile, there should also be many applications where a good feasible solution isenough if it is available in a small amount time. In this paper, to balance those competingneeds, we develop a new kind of branch-and-bound algorithm for solving the concave
minimization problem. We show that the algorithm converges to a rigorous optimal
solution, and besides that it generates a high quality heuristic solution if it is forced
to terminate in the early stage of iterations. In other words, the proposed algorithm
can be used in two ways, as an exact algorithm and as a heuristic tool. In the next
section, we will explain the basic workings of the usual simplicial algorithm, which
provides a framework for our algorithm. In Section 3, we will make necessary changes
and improvements to this algorithm in such a way as (i) to save efforts in the bounding2

operation, (ii) to strengthen the upper bound (incumbent value), not the lower bound,and (iii) to preserve the convergence property. In Section 4, we will present a detailed
description of the algorithm incorporating these three devices and a convergence proof.
In Section 5, we will report some numerical results of a comparison of the algorithm withan existing one, and show the performance as a heuristic tool. Lastly, we will summarize
the paper in Section 6, with some concluding remarks.

2

Simplicial algorithm for concave minimization

Let f be a concave function defined on an open subset of Rn including a polyhedron:
D = {x ∈ Rn | Ax = b, x ≥ 0},
where A ∈ Rm×n and b ∈ Rm . The problem considered in this paper is a minimizationof f over D, i.e.,
minimize f (x)(1)
subject to x ∈ D.
We assume that f is continuously differentiable, D is nonempty and bounded. Therefore,(1) has a globally optimal solution among veritces of D, though many of those are just
locally optimal.
One of the most popular methods for locating a globally optimal solution is thesimplicial branch-and-bound algorithm, originally proposed in [4]. In this algorithm, wefirst define an n-simplex ∆1 including D. The domain of f is assumed to be large enoughto include this simplex. Let v11 , . . . , v1n+1 denote the vertices of ∆1 . Then we have
∆1 = conv({v11 , . . . , v1n+1 }) ≡ x ∈ Rn | x = V1 λ, eT λ = 1, λ ≥ 0 ,where V1 = [v11 , . . . , v1n+1 ], and e ∈ Rn+1 is the all-ones vector. As subdividing ∆1 into
smaller simplices {∆k | k ∈ K} such that[∆k = ∆ 1 ,int(∆r ) ∩ int(∆s ) = ∅,r 6= s,k∈K

we compute a lower bound w(∆k ) of f on D ∩ ∆k for each k ∈ K, where int( · ) denotes
the set of interior points. We will discuss how to compute w(∆k ) later in detail.
e ∈ D is given. If f (eSuppose a feasible solution xx) ≤ w(∆k ), then we see that nox ∈ D ∩ ∆k satisfies f (x) < f (ex). Therefore, if f (ex) ≤ w(∆k ) for every k ∈ K, we
e is a globally optimal solution. If not, we subdivide ∆k for somecan conclude that x
appropriate k ∈ K further into smaller simplices and replace ∆k by those. The algorithm
is outlined as follows:3

ePrototype of the simplicial algorithm. Compute a lower bound w(∆1 ) and let x
be a feasible solution found in the process. Let L := {∆1 }, k := 1, and repeat Steps 1–3.
Step 1 (subproblem selection) Take a simplex ∆k with the least value of w from L.
Step 2 (bounding operation) If f (ex) ≤ w(∆k ), then terminate. Otherwise, go to Step 3.
Step 3 (branching operation) Subdivide ∆k into two subsimplices ∆1 and ∆2 . Computee if possible. Add ∆1 and ∆2 to L.
w(∆1 ) and w(∆2 ) and update the incumbent x
Let k := k + 1.
e isWhen there is no ∆ with w(∆) < f (ex) in the list L, the current incumbent x
a globally optimal solution of (1). In general, however, it does not happen, and thealgorithm would generate an infinite nested sequence {∆kq | q = 1, 2, . . . } such that∆k 1 ⊃ ∆ k 2 ⊃ · · · ,

(2)

T
kq
where ∆kq denotes the simplex selected at Step 1 of the kq th iteration. If ∞is
q=1 ∆a singleton for every infinite nested sequence, the algorithm is guaranteed to be convergent. The only known subdivision rule with such exhaustiveness is bisection. Let∆k = conv({vk1 , . . . , vkn+1 }). At Step 3, we may select the longest edge, say [vkr , vks ], anddivide it at a fixed ratio of α ∈ (0, 1/2]. Letting v = (1 − α)vkr + αvks , we have
∆1 = conv({vki | i 6= r} ∪ {v}),∆2 = conv({vki | i 6= s} ∪ {v}).

Another well-known subdivision rule is ω-subdivision, which subdivides ∆k radiallyinto n + 1 subsimplices and has no exhaustiveness property. It has been noted for a longtime that ω-subdivision is practically more efficient than bisection, but the convergence
was a theoretical open question until 2000 (see [8, 13] for more details).

3

Linear relaxation and local search

In the usual simplicial branch-and-bound algorithm, the lower bound w(∆) of f on D∩∆
is computed by minimizing a convex envelope g of f on ∆, which is a maximal convex
function underestimating f on ∆. In our case where f is concave, g is an affine function,
which agrees with f at the n + 1 vertices v1 , . . . , vn+1 of ∆. By noting that each x ∈ ∆can be written as x = Vλ for some λ ≥ 0 such that eT λ = 1, we have the value of g atx ∈ ∆ as follows
n+1Xg(x) =
λi f (vi ).
i=1

4

Thereby, w(∆) is given as the optimal value of a linear program:
minimize
Q(∆)

n+1
X

λi f (vi )i=1subject to AVλ = b, Vλ ≥ 0eT λ = 1, λ ≥ 0,

which is a linear relaxation of a subproblem of (1):P(∆)

minimize f (x)subject to x ∈ D ∩ ∆.

Although Q(∆) yields a fairly tight lower bound of P(∆) and ∆ ∈ L might be fathomed at an early iteration of the algorithm, our purpose is not necessarily to accelerate
the convergence but to obtain a better feasible solution in a smaller amount of time.
We will therefore try to simplify the relaxation of P(∆). This leads to a deterioration in
the lower bound of P(∆), but has some redeeming merits, especially when the simplicial
algorithm is used as a heuristic tool.

3.1

Simplified linear relaxation

Let us denote the centroid of ∆ by u =Pn+1

i=1 vi /(n + 1) and define

h(x) = ∇f (u)x + δ,
where
δ = min{f (x) − ∇f (u)x | x ∈ ∆}.

(3)

Note that the right-hand side of (3) is a concave minimization, but the feasible set ∆has only n + 1 vertices, at least one of which gives δ. Let us replace f by h in P(∆) andfurther drop the constraint x ∈ ∆. Then we have another linear relaxation of P(∆):R(∆)

minimize ∇f (u)x + δ
subject to Ax = b, x ≥ 0.

Let z(∆), wQ (∆) and wR (∆) denote the optimal value of P(∆), Q(∆) and R(∆), respectively. The former two values are considered to be +∞ if D ∩ ∆ = ∅.
Lemma 3.1. Among z(∆), wQ (∆) and wR (∆) exists a relationship:wR (∆) ≤ wQ (∆) ≤ z(∆).

5(4)

Proof. By definition, both objective functions g and h of Q(∆) and R(∆) underestimate
f on ∆, but the former is a maximal underestimating function. Moreover, the feasible
set D ∩ ∆ of P(∆) and Q(∆) is a subset of the feasible set D of R(∆). Hence, therelationship (4) is a natural consequence.
In terms of bound tightness, our proposed relaxation R(∆) is inferior to the usualQ(∆), as shown in Lemma 3.1. However, R(∆) has the following advantages:(i) the objective function h is easy to obtain if gradient vectors of f are given analytically,(ii) the feasible set D remains unchanged regardless of the variation of ∆, and(iii) the structure of the target problem (1) is inherited to R(∆).
In the simplicial algorithm, we need to repeatedly solve the same type of relaxed problems. If we adopt R(∆) instead of Q(∆), this computational burden is reduced considerably because the optimal solution to the preceding relaxed problem is feasible for thecurrent R(∆). We could recover its optimality for R(∆) in a very few simplex pivots.
If the target problem (1) has some favorable structure as in minimum concave-cost network flow problems [6, 7, 12, 14], this burden would be further reduced. Certainly, if theconvex envelope g is represented explicitly as a function in x, we can give the properties(ii) and (iii) to Q(∆), just by dropping the constraint x ∈ ∆. Unfortunately, to obtain
the explicit form of g, we have to solve a linear system of size n + 1, and besides its
solution becomes numerically unstable as ∆ grows smaller [9, 10].

3.2

Improving of the incumbent by local search

The last property (iii) also means that any optimal basic solution x0 of R(∆) is a feasible
basic solution of the target problem (1) and might be a locally optimal solution. Even
if not, we can reach a better solution, by visiting some adjacent vertices of D from x 0 .
Let c = ∇f (x0 ) and consider a linear program associated with (1):minimize cx
subject to Ax = b, x ≥ 0.

(5)

Let B denote the basis of x0 , the index set of m basic variables in x0 , and let N ={1, . . . , n} \ B. Also denote by (AB , AN ), (cB , cN ) and (xB , xN ), respectively, the corresponding partitions of A, c and x. Then we have a feasible dictionary of (5):xB = b0 − A0N xN
z = cB b0 + (cN − cB A0N )xN ,
6

(6)

0
0
−1
0
0
0
where A0N = A−1
B AN and b = AB b. The basic solution x is given as (xB , xN ) = (b , 0)
via this dictionary.

Proposition 3.2. If cN − cB A0N > 0, then x0 is a locally optimal solution of (1).
Proof. Let x0 be an arbitrary point in D \ {x0 }. Then there exist a unit vector d and apositive number t such that x0 = x0 + td. Since (x0B , x0N ) = (b0 − tA0N dN , tdN ), we havef (x0 ) − f (x0 ) = ∇f (x0 )(x0 − x0 ) + kx0 − x0 kβ(t)= t[(cN − cB A0N )dN + β(t)],where β(t) ≤ 0 by the concavity of f and limt→0 β(t) = 0. If dN ≤ 0, then x0 6∈ D
or x0 = x0 . Therefore, we may assume that dN ≥ 0 and dN 6= 0. This implies(cN − cB A0N )dN > 0, and besides (cN − cB A0N )dN + β(t) ≥ 0 for sufficiently small t > 0.
Hence, we have f (x0 ) − f (x0 ) ≥ 0 if x0 is in some neighborhood of x0 .
Suppose in the dictionary (6) that for some s ∈ N we havecs − cB a0s < 0,(7)

where a0s denotes the corresponding column of A0N . Then we perform a simplex pivot insome appropriate row, say corresponding to an r ∈ B, of a 0s . Let x1 denote the resulting
feasible basic solution. Since f is concave, we have
 1
0
f (x1 ) − f (x0 ) ≤ ∇f (x0 )(x1 − x0 ) = cj − cB A−1
B aj (xs − xs ).

(8)

If the pivot is nondegenerate, i.e., x1s − x0s = x1s > 0, then (8), together with (7), implies
f (x1 ) < f (x0 ). After updating B = B ∪ {s} \ {r} and N = N ∪ {r} \ {s}, we again
replace c = ∇f (x0 ) by c = ∇f (x1 ), and perform a simplex pivot in the dictionary (6)with respect to the new (B, N ) if possible. Continuing this process with the help of somecycling prevention rule for the simplex method (see e.g., [1]), we have a finite sequenceof feasible basic solutions {x` | ` = 0, 1, . . . , p} such thatf (x0 ) ≥ f (x1 ) ≥ · · · ≥ f (xp ),and the following holds in the dictionary (6) with c = ∇f (xp ):cN − cB A0N ≥ 0.

(9)

If the inequality holds strictly in (9), then Proposition 3.2 guarantees the local optimality
e with xp , except when all the pivotsof xp . Even if not, we could improve the incumbent x
are degenerate.
7

4

Convergence and heuristic application

Let K be a predetermined number of iterations and  ≥ 0 a tolerance for the value off . Our proposed simplicial branch-and-bound algorithm is described as follows:algorithm simplicial bb
begin
compute an n-simplex ∆1 = conv({v11 , . . . , v1n+1 }) including D;
let δ 1 := min{f (x) − ∇f (u1 )x | x ∈ ∆} for the centroid u1 of ∆1 ;solve R(∆1 ) of minimizing h1 (x) := ∇f (u1 )x + δ 1 and obtain wR (∆1 );let x1 denote the feasible basic solution satisfying h1 (x1 ) = wR (∆1 );e1 := local search(x1 ); ze1 := f (ex1 ); L := {∆}; k := 1;xwhile k ≤ K do begin/ ∗ Step 1 ∗ /select a simplex ∆k = conv({vk1 , · · · , vkn+1 }) with the least value of wR from L;
let hk (x) = ∇f (uk )x + δ k denote the objective function of R(∆k );let xk denote the feasible basic solution satisfying hk (xk ) = wR (∆k ); / ∗ Step 2 ∗ /if zek − wR (∆k ) ≤  then k := K + 1
else begin
subdivide ∆k into ∆1 and ∆2 according to the bisection rule; / ∗ Step 3 ∗ /for i = 1, 2 do begin
let δ := min{f (x) − ∇f (u)x | x ∈ ∆i } for the centroid u of ∆i ;solve R(∆i ) of minimizing h(x) := ∇f (u)x + δ and obtain wR (∆i );let xi denote the feasible basic solution satisfying h(xi ) = wR (∆i );ei := local search(xi )xend;
L := L ∪ {∆1 , ∆2 }end;
ek+1 ∈ arg min{f (x) | x = x
e1 , xe2 , xek } and let zek+1 := f (eselect x
xk+1 );
L := L \ {∆k }; k := k + 1
end;output (exk , zek )end;function local search(x)begin
let B denote the basis for x and N := {1, . . . , , n} \ B;let (cB , cN ) and (AB , AN ) denote the partitions of c := ∇f (x) and A;
0−1
A0N := A−1
B AN ; b := AB b;
while cN − cB A0N ≥ 0 does not hold do begin

8

select a column a0s of A0N such that cs − cB a0s < 0;
perform a pivot in an appropriate row of a0s , corresponding to an r ∈ B;
B := B ∪ {s} \ {r}; N := N ∪ {r} \ {t};update (cB , cN ), (AB , AN ), A0N and b0 according to the new (B, N );Let x denote the basic solution with (xB , xN ) = (b0 , 0) and let c := ∇f (x)end;return x
end;

4.1

Convergence proof

If K = +∞ and  = 0, the algorithm simplicial bb does not terminate in general andgenerates an infinite nested sequence {∆kq | q = 1, 2, . . . } as in (2), like the usual
simplicial algorithm with the bisection rule. However, we can show that the difference
between the incumbent value zekq and the lower bound wR (∆kq ) diminishes to zero ina subsequence of {∆kq | q = 1, 2, . . . }. This leads to the convergence of the algorithm
simplicial bb.
Lemma 4.1. Let {∆k | k ∈ K} be any infinite nested sequence of simplices generated
by the algorithm simplicial bb. Then there exists a subsequence {k 1 , k2 , . . . } ⊂ K such
that


(10)
lim zekq − wR (∆kq ) = 0.
q→∞

Proof. For every q = 1, 2, . . . , we can assumef (xkq ) ≥ zekq > wR (∆kq ) = ∇f (ukq )xkq + δ kq .

(11)

Let vkq denote the vertex of ∆kq defining δ kq . Then we haveδ kq = f (vkq ) − ∇f (ukq )vkq .
T
Recall that we adopt the bisection rule and have {v} = k∈K ∆k . Then ukq → v andvkq → v as q → +∞, because ukq and vkq are points in ∆kq . By the continuity of f and∇f , as q → +∞, we have∇f (vkq ) → ∇f (v),δ kq → f (v) − ∇f (v)v.

We can also assume xkq → x ∈ D as q → +∞, because xk ’s are generated in thecompact set D. Therefore, as q → +∞, we havewR (∆kq ) → ∇f (v)(x − v) + f (v) ≥ f (x),9by noting the concavity of f . This, together with (11), implies (10).
Theorem 4.2. Suppose K = +∞ and  = 0. If the algorithm simplicial bb terminates at
e k is a globally optimal solution of (1). If not, every accumulation
the kth iteration, then x
point of the sequence {exk | k = 1, 2, . . . } is a globally optimal solution.
Proof. If simplicial bb terminates, the assertion is obvious. Let us assume that it does
not terminate. Then simplicial bb generates at least one infinite nested sequence {∆ k |k ∈ K} satisfying (10) for some subsequence {k1 , k2 , . . . } ⊂ K. Let ze = limq→∞ zekq andassume, to the contrary, that ze > f (x0 ) for some x0 ∈ D. For every q = 1, 2, . . . , thispoint x0 belongs to some ∆ ∈ L and we havezekq > f (x0 ) ≥ wR (∆) ≥ wR (∆kq ),because ∆kq is selected as a simplex with the least value of wR at iteration kq . However,zekq − wR (∆kq ) → 0 as q → +∞, which is a contradiction. Therefore, we haveze ≤ f (x),∀x ∈ D.

e be any accumulation point of {eLet xxk | k = 1, 2, . . . } and assume that {ex kr | r =e. Even in this subsequence, as r → +∞, we have
1, 2, . . . } converges to xf (exkr ) = zekr → ze,
e is a globally optimal solution to
because {ez k | k = 1, 2, . . . } is nonincreasing. Hence, x(1).
Corollary 4.3. If K < +∞ or  > 0, the algorithm simplicial bb terminates after finitely
many iterations. Especially when K = +∞ and  > 0, it yields a globally -optimal
ek of (1).
solution x

4.2

Application as heuristic tools

In order to use simplicial bb to solve (1) heuristically, we need only to set K to a finite
number. As will be seen in the next section, the algorithm requires few iterations andyields a feasible solution of almost the same value as an optimal solution in most cases.
Even for a rather small K, we could expect feasible solutions of enough accuracy inactual applications. This is mainly due to the fact that local search works well after
solving R(∆) as a heuristic tool. In fact, the algorithm simplicial bb can be thought ofas a kind of multistart algorithm where the starting points are generated systematicallyby branch-and-bound. The centroids uk ’s of all simplices ∆k ∈ L serve as those starting
points.
10

If we select uk ’s randomly from the initial simplex ∆1 , as in the genuine multistartalgorithm, we can obtain a complete heuristic algorithm for (1). It is described simply
as follows:algorithm simplicial ms
begin
compute an n-simplex ∆1 = conv({v11 , . . . , v1n+1 }) including D;
δ := 0;for k = 1, . . . , K do begin
select a point u randomly from ∆1 and let h(x) := ∇f (u)x;solve R(∆1 ) of minimizing h(x) and obtain its optimal basic solution xk ;ek := local search(xk )xend;e ∈ arg min{f (x) | x = x
e1 , . . . , x
eK } and let ze := f (eselect xx);
output (ex, ze)
end;
Note in this description that we may ignore the constant δ in the objective function hof R(∆1 ) because we do not need lower bounds of f any more. In other words, R(∆1 )is solved just to provide a feasible basic solution for the function local search.

5

Numerical results

In this section, we will report some numerical results of having compared the algorithms
simplicial bb, simplicial ms and an ordinary simplicial branch-and-bound algorithm withbisection, referred to as textbook bb. The test problem was a concave quadratic minimization problem of the form:
minimize f (x) + ωdy y
subject to Ax + By ≤ b, (x, y) ≥ 0,
where

(12)

1
f (x) = xT Cx + dx x,
2and A ∈ Rm×p , B ∈ Rm×q , b ∈ Rm , C ∈ Rp×p , dTx ∈ Rp , dTy ∈ Rq , and ω is a positive
weight. The total number of variables is n = p + q + m, including m slack variables. The
matrix C = [cij ] was symmetric and tridiagonal, i.e., c11 = cii = −1.0, and ci,i−1 = ci−1,iwas a uniformly random number in the interval [−1.0, 0.0] for i = 2, . . . , p. Also, eachcomponent of (dx , dy ) was drawn randomly from the uniform distribution on [−1, 0, 0.0].
To make the feasible set bounded, b was set to [1, . . . , 1, p + q]T and all components in
11

simplicial_bb
textbook_bb-5

incumbent value

-5.5

-6

-6.5

1

2

10

100
log( # iterations)

1000

10000

29353

Figure 2: Changes in the incumbent value in the proposed algorithm.

the last row of [A, B] were fixed at ones. Other components were all random numbers in
the interval [−0.5, 1.0], where the percentages of zeros and negative numbers were about
20% and 10%, respectively.
Computer codes of simplicial bb, simplicial ms and textbook bb were written using
GNU Octave (version 2.1.73), a MATLAB-like computational tool [15], and run on asingle-processor workstation (Athlon64, 2.4GHz). Notice on the problem (12) that thenonlinear function f depends only on x ∈ Rp . Therefore, using the decomposition
technique [8, 18], we defined the initial simplex ∆1 so as to include the projection of
the feasible set onto the space Rp of x, and carried out essential operations related tosubsimplices ∆’s in Rp , in each code. As for the optimality criterion in simplicial bb andtextbook bb, we adopted zek − wR (∆k ) ≤ |ez k |, instead of zek − wR (∆k ) ≤ , to prevent themagnitude of zek from affecting the convergence, where  was fixed at 10−5 . Incidentally,
the example in Section 1 is an instance of (12) with (m, n, p, ω) = (40, 100, 20, 3.0), andif simplicial bb is applied to it, the incumbent value changes as in Figure 2.
First, let us see the performance of simplicial ms as an exact algorithm on small-scaleinstances with (m, n) = (40, 120). Figures 3 and 4 show the variation in the average
number of iterations and average computational time in seconds, respectively, requiredby simplicial bb and textbook bb to solve ten instances when p was fixed at 16 and ω
ranged from 1.0 to 10.0. Figures 5 and 6 show it when ω was fixed at 3.0 and p ranged
from 8 to 22. We see from these figures that simplicial bb takes considerably moreiterations than textbook bb while there is not so much difference in the computational

12

100000

simplicial_bb
textbook_bblog( # iterations )

10000

1000

100

10

1
1

2

2.5

3

4

5
Weight (ω)

7.5

10

Figure 3: The numbers of iterations when (m, n, p) = (40, 120, 16).

1000

simplicial_bb
textbook_bblog( CPU seconds )

100

10

1

0.1
1

2

2.5

3

4

5
Weight (ω)

7.5

Figure 4: Computational time (seconds) when (m, n, p) = (40, 120, 16).

13

10

100000

simplicial_bb
textbook_bblog( # iterations )

10000

1000

100

10

1
8

10

12

14

16

18

20

22

# nonlinear variables (p)Figure 5: The numbers of iterations when (m, n, ω) = (40, 120, 3.0).

1000

simplicial_bb
textbook_bblog( CPU seconds )

100

10

1

0.1
8

10

12

14
16
# nonlinear variables (p)18

20

Figure 6: Computational time (seconds) when (m, n, ω) = (40, 120, 3.0).

14

22

Table 1: Performance for 32 iterations of simplicial bb and simplicial ms.
m
100

n
ω
300 1.0200

600 1.0200

600 3.0300

900 1.0300

900 3.0400 1,200 3.0

bb
ms
bb
ms
bb
ms
bb
ms
bb
ms
bb
ms

p = n/6
pivot
time
4810.9 5.1314
4877.3 4.471
7995.1 30.23
8126.2 28.52
3326.1 12.44
3254.1 11.42
14408
115.4
15216
115.3
7937.4 63.34
8335.4 63.89
15800
209.2
15171
191.4

p = n/3
pivot time5923.5 6.293
6083.8 5.552
11677 45.09
12115 43.58
4356.4 16.33
4422.2 15.42
21634 173.5
21379 164.7
10962 87.60
11055 83.41
20224 267.7
20484 258.8

p = n/2
pivot time
5151.7 5.736
5534.6 5.320
15906 63.73
15157 56.55
5219.0 19.83
5207.0 18.17
27147 222.9
27045 214.6
13027 104.6
12895 97.38
22856 302.5
22842 288.8

time. This dominance relation is reversed when ω is less than about 3.0. In fact, theaverage computational time of textbook bb was well over 2, 000 seconds for problem
instances with ω ≤ 2.0. Once ω is fixed, however, both codes behaves alike, as shown in
Figure 6. As a whole, the algorithm simplicial bb appears to have potential for efficiency,
at least comparable to the usual simplicial branch-and-bound algorithm.
Let us turn next to the performance of simplicial bb as a heuristic algorithm. We fixed
the number K of iterations at 32 in simplicial bb, simplicial ms, and solved instances of size
up to (m, n, p) = (400, 1200, 600), using both codes. Table 1 lists the average number ofsimplex pivots (pivot) and average computational time in seconds (time) required by simplicial bb (bb) and simplicial ms (ms) to solve ten instances. Both codes carry out almost
the same number of pivoting operations, but simplicial bb takes a little more computational time because of additional operations involved in branch-and-bound. To investigate the quality of solutions, we extract some outputs (for instances #1 and #2) of bothcodes and list them in Table 2, which includes the incumbent value (output) and lower
bound (bound) at termination, and the iteration number at which the incumbent waslast updated (update). For problem instances of size (m, n, p, w) = (200, 600, 100, 3.0)
and (300, 900, 150, 3.0), we also add the optimal values, which were computed using acode of the algorithm developed in [9]. We observed for every instance of these two sizes
that both simplicial bb and simplicial ms generated a feasible solution of the same value
as an optimal solution. Unfortunately, each instance of the other sizes is too large tosolve to optimality using our available computer codes. However, simplicial bb always
15

Table 2: Outputs after 32 iterations of simplicial bb and simplicial ms.
m
200

n
p
ω
600 100 3.0 #1

opt.val.
-7.441762#2-7.844702

900 150 3.0 #1-7.708254#2-7.689507

900 450 1.0 #1

—

#2

—

900 450 3.0 #1

—

#2

—

400 1,200 600 3.0 #1

—

#2

—

300

300

300

bb
ms
bb
ms
bb
ms
bb
ms
bb
ms
bb
ms
bb
ms
bb
ms
bb
ms
bb
ms

output-7.441762-7.441762-7.844702-7.844702-7.708254-7.708254-7.689507-7.689507-2.704720-2.704726-2.681544-2.681603-6.355546-6.355546-6.567183-6.567183-6.996379-6.996379-6.982920-6.982920

bound
update-11.550959
1—
31-11.819086
1—
1-11.948366
1—
1-11.776019
1—
1-7.620925
21—
10-7.643540
27—
25-11.316951
1—
1-11.560518
2—
13-11.794577
1—
1-11.796606
1—
1

maintains the lower bound, which provides an indication, though rough, of the accuracyof outputs. Namely, we see from Table 2 that the ratio of the output value of simplicial bb to the optimal value is greater than 0.35 when ω = 1.0 and it rises to greaterthan 0.6 when ω = 3.0. This is an important strength of simplicial bb, not shared byother heuristic algorithms.

6

Conclusion

To enhance the computational efficiency of the branch-and-bound algorithm, various
techniques of tightening the lower bound have been developed so far. In contrast to
those, we have loosened it, and instead tightened the upper bound in this paper. As aresult, we have shown that good feasible solutions are obtained in the quite early stageof iterations and the algorithm can be used as a heuristic tool as well. The algorithm

16simplicial bb is our answer to the present situation where none can ask for theoreticallyefficient algorithms for the concave minimization problem. However, it is not a final
one because there remain two substantive issues to be improved in simplicial bb. First,
its computational efficiency still pales in comparison with other exact algorithms. To
put simplicial bb into practical use as an exact algorithm, we need to incorporate someprocedures of tightening the lower bound, such as a Lagrangian-based one in [9, 10, 12].
The other issue is memory consumption of the implementation. Since simplicial bb storesan exponential number of ∆k ’s in the worst case, it may suffer from a combinatorial
explosion in memory consumption, before yielding a solution, if we try to solve a large
scale instance to optimality. This is a critical issue shared by many branch-and-boundalgorithms for the concave minimization problem. The reverse search technique in [11]
could be a hint towards a possible resolution.

References[1] Chvátal, V., Linear Programming, Freeman (N.Y., 1983).
[2] Karmarkar, N., “A new polynomial-time algorithm for linear programming”, Combinatorica 4 (1984), 373–395.
[3] McMullen, P., “The maximum numbers of faces of a convex polytope”, Mathematika
17 (1970), 179–184.
[4] Horst, R., “An algorithm for nonconvex programming problems”, Mathematical
Programming 10 (1976), 312–321.
[5] Horst, R., P.M. Pardalos, and N.V. Thoai, Introduction to Global Optimization,
Springer-Verlag (Berlin, 1995).
[6] Guisewite, G.M., and P.M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity, and algorithms”, Annals of Operations Research 25(1990), 75–100.
[7] Holmberg, K., and H. Tuy, “A production-transportation problem with stochastic
demand and concave production costs”, Mathematical Programming 85 (1999), 157–
179.
[8] Horst, R. and H. Tuy, Global Optimization: Deterministic Approaches, 2nd ed.,Springer-Verlag (Berlin, 1993).
[9] Kuno, T., and H. Nagai, “A simplicial algorithm with two-phase bounding operation
for a class of concave minimization problems”, Pacific Journal of Optimization 1(2005), 277–296.

17[10] Kuno, T., and H. Nagai, “A simplicial branch-and-bound algorithm conscious of
special structures in concave minimization problems”, CS Technical Report 052 (University of Tsukuba, 2005), to appear in Computational Optimization andApplications.
[11] Kuno, T., and Y. Shiguro, “A polynomial-space finite algorithm for solving a classof reverse convex programs”, CS Technical Report 07-8 (University of Tsukuba,2007).
[12] Kuno, T., and T. Utsunomiya, “A Lagrangian based branch-and-bound algorithm
for production-transportation problems”, Journal of Global Optimization 18 (2000),
59–73.
[13] Locatelli, M., and U. Raber, “On convergence of the simplicial branch-and-boundalgorithm based on ω-subdivisions”, Journal of Optimization Theory and Applications 107 (2000), 69–79.
[14] Nagai, H., and T. Kuno, “A simplicial branch-and-bound algorithm for productiontransportation problems with inseparable concave production cost”, Journal of the
Operations Research Society of Japan 48 (2005), 90–110.
[15] Octave Home Page, http://www.octave.org/.
[16] Vavasis, S.A., Nonlinear Optimization: Complexity Issues, Oxford University Press(Oxford, 1991).
[17] Tuy, H., “Concave programming under linear constraints”, Soviet Mathematics 5(1964), 1437–1440.
[18] Tuy, H., Convex Analysis and Global Optimization, Kluwer Academic Publishers(Dordrecht, 1998).

18