1. Introduction
Integer programming problems occur in many real-life situations: production planning, scheduling, telecommunication networks, cargo loading, vehicle routing, and inventory maintenance, for example. There are numerous commercial software packages available for solving integer programming problems, such as CPLEX, Gurobi, KNITRO, and LINDO. There are also many open-source programs available. However, since the integer programming problem, in general, is NP-complete [1], it is very difficult to obtain a global optimum, and so, at best, a local optimum is generally found. For the case in which all of the decision variables are continuous, a sufficient condition for any local minimum to be a global minimum is that the Hessian matrix be positive definite [2]. If the objective function has two variables, one of which is integer and the other continuous, sufficient conditions for any local minimum to be a global minimum can be found in [3]. If the objective function has two integer variables, we give below sufficient conditions for any local minimum to be a global minimum. The function need not be integer convex for this condition to hold.
2. Two Integer Variables
Definition 1: Let
be a real mapping from the integers into the real line. The first difference of
is denoted by
and is defined as follows:
Second and subsequent difference of
are defined by
Definition 2: A function
,
is integer strictly convex if
is a strictly increasing function of z, that is, if
.
Definition 3: The function
has a local minimum at
if
and
.
Definition 4: The function
has a global minimum at
if
for all z. Ponstein [4] considers
to be a real, continuous, and differentiable scalar function with continuous first partial derivatives, of the vector X, which is contained in a convex region R of n-dimensional Euclidean space. He then defines a function to be strictly quasi-convex if
Kumin [3] extended this definition to give.
Definition 5: A function
is integer strictly quasi-convex if for any two points
and
we have the following:
Case I:
implies
for
.
Case II:
implies
for
.
Ponstein [4] also showed that any local minimum of a strictly quasi convex function is also a global minimum, and Kumin [3] extended his result to show that any local minimum of an integer strictly quasi convex function is also a global minimum.
Now consider a function
where
. Also, define
where
.
Theorem 1: Assume that
is integer strictly quasi-convex in w for all k and that
is integer strictly quasi-convex in k. Then, any local minimum of
is also a global minimum.
Proof: Let
be a local minimum of
and suppose it is not a global minimum. Then there exists a
such that
Now, since
is strictly integer quasi-convex in w for all k
. Thus,
Assume
. The proof follows similarly if
. From Definition 5, since
is integer strictly quasi convex, then
for
. In particular, for
we have
. But this contradicts the assumption that
is a local minimum.
Yüceer [5] defines a function to be discretely convex as follows: Let S be a subspace of a discrete n-dimensional space. A function
is defined to be discrete convex, if for all
, and
, we have
where
and
,
and
He then considers the following example
where
Yüceer then shows that
is not discretely convex. Below, we show that any local minimum of f is also a global minimum although it is not a discretely convex function.
We first show that
is integer strictly quasi-convex in
. According to Definition 2,
is integer strictly convex in
.
Extending Ponstein’s definitions to functions with an integer variable implies that
is also integer strictly quasi convex in
since it is strictly integer convex. Now consider
.
will be a local minimum of
if
and
.
For this function:
If i is odd, then
is an even integer which is divisible by 2. If i is even, then
is an odd integer and not divisible by 2. Thus,
and
where
. Then
where
.
Using Definition 3, and by comparing the values of
and
we find that
is a local minimum of
.
Thus,
We now verify that
satisfies Definition 5. Assume that i is an odd integer.
1) For any
,
. Now, since
we have two conditions to consider:
or 0,
.
If
and
, then for
, we have
which satisfies Case I of Definition 5. If
and
, k can be either positive or negative. If
, then for
we have
which satisfies Case I of Definition 5.
If
then
. So for
we have
since
which also satisfies Case I of Definition 5.
2) For any
,
and
. So, for
, we have
which satisfies Case 2 of Definition 5. The proof follows similarly if i is an even integer.
1) and 2) show that
satisfies the condition of Definition 5, hence it is a strictly integer quasi-convex function. Thus, according to Theorem 1, any local minimum of
is a global minimum.
3. Conclusion
A sufficient condition is developed for functions of two integer variables such that any local minimum is also a global minimum. This result is important because many optimization problems in integer programming do not have integer convex functions, but still may satisfy this condition.