Optimization over Integers with Robustness in Cost and Few
Constraints
Kai-Simon Goetzmann
1
?
, Sebastian Stiller
2
??
, and Claudio Telha
3
1
goetzman@math.tu-berlin.de
, Institut fur Mathematik, Technische Universitat Berlin
2
, Sloan School of Management, Massachusetts Institute of Technology
3
, Operations Research Center, Massachusetts Institute of Technology
Abstract.
Robust optimization is an approach for optimization under uncertainty that has recently
attracted attention both from theory and practitioners. While there is an elaborate and powerful
machinery for continuous robust optimization problems, results on robust combinatorial optimization
and robust linear integer programs are still rare and hardly general. In a seminal paper Bertsimas
and Sim [7] show that for an arbitrary, linear 0-1-problem, over which one can optimize, one can
also optimize the cost-robust counterpart. They explicitly note that this method is conned to binary
problems. We present a result of this type for general integer programs. Further, we extend the result
to integer programs with uncertainty in one constraint.
We show that one can optimize a not necessarily binary,
cost
robust problem, for which one can optimize
a slightly modied version of the deterministic problem. Further, in case there is a
{approximation
for the modied deterministic problem, we give a method for the cost robust counterpart to attain a
(
+
"
){approximation (for minimization problems; for maximization we get a 2
{approximation), or
again a
{approximation in a slightly more restricted case.
We further show that general integer linear programs where a single or few
constraints
are subject
to uncertainty can be solved, in case the problem can be solved for constraints on piecewise linear
functions. In case the programs are again binary, it suces to solve the underlying non-robust program
n
+ 1 times.
To demonstrate the progress achieved by our general techniques for non-binary integer programs,
we apply them to two classes of integer programs, namely, totally unimodular integer programs and
integer programs with two variables per inequality. We also exemplify the power of our approach for
combinatorial optimization problems. Here the method yields polynomial time approximations and
pseudopolynomial, exact algorithms for Unbounded Knapsack Problems. We derive an algorithm for
problems with both cost and constraint robustness.
As the general results of this paper could be applied so broadly and quickly already here, we believe
they will also be a fruitful method for future research in robust optimization over integers.
?
Supported by the Deutsche Forschungsgemeinschaft within the research training group `Methods for Discrete
Structures' (GRK 1408).
??
Marie-Curie Fellow of the European Commission under the ROSES-Project (FP7-PEOPLE-2009-IOF 254402).
1 Introduction
A solution to an optimization problem often has to be good not just for one instance but for a set of
scenarios. This can either be due to uncertainty as to which of the scenarios will eventually occur, or because
the solution shall be used several times in dierent scenarios.
One solution concept for optimization over scenarios is Robust Optimization. In the robust paradigm
feasibility and cost of a solution is measured by those scenarios in which the solution performs worst. This
worst case approach contrasts to stochastic programming, where the cost of a solution is typically a weighted
average over all scenarios, good ones and bad ones.
As an illustration, suppose we choose a route for regularly driving to work. It makes sense to use some
type of average as a measure for fuel consumption in this case. But as far as safety is concerned, one will
consider each route according to the risk in its worst case scenario.
Robust optimization has thriven in the past decade, partly because its applicability became apparent,
partly because the resulting mathematical models allow for strong solution methods. For continuous problems
a cohesive body of quite general methods has been developed. For combinatorial problems and integer linear
programs the picture is a lot more scattered. Typically, the results cover a specic combinatorial problem.
This is of course a consequence of the richness of combinatorial optimization and integer linear programming.
General results for all of these problems as in the continuous case are unlikely. Therefore the following result
by Bertsimas and Sim is even more remarkable:
In [7], they show that
{
for uncertain cost coecients, where at most
of them can deviate from the nominal setting at the
same time, solvability or approximability of any problem with binary decision variables extends to the
robust case, as it suces to solve a linear number of instances of the deterministic problem.
Unfortunately, this result is intrinsically limited to binary variables. We give a corresponding result for
integer, not-necessarily binary cost robust programs. Further, we can extend our method to general robust
integer programs with uncertainty in one (or few) constraint(s). Restricting this result again to binary
problems gives the exact sibling of the cost robust result in [7] for robustness in constraints.
Our Contribution:
The main results of this paper are the following:
{
The cost robust counterpart (in the same sense as in [7]) of an integer problem can be solved or approx-
imated if the original problem can be solved for piecewise linear convex cost functions with at most two
bends.
{
To solve integer problems with uncertainty in a constant number of linear constraints, one has to solve
a modied problem where the left hand sides of the constraints are replaced by piecewise linear convex
functions.
{
For
binary
problems with uncertainty in a constant number of linear constraints, it suces to solve a
polynomial number of instances of the original problem with slightly modied coecients in the con-
straints.
These general results allow us to develop methods for cost robust counterparts of entire classes of integer
linear programs, notably, totally unimodular programs (TUM) and integer programs with two variables per
constraint (IP2). Both classes have been studied intensely in the deterministic case, but we are not aware of
any general results on their robust counterparts. Our general result on cost robust TUM problems broadly
extends results on Robust Min Cost Flows in [7]. Further, we apply our general results to a combinatorial
problem, namely, Unbounded Knapsack. In this case we derive an algorithm that handles cost robustness
and robustness in the constraints at the same time.
Our result on integer programs with uncertainty in the constraints is limited to a constant number of
disturbed constraints. A path breaking work [8] on robust linear programs (and other continuous optimization
classes) gives a method to
solve
robust LPs where potentially every constraints is subject to disturbances.
This paper [8] has established the role of
scenario sets in robust optimization, i.e., the set of all scenarios
where each input parameter can vary in its own interval, but the absolute, normalized sum of all variations is
limited by a constant
. The major part of [8] is devoted to show that these sets imply a good probability for
a robust solutions to be feasible outside the assumed scenarios set. This result holds
only
for small, constant
numbers of constraints being subject to uncertainty. Also, primary examples in [8] feature uncertainty in one
constraint only. Hence, the loss in solvability for the integer case seems not very important, as already the
scenario sets are not well justied for the general case.
Often optimization problems with a natural, non-binary, integer linear programming description can be
reformulated as binary integer linear programs. Even granted the incurred blow-up of the instance, this does
usually not yield a workaround to apply results for robust binary IPs to the naturally non-binary problem.
The hindrance is usually that the scenarios sets of the robust counterparts make no sense once the problem
is transformed into an unnatural binary program.
Related Work:
To the best of our knowledge we give the rst results on cost robust counterparts of general
integer programs.
Modern continuous robust optimization started with [21] for convex uncertainty sets and [4,5,6] for
ellipsoidal uncertainty sets. Still a good overview for the state of the art is [1]. The
-scenario setting
from [7,8] has found frequent application. It has also been applied to certain covering problems in a two-
stage robust setting [10,15].
Robust Knapsack has so far only been considered in the binary setting. Yu [23] considered the Knapsack
Problem with general scenarios for uncertain costs and showed that unless the number of scenarios is constant,
the problem is strongly NP-hard. Aissi et al. [2] remarked that Yu's proof already shows that there is no
approximation algorithm for this problem at all. For
-scenarios, however, the result from [7] applies and gives
an FPTAS. Klopfenstein and Nace [16,17] considered polyhedral aspects of the robust Knapsack Problem,
and in the context of the chance-constraint version also a weight robust Knapsack Problem. For deterministic
Unbounded Knapsack Hochbaum [11] considered a non-linear extension of the problem with concave and
convex functions for the cost and weight of the items, respectively. This problem is similar to some of the
modied Knapsack problems we use.
Integer linear programs with two variables per inequalities and positive objective function coecients are a
generalization of the minimum weight vertex cover and the minimum weight 2-satisability problem (2SAT).
Hochbaum et al. [12] and Bar-Yehuda and Rawitz [3] provide a pseudopolynomial time 2-approximation algo-
rithm for this class of integer programs. In case the inequalities are restricted to be monotone, Hochbaum and
Naor [13] and Bar-Yehuda and Rawitz [3] provide a pseudopolynomial time exact algorithm. All algorithms
explicitly assume that the variables are bounded.
Our results for totally unimodular integer programs generalize results on specic totally unimodular
problems, e.g., Min Cost Flows [7].
Structure of the paper.
The remainder of this paper is organized as follows: In Section 2we present the general
results on cost robust integer problems, and apply them to problems with a total unimodular description
(Section 2.1) and Integer Programs with two variables per inequality (Section 2.2). Section 3is devoted to
the general result on constraint robustness, which is then applied, together with the results from Section 2,
to the Unbounded Knapsack Problem (Section 3.1).
2 Uncertainty in the Objective
We start with the general result on cost robust, not necessarily binary problems. We will use [
n
] for the set
f
1
;:::;n
g
and IN for the non-negative integers (including 0) here and throughout. By
T
(
A
) we denote the
running time of an algorithm
A
. The formal denition for the considered class of problems reads as follows:
Denition 1 (Cost Robust Optimization Problem).
For the optimization problems
min
x
2
X
f
c
T
x
g
and
max
x
2
X
f
c
T
x
g
, given by
P
= (
c;X
)
where
X
ZZ
n
and
c
2
IR
n
, and a non-negative integer vector
d
2
IN
n
together with
2
[
n
]
, the
minimization (maximization) (
d;
){Cost Robust Counterpart (CRC) of
P
is
dened by
min
x
2
X
8
>
<
>
:
c
T
x
+ max
S
[
n
]
j
S
j
X
j
2
S
j
d
j
x
j
j
9
>
=
>
;
and
max
x
2
X
8
>
<
>
:
c
T
x
max
S
[
n
]
j
S
j
X
j
2
S
j
d
j
x
j
j
9
>
=
>
;
;
(2.1)
respectively.
Our main goal is to show that one can solve or approximate the CRC of
P
, if one can solve or approximate
the following variant of
P
:
Denition 2 (Modied Optimization Problem).
For the minimization (maximization) problem given
by
P
= (
X;c
)
, a vector
c
0
2
IR
n
0
and a number
0
, the
(
c
0
;
){Modied Minimization (Maximization)
Problem (MMin, MMax) of
P
is
min
x
2
X
8
<
:
X
j
2
[
n
]
e
c
j
(
x
j
)
9
=
;
and
max
x
2
X
8
<
:
X
j
2
[
n
]
e
c
j
(
x
j
)
9
=
;
;
(2.2)
respectively, where
e
c
j
(
x
) :=
c
j
x
+ max
f
c
0
j
x
;
0
g
+ max
f
c
0
j
x
;
0
g
for minimization,
e
c
j
(
x
) :=
c
j
x
max
f
c
0
j
x
;
0
g
max
f
c
0
j
x
;
0
g
for maximization problems.
At this point minimization and maximization are fully symmetric. At a later stage it will come in handy to
have them dened separately.
Theorem 3.
Consider the optimization problem of
P
= (
c;X
)
with
X
ZZ
n
and
c
2
IR
n
. Suppose for some
1
there is a
{approximation algorithm
A
1
for the
(
c
0
;
)
{MMin (MMax) of
P
and arbitrary
c
0
and
.
Further suppose, for given
d
2
IN
n
and
2
[
n
]
there is an algorithm
A
2
that computes upper bounds
u
j
on
the absolute value of each variable
x
j
in the optimal solution of the
(
d;
)
{CRC of
P
.
Then there is a
{approximation algorithm
A
for the
(
d;
)
{CRC of
P
with running time
T
(
A
)
2
O
T
(
A
2
) + max
j
f
u
j
d
j
g
T
(
A
1
)
.
Note that for
= 1, i.e., if we have an exact algorithm for the modied problem, we can solve the CRC
exactly.
Proof.
We only consider minimization problems, since we can transform any maximization problem into a
minimization problem by taking the negative of the costs. We formulate the inner maximization problem
of (2.1) as an integer program (IP). This IP is totally unimodular, thus we can substitute it by its dual
LP-relaxation. Then the CRC reads as follows:
8
>
>
>
>
<
>
>
>
>
:
min
c
T
x
+
#
+
P
j
2
[
n
]
(
y
j
+
z
j
)
s.t.
y
j
+
#
d
j
x
j
8
j
2
[
n
]
z
j
+
#
d
j
x
j
8
j
2
[
n
]
y;z;#
0
x
2
X :
(2.3)
In an optimum,
y
j
= max
f
d
j
x
j
#;
0
g
and
z
j
= max
f
d
j
x
j
#;
0
g
, so (2.3) is equivalent to
min
x
2
X;#
0
8
<
:
c
T
x
+
#
+
X
j
2
[
n
]
max
f
d
j
x
j
#;
0
g
+ max
f
d
j
x
j
#;
0
g
9
=
;
:
(2.4)
For a xed
#
, this is equivalent to the (
d
j
;#
){MMin of
P
. By the conditions of the Theorem, we can compute
a
-approximate solution to this problem.
In an optimum we have
j
x
j
j
u
j
, so if
#
max
j
u
j
d
j
=:
#
, for all
j
both maxima vanish. Hence, if we
increase
#
beyond this number, the objective value increases. Therefore
#
is an upper bound for the optimal
value of
#
.
Also, the optimal
#
is integral: Denote by
C
(
#
) :=
#
+ min
x
2
X
8
<
:
X
j
2
[
n
]
c
j
x
j
+ max
f
d
j
x
j
#;
0
g
+ max
f
d
j
x
j
#;
0
g
9
=
;
(2.5)
the optimal cost for a xed
#
. Since
x
and
d
are integral, this function is linear in
#
within each interval
[
k;k
+1]
;k
2
IN. In such an interval the local maximum is obtained for
#
=
k
or for
#
=
k
+1, and thus the
global maximum is obtained for some integral
#
.
We compute all corresponding
-approximate solutions and choose the best among them, resulting in the
claimed running time.
ut
Remark.
Our model of robustness limits to deviation in at most
cost coecients. The resulting inner
maximization problem, which we dualized in the previous proof, is totally unimodular. Therefore a standard
argument originating from [7] gives that this model is equivalent to protecting against any cost function
c
+
d
with
in the set
f
2
IR
n
:
P
j
2
[
n
]
j
j
j
g
.
Unless max
j
u
j
d
j
is polynomial in the input, in Theorem 3one ends up with a pseudopolynomial algorithm
for the CRC, even if one has a polynomial algorithm for the modied optimization problem. This can be
overcome if
= 1 and
C
as dened in (2.5) is convex as a function of
#
, in which case the correct
#
can
be found via a carefully constructed binary search (similar to the one in proof of Theorem 7 in [7]).
Theorem 4.
Consider the minimization problem of
P
= (
c;X
)
with
X
IN
n
and
c
2
IR
n
0
. Under the
conditions of Theorem 3, if
= 1
and
C
is a convex function, then there is an exact algorithm
A
for the
(
d;
)
{CRC of
P
with running time
T
(
A
)
2 O
T
(
A
2
) + max
j
log(
u
j
d
j
)
T
(
A
1
)
.
For a detailed description of an application of this result we refer the reader to section 2.1.
When
>
1 or
C
is not convex, we can still restrict the number of calls of the oracle
A
1
to
O
(max
j
log(
u
j
d
j
))
in exchange for a slightly weaker approximation guarantee. But for this result we have to consider minimiza-
tion and maximization separately and restrict to combinatorial problems with non-negative cost coecients
and variables. Note that in this case the second maximum in both the denition of MMin and MMax vanishes.
Theorem 5 (Minimization Problem).
Consider the minimization problem of
P
= (
c;X
)
with
X
IN
n
and
c
2
IR
n
0
. Under the conditions of Theorem 3, for all
" >
0
there is a
(
+
"
)
{approximation algorithm
A
for the
(
d;
)
{CRC of
P
with running time
T
(
A
)
2 O
T
(
A
2
) +
1
"
max
j
log(
u
j
d
j
)
T
(
A
1
)
.
Proof.
We start as in the proof of Theorem 3. To attain the claimed running time, however, for any given
" >
0, we now solve (2.5) approximately for all
#
2 f
0
g[f
(1 +
"
)
k
:
k
2
IN
;
(1 +
"
)
k
1
#
g
, and return the
best of all these solutions. This yields a (
+
"
)-approximation for the CRC:
Denote the optimal value of
#
by
#
. In case
#
2 f
0
;
1
g
, our solution is within a factor of
of the
optimum, since these two values for
#
are checked. Otherwise, let
k
0
2
IN
r
f
0
g
be such that (1 +
"
)
k
0
1
<
#
(1 +
"
)
k
0
=:
#
0
:
Since
;#
;c
, and
x
0, we get
4
C
(
#
0
)
C
(
#
)
max
8
<
:
#
0
#
;
min
x
2
X
nP
j
c
j
x
j
+ max
f
d
j
x
j
#
0
;
0
g
o
min
x
2
X
nP
j
c
j
x
j
+ max
f
d
j
x
j
#
;
0
g
o
9
=
;
1 +
" :
Since we can compute
-approximations to
C
(
#
), the best solution we nd is a (
+
"
)-approximation for the
CRC. Further, the oracle
A
1
is called
O
(
log
(1+
"
)
#
) =
O
1
"
max
j
log(
u
j
d
j
)
times, resulting in the claimed
running time.
ut
For maximization the perturbed cost in a worst scenario can be relatively close to zero, while all numbers
involved are rather large. This, roughly speaking, spoils an approximation result for maximization similar to
Theorem 5|unless we impose a further condition:
Theorem 6 (Maximization Problems).
Consider the maximization problem of
P
= (
c;X
)
with
X
IN
n
and
c
2
IR
n
0
. Suppose the conditions of Theorem 3hold, and suppose that the relative cost decrease in the
(
d;
)
{CRC of
P
is bounded from below by a positive constant
, i.e.:
9
>
0 : (
c
j
d
j
)
c
j
8
j
2
[
n
]
:
Then there is a
2
{approximation algorithm
A
for the
(
d;
)
{CRC of
P
with running time
T
(
A
)
2
O
T
(
A
2
) + max
j
log(
u
j
d
j
)
T
(
A
1
)
.
4
Using
a
+
b
c
+
d
max
a
c
;
b
d
8
c;d >
0.
Proof.
As in the proof of Theorem 5, we solve the MMax of
P
for
#
= (1 +
"
)
k
for some
k
2
IN and a
particular
" >
0. For the choice of
"
, consider an optimal solution (
x
;#
) with value OPT. We get that
#
#
+
X
j
2
[
n
]
max
f
d
j
x
j
#
;
0
g
=
c
T
x
OPT
| {z }
(1)
(
)
d
T
x
(1
)
c
T
x
;
(2.6)
where (
) holds because (1) is the cost we loose due to the decrease of some of the coecients, and this cost
is bounded by
d
T
x
.
We now set
"
:=
=
2(1
)
(w.l.o.g.
>
1). Then
OPT
(
c
d
)
T
x
c
T
x
= 2
"
(1
)
c
T
x
(2
:
6)
2
"#
:
(2.7)
With this, we can bound the error that arises from approximating
#
:
Denote by
C
(
#
) :=
#
+ max
x
2
X
nP
j
2
[
n
]
c
j
x
j
max
f
d
j
x
j
#;
0
g
o
the optimal cost for a xed
#
.
With
#
0
as in the proof of Theorem 5we then get
OPT
C
(
#
0
)
OPT
#
0
+ max
x
2
X
nP
j
2
[
n
]
c
j
x
j
max
f
d
j
x
j
#
;
0
g
o
(since
#
0
#
)
=OPT
#
0
+ OPT +
#
(since
#
optimal)
OPT
"#
+
"#
(1 +
"
)
#
+ OPT +
#
(since
#
0
(1 +
"
)
#
)
= 1 +
"#
OPT
"#
(2
:
7)
2
:
Since we are able to approximate the optimal solution to the MMax of
P
within a factor of
, the
considerations above prove that our algorithm yields a 2
-approximation.
The number of calls of
A
1
is the same as in the proof of Theorem 5. Since
"
is constant, we get the
claimed overall running time.
ut
2.1 Problems with Totally Unimodular Description
The concept of totally unimodular matrices is arguably the most successful concept for solving a large class
of integer programs. In general, robust counterparts need not inherit total unimodularity. We show that
in general the CRC of
P
can be solved exactly for those problems where the solution space of
P
can be
described by a totally unimodular matrix of size polynomial in the size of the input of
P
.
This generalizes results on specic totally unimodular problems. In particular, it broadly generalizes the
results on Robust Network Flows in [7], since the Min Cost Flow Problem is totally unimodular.
In this section we do not require non-negativity of the cost vector, so the minimization results we show
can be used for maximization problems as well. The structure of the problems considered here is as follows:
Denition 7.
A minimization problem
P
= (
c;X
)
is said to have a
bounded TUM description (
A;b;u
)
if
the set of feasible solutions
X
IN
n
is described by a totally unimodular matrix
A
2
IR
m
n
, an integral
right-hand-side
b
, and an integral vector of upper bounds
u
, i.e.
conv(
X
) =
f
x
2
IR
n
:
Ax
b;x
u
g
; A
TUM
;b;u
2
ZZ
n
:
Remark.
The non-negativity condition can be lifted. Still this yields much less readable results that rest on
similar arguments.
For totally unimodular problems we rst show that we can always solve MMin:
Lemma 8.
If the minimization problem
P
= (
c;X
)
is given by a bounded TUM description
(
A;b;u
)
, then
the Modied Minimization Problem can be solved in polynomial time.
Proof.
Let
e
c
be an arbitrary vector of piecewise linear cost functions as dened in Denition 2. Note that
since
x
0, the second maximum in the cost functions vanishes and they have a single bend at
=
c
0
j
.
We split up each variable into three new variables with slightly dierent cost coecients. Their upper
bounds are chosen such that their sum corresponds to the original variable. Set
x
j
:=
d
=
c
0
j
e
. Bounds and
costs are set as follows:
Variable Upper Bound Cost Coecient
x
(1)
j
x
j
1
c
(1)
j
:=
c
j
x
(2)
j
1
c
(2)
j
:=
c
j
+
c
0
j
x
j
x
(3)
j
u
j
x
j
c
(3)
j
:=
c
j
+
c
0
j
Let 1l denote the vector of ones of compatible size. The resulting problem then reads:
8
>
>
>
>
>
<
>
>
>
>
>
:
min
P
j
2
[
n
]
c
(1)
j
x
(1)
j
+
c
(2)
j
x
(2)
j
+
c
(3)
j
x
(3)
j
s.t.
x
(1)
+
x
(2)
+
x
(3)
2
X
x
(1)
x
1l
x
(2)
1l
x
(3)
u
x :
(2.8)
Since
c
(1)
j
c
(2)
j
c
(3)
j
, it is equivalent to the Modied Minimization Problem (2.2).
On the other hand we have
x
(1)
+
x
(2)
+
x
(3)
2
conv(
X
)
x
(1)
x
1l
x
(2)
1l
x
(3)
u
x
9
>
>
=
>
>
;
()
2
6
6
4
AAA
I
0 0
0
I
0
0 0
I
3
7
7
5
|{z }
=:
A
0
2
4
x
(1)
x
(2)
x
(3)
3
5
| {z }
=:
x
0
2
6
6
4
b
x
1l
1l
u
x
3
7
7
5
| {z }
=:
b
0
where
I
is the
n
-dimensional identity matrix.
The matrix
A
0
is again totally unimodular, and the right-hand-side
b
0
is obviously integral. Therefore the
optimum of
8
>
>
>
>
>
<
>
>
>
>
>
:
min
P
j
2
[
n
]
c
(1)
j
x
(1)
j
+
c
(2)
j
x
(2)
j
+
c
(3)
j
x
(3)
j
s.t.
x
(1)
+
x
(2)
+
x
(3)
2
conv(
X
)
x
(1)
x
1l
x
(2)
1l
x
(3)
u
x
(2.9)
is integral and thus an optimal solution of (2.8). Also, it can be computed in polynomial time.
ut
Further, in this setting
C
is convex:
Lemma 9.
Let
C
(
#
)
be dened as in (2.5). Then for a minimization problem
P
= (
c;X
)
with a bounded
TUM description
(
A;b;u
)
,
C
is convex for any
c
2
IR
n
;d
2
IN
n
;
2
[
n
]
.
Proof.
Consider problem (2.3), where because
x
0 the variables
z
j
and corresponding constraints are
removed, and let (
x
(1)
;y
(1)
) and (
x
(2)
;y
(2)
) be optimal solutions to this problem for
#
=
#
1
and
#
=
#
2
,
respectively. Then for arbitrary
2
[0
;
1], (
x
(1)
+ (1
)
x
(2)
;y
(1)
+ (1
)
y
(2)
) is a feasible solution for
#
=
#
1
+ (1
)
#
2
, if in the last constraint of (2.3) we replace
X
by conv(
X
).
The proof of Lemma 8tells us that the optimal solution of this problem is always integral. Hence we get
C
(
#
1
+ (1
)
#
2
)
c
T
(
x
(1)
+ (1
)
x
(2)
) +
(
#
1
+ (1
)
#
2
) + 1l
T
(
y
(1)
+ (1
)
y
(2)
)
=
C
(
#
1
) + (1
)
C
(
#
2
)
:
This proves that
C
is indeed convex.
ut
We can now apply Theorem 4and get that we can solve the CRC of any problem with a bounded totally
unimodular description in polynomial time:
Theorem 10.
If the minimization problem
P
= (
c;X
)
is given by a bounded TUM description
(
A;b;u
)
,
then for any
c
2
IR
n
;d
2
IN
n
and
2
[
n
]
, there is an exact algorithm for the
(
d;
)
{CRC of
P
that runs in
polynomial time.
2.2 Integer Programs with Two Variables per Inequality
We now apply our main results to a second, large, and intensely studied class of integer programs, namely
integer programs with two variables per inequality (IP2).
Denition 11 (Integer Programs with Two Variables per Inequality).
A
bounded integer program
with two variables per inequality
(bounded IP2) is a system of the form
min
f
c
T
x
:
a
T
i
x
b
i
for
i
= 1
;:::;m; `
x
u; x
integer
g
;
where
b
2
ZZ
m
,
`;u
2
ZZ
n
,
c
2
Q
n
and each vector
a
i
2
ZZ
n
has two non-zero components.
A bounded IP2 is called
monotone
if the non-zero coecients of
a
i
have opposite signs.
The conditions required in Section 2allow to intensely use the existing techniques for non-robust IP2, in
particular [12], [13] and [3]. We obtain a pseudopolynomial time 2{approximation for the CRC of bounded
IP2s and an exact pseudopolynomial time algorithm for the CRC of bounded, monotone IP2s.
Theorem 12.
The cost robust counterpart of a bounded monotone IP2 can be solved in pseudopolynomial
time.
Remark.
In the appendix, we prove Theorem 12 by extending (to handle piecewise linear functions) the
pseudopolynomial time algorithm of Hochbaum and Naor [13] for bounded monotone IP2. In [3], Bar-Yehuda
and Rawitz give an exact pseudopolynomial algorithm for monotone cost functions but non-negative lower
bounds.
Theorem 13.
There is a pseudopolynomial time 2-approximation algorithm for the cost robust counterpart
of a bounded IP2 with non-negative coecients in the objective function and non-negative lower bounds.
Remark.
In the appendix, we prove 13 by extending (to handle piecewise linear functions) the pseudopoly-
nomial 2-approximation algorithm of Hochbaum et al. [12]. This result is also shown in [3].
3 Uncertainty in Constraints
We now turn to the case where the coecients of a single linear constraint (or those of a constant number of
them) are uncertain. All results presented here hold both for minimization and maximization, so we restrict
to one of the two. The formal denition of the considered class of problems is as follows:
Denition 14 (Constraint Robust Maximization Problem).
Consider the problem
max
x
2
X
f
c
T
x
g
,
given by
P
= (
c;X
)
where
c
2
IR
n
and
X
=
f
x
2
X
0
:
a
T
x
r
g
for some
X
0
ZZ
n
;a
2
IR
n
;r
2
IR
.
For a non-negative integer vector
b
2
IN
n
together with
2
[
n
]
, the
(
b;
){Constraint Robust Counterpart
(ConsRC) of
P
is dened by
max
c
T
x
s.t.
x
2
X
0
; a
T
x
+ max
S
[
n
]
j
S
j
X
j
2
S
j
b
j
x
j
j
r:
(3.1)
As in the cost robust setting, the left hand side of the constraint with uncertain coecients can be
transformed into a sum of piecewise linear convex function with two bends:
Lemma 15.
The
(
b;
)
{Constraint Robust Counterpart of the maximization problem
P
= (
c;X
)
as dened
in Denition 14 is equivalent to
max
0
max
x
2
X
(
)
c
T
x
(3.2)
with
X
(
) :=
8
<
:
x
2
X
0
:
+
X
j
2
[
n
]
a
j
x
j
+ max
f
b
j
x
j
;
0
g
+ max
f
b
j
x
j
;
0
g
r
9
=
;
:
Proof.
With the same transformations as in the cost robust setting, we get that (3.1) is equivalent to
max
c
T
x
s.t.
x
2
X
0
; a
T
x
+ min
0
8
<
:
+
X
j
2
[
n
]
a
j
x
j
+ max
f
b
j
x
j
;
0
g
+ max
f
b
j
x
j
;
0
g
9
=
;
r:
Thus, for all feasible solutions
x
of (3.1) there exists some
(
x
)
0 such that
x
2
X
(
(
x
)). Consequently, as
claimed (3.1) is equivalent to max
0
max
x
2
X
(
)
c
T
x
.
ut
For the non-binary case, the optimal value
can be found by enumeration, since it is integral and bounded
by the maximum deviation in the constraint coecients.
Corollary 16.
Consider the
(
b;
)
{ConsRC of the maximization problem
P
= (
c;X
)
as dened in Denition
14. Suppose there is an algorithm
A
1
computing a
-approximation for
max
x
2
X
(
)
c
T
x
for any
0
, and
an algorithm
A
2
that computes upper bounds
u
j
on the absolute value of each variable
x
j
in the optimal
solution of (3.1). Then there is a
-approximation algorithm
A
for the
(
b;
)
{ConsRC of
P
with running
time
T
(
A
) =
O
T
(
A
2
) + max
j
f
u
j
b
j
g
T
(
A
1
)
.
If all variables are binary, i.e.
X
0
f
0
;
1
g
n
, there are only
n
+ 1 possible values for
, and for a xed
the constraint of problem (3.2) becomes linear again. Hence, to solve the (
b;
){ConsRC of
P
= (
c;X
), it
suces to solve
n
+ 1 problems of the type of
P
for slightly dierent coecients in the linear constraint:
Theorem 17.
If
X
0
f
0
;
1
g
n
, the
(
b;
)
{ConsRC of the maximization problem
P
= (
c;X
)
as dened in
Denition 14 is equivalent to
max
`
=1
;:::;n
+1
0
@
max
c
T
x
s.t.
x
2
X
0
; b
`
+
a
T
x
+
`
1
X
j
=1
(
b
j
b
`
)
x
j
r
1
A
;
whereby w.l.o.g. we assume
b
n
b
n
1
:::
b
1
and dene
b
n
+1
:= 0
.
Remark.
This result is an exact sibling of the result on cost robust binary problems in [7], but with uncer-
tainty in a constraint instead of the costs.
Proof.
The optimal value
lies in [0
;b
1
]. We split up this interval at
b
`
;`
=
n:::;
2
;
and maximize over
each subinterval, i.e. we reformulate (3.2) to get
max
`
=1
;:::;n
max
2
[
b
`
+1
;b
`
]
max
x
2
X
(
)
c
T
x
:
(3.3)
For
x
2 f
0
;
1
g
n
we have max
f
b
j
x
j
;
0
g
= max
f
b
j
;
0
g
x
j
, and thus for
2
[
b
`
+1
;b
`
]
X
(
) =
8
<
:
x
2
X
0
:
+
X
j
2
[
n
]
a
j
x
j
+ max
f
b
j
;
0
g
x
j
r
9
=
;
=
8
<
:
x
2
X
0
:
+
a
T
x
+
`
X
j
=1
(
b
j
)
x
j
r
9
=
;
:
(3.4)
For any xed
x
, the left hand side of the constraint in (3.4) is a linear function in
that has to be no greater
than
r
somewhere in [
b
`
+1
;b
`
] for
x
to be feasible. Thus, if the constraint is satised for any
in this interval,
because of linearity it will be satised for at least one of the values
=
b
`
+1
or
=
b
`
. As a consequence,
max
2
[
b
`
+1
;b
`
]
max
x
2
X
(
)
c
T
x
= max
=
b
`
+1
;b
`
max
x
2
X
(
)
c
T
x
:
(3.5)
Combining (3.3){(3.5) this yields the claimed result.
ut
Remark.
A direct corollary from Theorem 17 is the existence of an FPTAS for the weight robust counterpart
of the binary Knapsack Problem, generalizing a result from [17].
All the results from this section hold as well if there is a constant number
k
of constraints with uncertain
coecients. The problem max
x
2
X
(
)
would then have to be solved (max
j
f
u
j
b
j
g
)
k
times in the setting of
Corollary 16 and (
n
+ 1)
k
times in the binary case.
3.1 Robust Unbounded Knapsack Problems
To demonstrate how versatile our main results are for combinatorial problems, we apply them to the
Un-
bounded Knapsack Problem
, the non-binary extension of the classical Knapsack Problem (KP). For this
problem we will be able to handle counterparts that feature both, cost robustness and robustness in the
constraint.
To distinguish between the standard version of the Unbounded Knapsack and a technically relevant
modication used further below, we speak of the
Linear
and the
Concave
Unbounded Knapsack Problem.
Denition 18 (Linear Unbounded Knapsack Problem).
An instance of the
Linear Unbounded Knap-
sack Problem
(UKP) is given by a knapsack capacity
W
0
and
n
types of items with weights
w
j
2
IN
and
costs
c
j
2
IR
0
,
j
2
[
n
]
. The task is to nd a vector
x
2
IN
n
with
P
j
w
j
x
j
W
maximizing the cost
P
j
c
j
x
j
.
The linear UKP and its later dened extensions, in particular its robust counterparts, are
NP
-hard, by
the weak
NP
-hardness of the binary KP. Intuitively, UKP seems to be more complex than the binary KP,
since the input is more compact. Still, as for KP, there is both a pseudopolynomial Dynamic Program (DP)
and an FPTAS [18,14].
We now consider the robust versions of the Unbounded Knapsack Problem.
Cost Robust UKP.
While the result for binary cost robust programs [7] can be applied to the standard
Knapsack Problem, the CRC of the UKP surpasses the reach of [7]. One may argue that the UKP can
be formulated as a binary integer program spending a variable for each potentially useful copy of an item.
But, apart from the enormous blow up in size, the robust counterpart of such an IP, where at most a xed
number of cost coecients may vary, is completely dierent to that of the UKP|and apparently does not
make much sense.
To tackle the
Cost Robust Unbounded Knapsack Problem
(CRUKP) with our results from Section 2, we
consider the following problem:
Denition 19 (Concave Unbounded Knapsack Problem).
An instance of the
Concave Unbounded
Knapsack Problem
(ConcUKP) is given by a knapsack capacity
W
, weights
w
j
2
IN
;j
2
[
n
]
, and
monotoni-
cally increasing, concave cost functions
c
j
: IR
0
!
IR
0
,
j
2
[
n
]
, given by an oracle.
The task is to nd a vector
x
2
IN
n
with
P
j
w
j
x
j
W
maximizing the cost
P
j
c
j
(
x
j
)
.
This problem has been considered in literature before, as it has a lot of applications. Hochbaum presented
an FPTAS for it in [11]. We sketch an alternative FPTAS based on a dynamic program (DP). The detailed
proofs are moved to the appendix.
To construct the FPTAS, we consider the following DP for ConcUKP: Iteratively compute state spaces
S
j
;j
= 1
;:::;n
. A state [
Y;C
]
2 S
j
represents a partial solution with weight
Y
and cost
C
using only items
from the subset
f
1
;:::;j
g
.
S
j
is created by adding any feasible number of items of type
j
to each state in
S
j
1
, starting with
S
0
:=
f
[0
;
0]
g
. Through elimination of dominated states we can ensure
jS
j
j
W
+ 1 at
all times, thus bounding the number of calls to the cost oracle by
O
(
n
2
W
).
This DP can be transformed into an FPTAS by a general scheme due to Woeginger [22]. To get polynomial
running time, however, it has to be slightly modied: Instead of considering every possible number of items of
each type to be added to the knapsack, we only consider powers of 1+
"
. The concavity of the cost functions
ensures that the loss arising through this is bounded by a factor of 1 +
"
, preserving the approximation
guarantee of the FPTAS.
Now observe that the cost functions of the Modied Maximization Problem for UKP are feasible cost
functions for ConcUKP. Also,
b
W
=
w
j
c
is an upper bound on
x
j
with a polynomial encoding length. Therefore,
we can apply Theorem 6to get the following result:
Theorem 20.
For all
" >
0
, there is a
(2 +
"
)
{approximation algorithm for CRUKP, if the relative cost
decrease is bounded from below by a constant.
Weight Robust UKP.
Next we turn to the Unbounded Knapsack Problem where weights instead of costs
are uncertain. At most
types of items can increase their weight, and we are looking for a solution that is
feasible in all scenarios, maximizing the cost. In terms of section 3, we have uncertainty in the only constraint.
Let
w
j
denote the possible increase in weight of items of type
j
. We consider the (
w;
)-ConsRC of UKP,
also called the
Weight Robust Unbounded Knapsack Problem
(WRUKP).
From Corollary 16 we learn that we have to solve max
x
2
X
(
)
c
T
x
in order to get a pseudopolynomial
algorithm for WRUKP. The FPTAS from [11] could be used for this, but we will focus on computing an
exact algorithm in pseudopolynomial time here. This can be done by the DP presented above for ConcUKP,
slightly modied to work with piecewise linear weight functions with a single bend. With
u
j
=
W
w
j
, we get
an algorithm for WRUKP with running time
O
max
w
j
w
j
n
2
W
2
.
General Robust UKP.
Finally, we consider a version of UKP where both weights and costs are uncertain,
called the
General Robust Unbounded Knapsack Problem
(RUKP). At most
w
types of items can increase
their weight, and at most
c
cost coecients decrease. The goal is to nd a solution
x
that is feasible in all
scenarios and maximizes the worst-case cost:
max
x
8
>
<
>
:
X
j
2
[
n
]
c
j
x
j
max
S
c
[
n
]
j
S
c
j
c
8
<
:
X
j
2
S
c
d
j
x
j
9
=
;
9
>
=
>
;
s.t.
X
j
2
[
n
]
w
j
x
j
+ max
S
w
[
n
]
j
S
w
j
w
8
<
:
X
j
2
S
w
w
j
x
j
9
=
;
W :
This is the (
w;
w
){ConsRC of CRUKP. We adapt the DP for ConcUKP such that it works for piecewise
linear weight functions. By Theorem 3we get an exact algorithm
A
1
for CRUKP on the modied solution
space
X
(
) with a running time of
T
(
A
1
) =
O
max
jd
j
w
j
n
2
W
2
. Thus we can solve RUKP exactly in a
running time of
O
max
jw
j
w
j
max
jd
j
w
j
n
2
W
3
.
Alternatively, if the relative cost decrease is bounded from below by a constant, we can use the (2 +
"
){
approximation algorithm
A
0
1
for CRUKP with polynomial running time to get a (2 +
"
){approximation for
RUKP in time
O
max
jw
j
w
j
W
T
(
A
0
1
)
.
Acknowledgement
We are grateful to Martin Skutella and Gunter Rote for discussions that substantially enhanced this paper.
References
1. Special issue on robust optimization.
Mathematical Programming B
, 107(1-2), 2006.
2. H. Aissi, C. Bazgan, and D. Vanderpooten. Approximation of min-max and min-max regret versions of some
combinatorial optimization problems.
European Journal of Operational Research
, 179(2):281{290, 2007.
3. R. Bar-Yehuda and D. Rawitz. Ecient algorithms for integer programs with two variables per constraint 1.
Algorithmica
, 29(4):595{609, 2001.
4. A. Ben-Tal and A. Nemirovski. Robust convex optimization.
Mathematics of Operations Research
, 23(4):769{805,
1998.
5. A. Ben-Tal and A. Nemirovski. Robust solutions to uncertain linear programs.
Operations Research Letters
,
25(1):1{13, 1999.
6. A. Ben-Tal and A. Nemirovski. Robust solutions of linear programming problems contaminated with uncertain
data.
Mathematical Programming
, 88(3):411{424, 2000.
7. D. Bertsimas and M. Sim. Robust discrete optimization and network ows.
Mathematical Programming
, 98(1-
3):49{71, 2003.
8. D. Bertsimas and M. Sim. The price of robustness.
Operations Research
, 52(1):35{53, 2004.
9. E. Cohen and N. Megiddo. Improved algorithms for linear inequalities with two variables per inequality. In
Proceedings of the 23th Annual ACM symposium on Theory of Computing
, pages 145{155. ACM, 1991.
10. U. Feige, K. Jain, M. Mahdian, and V. Mirrokni. Robust combinatorial optimization with exponential scenar-
ios. In
IPCO '07: Proceedings of the 12th International Conference on Integer Programming and Combinatorial
Optimization
, pages 439{453, Berlin, Heidelberg, 2007. Springer-Verlag.
11. D. Hochbaum. A nonlinear knapsack problem.
Operations Research Letters
, 17(3):103{110, 1995.
12. D. Hochbaum, N. Megiddo, J. Naor, and A. Tamir. Tight bounds and 2-approximation algorithms for integer
programs with two variables per inequality.
Mathematical Programming
, 62(1):69{83, 1993.
13. D. Hochbaum and J. Naor. Simple and fast algorithms for linear and integer programs with two variables per
inequality.
SIAM Journal on Computing
, 23:1179{1192, 1994.
14. O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems.
Journal of ACM
, 22:463{468, 1975.
15. R. Khandekar, G. Kortsarz, V. Mirrokni, and M. Salavatipour. Two-stage robust network design with exponential
scenarios. In
ESA '08: Proceedings of the 16th annual European Symposium on Algorithms
, pages 589{600, Berlin,
Heidelberg, 2008. Springer-Verlag.
16. O. Klopfenstein and D. Nace. A note on polyhedral aspects of a robust knapsack problem. Available online at
http://www.optimization-online.org/DB FILE/2006/04/1369.pdf, 2007.
17. O. Klopfenstein and D. Nace. A robust approach to the chance-constrained knapsack problem.
Operations
Research Letters
, 36(5):628{632, 2008.
18. S. Martello and P. Toth.
Knapsack Problems. Algorithms and Computer Implementations
. John Wiley and Sons,
1990.
19. N. Megiddo. Towards a genuinely polynomial algorithm for linear programming.
SIAM J. Comput.
, 12(2):347{
353, 1983.
20. J. C. Picard. Maximal closure of a graph and applications to combinatorial problems.
Management Science
,
22(11):1268{1272, 1976.
21. A. L. Soyster. Convex programming with set-inclusive constraints and applications to inexact linear programming.
Operations Research
, 21(5):1154{1157, 1973.
22. G. Woeginger. When does a dynamic programming formulation guarantee the existence of an FPTAS? In
SODA
'99: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms
, pages 820{829, Philadelphia,
PA, USA, 1999. Society for Industrial and Applied Mathematics.
23. G. Yu. On the max-min 0-1 knapsack problem with robust optimization applications.
Operations Research
,
44(2):407{415, 1996.
Appendix
An Algorithm for Bounded Monotone IP2
Theorem 12 (revisited).
The cost robust counterpart of a bounded monotone IP2 can be solved in pseu-
dopolynomial time.
Proof.
In what follows, we require the following graph concept. A
closed set
of a digraph is a subset of nodes
with no outgoing arcs to its complement. The
minimum weight closure
for a digraph is the problem of nding
a closed set with minimum weight. It was shown to be polynomial-time solvable by Picard [20].
Using Theorem 3, it is enough to solve the modied problem
Q
M
= min
8
<
:
X
j
e
c
j
(
x
j
):
a
T
i
x
b
i
for
i
= 1
;:::;m; `
x
u; x
integer
9
=
;
associated to a bounded monotone IP2 system
Q
= min
f
c
T
x
:
a
T
i
x
b
i
for
i
= 1
;:::;m; `
x
u; x
integer
g
in pseudopolynomial time. Recall that
e
c
j
(
x
j
) =
c
j
x
j
+ max
f
d
j
x
j
#;
0
g
+ max
f
d
j
x
j
#;
0
g
.
Hochbaum and Naor [13] proposed a pseudopolynomial time algorithm for a bounded monotone IP2
that reduces the problem to the minimum weight closure of a digraph with pseudopolynomially many nodes.
They established a bijection between the feasible solutions of
Q
and the non-empty closed sets of a certain
digraph
G
which we will also use: The variables
`
j
x
j
u
j
are represented in
G
by disjoint directed paths
P
j
having
u
j
`
j
+1 nodes identied with the numbers from
u
j
to
`
j
in consecutive decreasing order. Each
inequality
a
ir
x
r
a
is
x
s
b
i
of
Q
(where
a
ir
a
is
>
0) is represented in
G
by a collection of arcs from
P
s
to
P
r
: the node
p
of path
P
s
is connected to the node
d
(
a
is
p
+
b
i
)
=a
ir
e
of path
P
r
, for every
p
such that the
latter node exists. Finally, there is a special vertex
v
which is connected, bidirectionally, to the last node
`
j
of every path
P
j
. This ensures that any closed set
S
6
=
;
contains
v
, forcing
P
j
\
S
to be a collection of
nodes with consecutive labels from
p
j
to
`
j
, for some
`
j
p
j
u
j
. In the bijection, this is interpreted as
the assignment
x
j
=
p
j
for variable
x
j
.
We use this bijection to solve
Q
M
(see Algorithm 1). We need to set weights for the nodes of
G
so that
if
S
x
is the closed set associated to the feasible solution
x
for
Q
M
, then the total weight of
P
j
\
S
x
is equal
to
e
c
j
(
x
j
). We achieve this with the following weights
w
j
(
p
) for the nodes
p
2
P
j
: Set
w
j
(
l
j
) =
c
j
`
j
and
w
j
(
p
) =
e
c
j
(
p
)
e
c
j
(
p
1) for
`
j
+ 1
p
u
j
. Finally, we nd, using Picard's algorithm [20], the minimum
weight closure of
G
with weights
f
w
j
(
)
g
j
and a suitable weight for
v
that makes the minimum closure
non-empty.
ut
A 2{Approximation Algorithm for Bounded IP2
Theorem 13 (revisited).
There is a pseudopolynomial time 2-approximation algorithm for the cost robust
counterpart of a bounded IP2 with non-negative coecients in the objective function and non-negative lower
bounds.
Proof.
We closely follow the results in [12]. Consider the modied minimization problem
S
M
= min
f
Pe
c
j
(
x
j
):
a
T
i
x
b
i
; `
x
u; x
integer
g
of a bounded IP2 instance with non-negative coecients in the objective function
and non-negative lower bounds. In this case, we just need to consider
e
c
j
(
x
j
) =
c
j
x
j
+ max
f
d
j
x
j
#;
0
g
,
where
c
j
and
d
j
are non-negative numbers. We associate two variables
x
+
j
and
x
j
to each variable
x
j
in
S
M
and then dene the following monotone system
S
0
M
:
min 1
2
n
X
j
=1
e
c
j
(
x
+
j
) +
e
c
j
(
x
j
)
a
iv
x
+
v
a
iw
x
w
b
i
and
a
iv
x
v
+
a
iw
x
+
w
b
i
;
8
a
iv
a
iw
>
0
a
iv
x
+
v
+
a
iw
x
+
w
b
i
and
a
iv
x
v
a
iw
x
w
b
i
;
8
a
iv
a
iw
<
0
`
x
+
u
u
x
`
x
+
;x
2
ZZ
n
Algorithm 1
: Algorithm for bounded monotone IP2
V
=
f
(
j;p
) :
j
2 f
1
;:::;n
g
and
`
j
p
u
j
g [ f
v
g
1
E
var
=
f
((
j;p
)
;
(
j;p
1)) :
j
2 f
1
;:::;n
g
and
`
j
+ 1
p
u
j
g
2
E
v
=
f
((
j;`
j
)
;v
) :
j
2 f
1
;:::;n
gg [ f
(
v;
(
j;`
j
)) :
j
2 f
1
;:::;n
gg
3
forall
a
ir
x
r
a
is
x
s
b
i
of
Q
where
a
ir
;a
is
>
0
do
4
E
ineq
i
=
f
((
s;p
)
;
(
r;
d
(
a
is
p
+
b
i
)
=a
ir
e
)) :
`
s
p
u
s
g \
V
V
5
endfor
6
E
=
E
var
[
E
v
[
S
i
E
ineq
i
7
for
j
:= 1
to
n
do
8
w
((
j;`
j
)) =
c
j
`
j
9
w
((
j;p
)) =
e
c
j
(
p
)
e
c
j
(
p
1) for
`
j
+ 1
p
u
j
10
endfor
11
w
(
v
) =
n
max
j
fj
c
j
jg
max
j
fj
`
j
j
+
j
u
j
jg
12
Find minimum weight closure
S
of
G
= (
V;E
) using
w
as weight function
13
for
j
:= 1
to
n
do
14
x
j
= max
f
p
: (
j;p
)
2
V
\
S
g
15
endfor
16
return
x
17
Note that if
x
is feasible for
S
M
, then
x
+
=
x
,
x
=
x
is feasible for
S
0
M
. Moreover, their respective costs
coincide and therefore
OPT
(
S
0
M
)
OPT
(
S
M
). We can compute an optimal solution (~
x
+
;
~
x
) for
S
0
M
using
the algorithm in Theorem 12 and we can also compute an arbitrary feasible solution
z
for
S
M
, using the
strongly polynomial time algorithm from [19,9]. Finally, we construct the 2-approximate solution
b
x
for
S
M
using
z
and ~
x
as follows:
{
If
z
j
lies in the interval between ~
x
+
j
and
~
x
j
, we set
b
x
j
=
z
j
.
{
If
z
j
is less than both ~
x
+
j
and
~
x
j
, we set
b
x
j
= min
f
~
x
+
j
;
~
x
j
g
.
{
If
z
j
is greater than both ~
x
+
j
and
~
x
j
, we set
b
x
j
= max
f
~
x
+
j
;
~
x
j
g
.
In [12], they prove that this solution is feasible for
S
M
. In order to prove the approximation guarantee,
we need a introduce a new argument. Note that, since the objective function coecients and the lower
bounds are non-negative, then
e
c
j
(
b
x
j
)
e
c
j
(~
x
+
j
) +
e
c
j
(
~
x
j
). Therefore the value of
b
x
in
S
M
is at most
2
OPT
(
S
0
M
)
2
OPT
(
S
M
). It is easy to check the proposed algorithm runs in pseudopolynomial time.
ut
An FPTAS for ConcUKP
The details of the DP sketched in Section 3.1 are listed in Algorithm 2. By elimination of dominated states
the size of each
S
j
can be reduced to at most
W
+ 1. Every time a new state is created, we have to call the
oracle for the cost function, thus the number of these calls is in
O
(
nW
2
).
As outlined above, the DP can be transformed into an FPTAS with the result from [22].
Lemma 21.
There is an FPTAS for ConcUKP.
Proof.
In Algorithm 2, out of each state we create up to
u
j
+ 1 new states, which is not polynomial in
the input size as demanded in [22], Condition C.4(ii). Therefore, we modify the DP as follows: For a given
accuracy
" >
0, instead of all possible numbers of items, only consider powers of 1+
"
in line 6 of Algorithm
2.
5
To see that the solution of the modied DP is within a factor of 1+
"
of the optimum, consider an optimal
solution
x
and the corresponding DP solution
x
:
(1 +
"
)
k
j
x
j
<
(1 +
"
)
k
j
+1
)
x
j
= (1 +
"
)
k
j
:
5
To get an integral solution, the powers (1+
"
)
k
could be rounded up, preserving the approximation guarantee. To
simplify things, however, we consider the unrounded values.
Algorithm 2
: DP for ConcUKP
u
j
:=
b
W
=
w
j
c 8
j
2
[
n
]
1
S
0
:=
f
[0
;
0]
g
2
for
j
:= 1
to
n
do
3
S
j
:=
?
4
forall
[
Y;C
]
2 S
j
1
do
5
for
i
:= 0
to
u
j
do
6
if
Y
+
i
w
j
> W
then
7
break
8
endif
9
S
j
:=
S
j
[ f
[
Y
+
i
w
j
;C
+
c
j
(
i
)]
g
10
endfor
11
endfor
12
endfor
13
return
max
f
C
: [
Y;C
]
2 S
n
g
14
Since
c
j
is non-decreasing (
i
), concave (
ii
) and non-negative (
iii
), for all
j
2
[
n
] we get
c
j
(
x
j
)
(
i
)
c
j
1
1 +
"x
j
(
ii
)
1
1 +
"c
(
x
j
) +
1
1
1 +
"
c
(0)
(
iii
)
1
1 +
"c
(
x
j
)
:
(3.6)
Denote the best value found by the modied DP by
C
DP
and the optimal cost by OPT. Then it follows that
C
DP
X
j
2
[
n
]
c
j
(
x
j
)
(3.6)
1
1 +
"
X
j
2
[
n
]
c
j
(
x
j
) = 1
1 +
"
OPT
:
Therefore, the best solution found by the DP is indeed a (1 +
"
)-approximation.
Now we show that the modied DP satises the conditions from [22]. Let
k
:= max
f
k
2
IN
r
f
0
g
:
(1 +
"
)
k
max
j
(
u
j
)
g
. We have a family of mappings
F
=
f
e
F;F
0
;F
1
;:::;F
k
g
creating new states out of a
state [
Y;C
] and an input vector [
w
j
;c
j
], as well as a family
H
=
f
e
H;H
0
;H
1
;:::;H
k
g
with mappings checking
the feasibility of the new states. They are dened as follows:
e
F
(
w
j
;c
j
;Y;C
) := [
Y;C
]
e
H
(
w
j
;c
j
;Y;C
) := 0
F
k
(
w
j
;c
j
;Y;C
) := [
Y
+ (1 +
"
)
k
w
j
;C
+
c
j
((1 +
"
)
k
)]
H
k
(
w
j
;c
j
;Y;C
) :=
Y
+ (1 +
"
)
k
w
j
W :
We set the degree-vector
D
:= [1
;
1], and two relations on the states as follows:
S
dom
S
0
,
S
=
S
0
;
[
Y;C
]
qua
[
Y
0
;C
0
]
,
Y
Y
0
:
Conditions C.1 through C.3 from [22] can then be veried. With the modication from above,
jFj
is
linear in the input:
jFj
=
k
+ 2
log
(1+
"
)
(max
j
2
[
n
]
u
j
)+2
:
Thus the DP also satises C.4 and can therefore be turned into an FPTAS. Since the modied DP is itself
a (1 +
"
)-approximation, we get an FPTAS for ConcUKP.
ut
