Algorithms for Inverse Optimization Problems

Sara Ahmadian
Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON N2L 3G1, Canada
sahmadian@uwaterloo.ca

Umang Bhaskar1
Tata Institute of Fundamental Research, Mumbai, India 400 005
umang@tifr.res.in

Laura Sanità
Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON N2L 3G1, Canada
sanita@uwaterloo.ca

Chaitanya Swamy2
Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON N2L 3G1, Canada
cswamy@uwaterloo.ca

Abstract
We study inverse optimization problems, wherein the goal is to map given solutions to an under-
lying optimization problem to a cost vector for which the given solutions are the (unique) optimal
solutions. Inverse optimization problems find diverse applications and have been widely studied.
A prominent problem in this field is the inverse shortest path (ISP) problem [9, 3, 4], which finds
applications in shortest-path routing protocols used in telecommunications. Here we seek a cost
vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has
minimum `∞ norm. Despite being extensively studied, very few algorithmic results are known for
inverse optimization problems involving integrality constraints on the desired cost vector whose
norm has to be minimized.
Motivated by ISP, we initiate a systematic study of such integral inverse optimization prob-
lems from the perspective of designing polynomial time approximation algorithms. For ISP, our
main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint
commodities, which we show is tight assuming P 6=NP. We then consider the integral-cost inverse
versions of various other fundamental combinatorial optimization problems, including min-cost
flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight
or nearly-tight approximation guarantees for these. Our guarantees for the first two problems
are based on results for a broad generalization, namely integral inverse polyhedral optimization,
for which we also give approximation guarantees. Our techniques also give similar results for
variants, including `p -norm minimization of the integral cost vector, and distance-minimization
from an initial cost vector.

2012 ACM Subject Classification Theory of computation → Network optimization, Theory of

computation → Approximation algorithms analysis, Mathematics of computing → Network flows

Keywords and phrases Inverse optimization, Shortest paths, Approximation algorithms, Linear
programming, Polyhedral theory, Combinatorial optimization

Digital Object Identifier 10.4230/LIPIcs.ESA.2018.1

1
Funded in part by a Ramanujan Fellowship. Part of this work was done while visiting U. Waterloo.
2
Supported in part by NSERC grant 327620-09 and an NSERC Discovery Accelerator Supplement Award.
© Sara Ahmadian, Umang Bhaskar, Laura Sanità, and Chaitanya Swamy;
licensed under Creative Commons License CC-BY
26th Annual European Symposium on Algorithms (ESA 2018).
Editors: Yossi Azar, Hannah Bast, and Grzegorz Herman; Article No. 1; pp. 1:1–1:14
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
1:2 Algorithms for Inverse Optimization Problems

1 Introduction

Consider the following problem, adapted from [4], faced by the administrator of a telecommu-
nication network. The administrator seeks to impose a desired routing pattern (e.g., one that
distributes traffic along multiple paths to minimize congestion) under a given underlying
routing protocol. Many routing protocols – OSPF (open-shortest-path-first), IS-IS etc. – use
shortest-path routing, with path lengths defined as the sum of link lengths that are set by the
administrator, where the link lengths must typically be positive integers that can be stored
using a limited number of bits (e.g., in IS-IS, they must be at most 63). Thus, the adminis-
trator must choose small, positive, integer link lengths so that the resulting shortest paths
coincide with the prescribed paths (thus ensuring that we utilize precisely these paths).
This is an inverse shortest path (ISP) problem (which also arises in seismic tomography,
traffic modeling, and network tolling [9, 19, 8, 12, 13]), a prominent problem from the rich
class of inverse optimization problems, wherein we are given solutions to an underlying
optimization problem and we seek a cost vector under which the given solutions constitute
the (unique) optimal solutions. Since we map solutions to a suitable cost vector, this is termed
inverse optimization. Inverse optimization problems find applications in a variety of domains
including telecommunication routing [3, 4], seismic and medical tomography [9, 19, 23],
traffic modeling and network tolling [12, 13, 9, 8], and portfolio optimization [18]. They
also arise in the domain of revealed-preference theory in economics [24], which seeks to
understand when observations can be attributed to behavior consistent with game-theoretic
models. As these examples indicate, inverse optimization problems typically have two primary
objectives: (a) parameter estimation, where we seek to infer certain parameters of a system
that are consistent with a set of observations (e.g., seismic and medical tomography, revealed
preference theory); and (b) solution imposition, where the goal is to (minimally) perturb the
system parameters so as to enforce a set of solutions (e.g., the telecommunication routing
application mentioned above, and network tolling where we want to find (minimal) edge tolls
imposing a given routing pattern as an equilibrium flow).
Motivated by ISP, we consider inverse optimization problems wherein the desired cost
vector c is required to be positive, integral, and induce the given subset S of solutions as
the unique optimal solutions to the underlying optimization problem; we call these problems
integral inverse optimization problems. We primarily consider the objective of minimizing
kck∞ , but our results also yield guarantees for the objective of minimizing the perturbation
kc − c(0) k∞ of a given “base” cost vector c(0) , which is frequently considered in the inverse-
optimization literature. Uniqueness can be important because we may want to explain/impose
S without introducing spurious solutions (i.e., “we get precisely what we bargain for”), and
integrality is, in many cases, a desirable or necessary practical consideration (as in the
telecommunication-routing setting). Despite extensive literature, very few algorithmic results
are known for inverse optimization problems involving integrality constraints on the desired
cost vector whose norm, or deviation from a given cost vector c(0) , is to be minimized; we
only know of [3, 4] that address this, both in the context of ISP.

Our contributions and results. We initiate a systematic study of integral inverse optimiza-
tion problems from the perspective of designing polynomial time (approximation) algorithms.
We focus on the inverse versions of various combinatorial optimization problems, a nat-
ural starting point to investigate integral inverse optimization problems. As our results
demonstrate, even for such problems, wherein the underlying optimization problem is well
structured and polytime-solvable, the resulting integral inverse optimization problems are
S. Ahmadian et al. 1:3

Table 1 Summary of our main results. These are stated for the implicit model, wherein the
solution-set is specified implicitly by listing its support set. Most of our guarantees also hold in the
explicit model.

Problem Our results

Inverse shortest path (ISP) polytime
additive 1-approximation; problem is NP-hard
Node-disjoint multicommodity ISP
(Previous work gives multiplicative O(|V |)-approx.)
Inverse polyhedral optimization additive 1-approximation for minimization (IMin-Poly)
(IOpt-Poly) with TU constraint matrix multiplicative 2-approx. for maximization (IMax-Poly)
p

IOpt-Poly with {0, 1} matrix A multiplicative O
e min{r, k} -approximation
(r, k = row, column sparsity of A) additive factors of k: IMin-Poly; (k − 1): IMax-Poly
Inverse versions of min-cost flow
additive 1-approx.; follows from results for IOpt-Poly
and min/max-cost bipartite matching
Inverse matroid-basis optimization polytime (for minimization and maximization)

quite non-trivial and exhibit an interesting range of possibilities in terms of positive (ap-
proximation) algorithmic results and hardness of approximation results. We obtain tight or
nearly-tight guarantees for a variety of integral inverse optimization problems, including the
well-studied inverse shortest path (ISP) problem. Our salient contributions are as follows;
Table 1 summarizes our main results.

We begin by considering ISP (Section 3). We show that the single-commodity version
(Section 3.1), wherein S is a subset of s t paths in a directed graph, is polytime
solvable (Theorem 5). We then consider multicommodity ISP, the generalization where
we have multiple commodities, each specified by an (si , ti ) pair of nodes and a subset
Si of si ti paths, and we seek positive, integral edge costs that ensure that Si is the
unique set of shortest si ti paths for each commodity i. We resolve the status of
node-disjoint multicommodity ISP, where the Si s correspond to node-disjoint subgraphs
(Section 3.2): we devise an additive 1-approximation algorithm (Theorem 6), which is
the best possible guarantee (if P 6=NP) since we show that this node-disjoint version is
NP-hard
(Theorem 7). Our proof also shows that it is NP-hard to obtain a multiplicative
3
2 −  -approximation for multicommodity ISP, for any  > 0.
Our results improve upon the previous-best multiplicative O(|V |)-approximation guaran-
tees for these problems, which follow from the work of [3, 4]. The algorithms in [3, 4] are
for multicommodity ISP, but they apply to the restrictive setting where Si includes a
single si ti -path for every commodity; moreover, they do not yield improved guarantees
even for the special cases of single-commodity ISP or node-disjoint multicommodity ISP.
We also improve upon the factor 89 hardness-of-approximation guarantee in [4].
Motivated by the fact that many combinatorial optimization problems can be cast as
polyhedral optimization problems, in Section 4, we consider a broad generalization of
integral inverse discrete optimization, namely integral inverse polyhedral optimization.
Here, we are given a polytope P ⊆ Rn explicitly, and the set S is replaced by a set X of
extreme points of P; we seek a positive, integral cost vector c ∈ Zn that induces X as the
unique set of extreme-point optimal solutions to the problem of optimizing (minimizing
or maximizing) cT x over x ∈ P. We obtain approximation guarantees for integral inverse
polyhedral optimization that depend on the structure of the constraint matrix A defining
P. When A is totally unimodular (TU), we obtain an additive 1-, or multiplicative 2-
approximation (see Theorem 8), and for a general {0, 1} matrix A, our approximation
factor depends on the row and/or column sparsity of A (see Theorem 9). As corollaries

ESA 2018
1:4 Algorithms for Inverse Optimization Problems

of these results, we obtain additive 1-approximation algorithms for the integral inverse
versions of min-cost flows and max/min-cost bipartite matchings.
Similar to ISP, integral inverse min-cost flow (IMCF) captures the optimization problem
encountered in the context of spanning-tree protocols (STPs) – e.g., rapid STP, multiple
STP etc. – which route using a shortest-path tree rooted at a given node s under the
assigned link weights; enforcing a prescribed routing tree rooted at s by choosing small,
positive, integer link lengths is then an IMCF problem, and in fact, the special case
involving a single source and infinite (or equivalently, very large) capacities. This link-
weight assignment problem was studied in [15, 16], who prove upper bounds on the
optimum value (in a more general setting). We show that this single-source IMCF problem
is polytime solvable, which implies that we can solve this link–weight assignment problem
in polynomial time.
It is illuminating to view integral inverse polyhedral optimization (IOpt-Poly) geometrically.
The set of cost vectors that yield X as extreme-point optimal solutions in P, form a
polyhedral cone; a cost vector in the interior of this cone yields X as the unique set of
extreme-point optimal solutions. Thus, the goal in IOpt-Poly is to find a shortest (in k.k∞ -
norm) positive, integral vector in the interior of this cone (if one exists). Viewed from this
perspective, integral inverse polyhedral optimization can be seen as a problem in the field
of geometry of numbers and in the same vein as the important shortest-vector-problem in
lattices. We believe that this geometric connection makes IOpt-Poly an appealing problem
of independent interest meriting further study.
In Section 5, we consider integral inverse matroid-basis optimization. Here, S is a
collection of bases of a matroid, and we seek positive, integer costs on the elements under
which S is the unique set of optimal bases. We give a polytime algorithm for this problem
(Theorem 12).

Our techniques are versatile and yield results for various variants (see Section 6), including,
most notably, integral inverse optimization under two other commonly considered objectives
in the literature: (1) `p -norm minimization, where we seek to minimize kckp ; and (2) distance
minimization, where we seek to minimize the perturbation kc − c(0) k∞ of an integral “base”
vector c(0) . Our results typically also hold in an implicit model, where the input specifies a
(potentially exponential-size) set S implicitly by listing the elements in terms of its support.
Most prior results on inverse optimization, with the exception of ISP, are obtained in the
setting where S consists of a single solution x̂ (with [26, 28] being exceptions), which is not
required to be the unique optimal solution, and the objective is to minimize kc − c(0) k∞ (or
kc − c(0) kp for some other p), with c fractional. This setting is significantly simpler than the
integral inverse optimization setting we consider. In particular, it is not hard to see that,
as noted in [2], even for a general inverse polyhedral optimization problem, one can: (a)
utilize the complementary slackness (CS) conditions from LP theory to encode the problem
of finding a suitable cost vector c as another LP (or a convex program for `p norms); or (b)
use the ellipsoid method to solve the LP that directly encodes that x̂ has optimal objective
value among all x ∈ P, given an optimization/separation oracle for P. This work therefore
focuses on obtaining faster algorithms for the integral inverse optimization problem.
In contrast, in the integral inverse optimization setting, two distinct sources of difficulty
arise that do not appear in the above setup. First, even computing a suitable fractional cost
vector is non-trivial due to the uniqueness constraint. For instance, in inverse polyhedral
optimization, this entails discerning if the given solutions form the extreme points of a face
of the given polytope, and determining how to encode, and separate over, the constraints
enforcing uniqueness. Second, rounding a fractional cost vector poses the difficulty that we
S. Ahmadian et al. 1:5

need to coordinate things so as to simultaneously ensure that all solutions in S continue

to have the same cost, and solutions not in S remain non-optimal solutions. This creates
unique challenges, and we leverage tools from optimization theory, polyhedral theory, and
recent results in discrepancy theory to circumvent these difficulties and obtain our results.
An interesting and notable implication of our work is that, in many cases, imposing integral
costs does not significantly impact the achievable performance guarantees.
Our array of results allude to the richness of integral inverse optimization problems. While
our work makes significant progress towards understanding these problems, it also opens up
various directions for further research, such as investigating the inverse-optimization versions
of NP-hard optimization problems.

Related work. Inverse problems were initially extensively studied in geophysics for the
estimation of model parameters (see, e.g., [23]). Since then there has been a great deal of
work in inverse optimization in the optimization community (see, e.g., the survey [17]). In the
optimization community, Burton and Toint [9] (see also [8]) were the first to consider inverse
optimization problems. They introduced the the `2 -norm distance-minimization variant
of ISP,where we seek to minimize kc − c(0) k2 , where c(0) is a base vector, while allowing
for fractional cost vectors, and do not require the given paths to be the unique shortest
paths. They motivate ISP from applications in traffic modeling and seismic tomography,
and suggest the extension to the `1 and `∞ norms. Ben-Ameur and Gordin [3] and Bley [4]
study (among other problems) ISP under the constraints of positive, integral edge costs,
and uniqueness of the given paths (i.e., integral ISP), motivated by its applications to
shortest-path routing protocols. These give algorithms having
multiplicative approximation
ratios of O min{|V |/2, (maximum length of a given path)} , and [4] also shows that it is
NP-hard to obtain an approximation ratio better than 9/8. Other ISP variants have also
been investigated [2, 4, 7, 11, 12, 13, 25].
Following initial work on inverse shortest paths, algorithms were developed for the
inverse-optimization versions of other combinatorial optimization problems, such as minimum
spanning tree, min-cost flow, min-cut, matroid intersection, and general inverse polyhedral
optimization (also called inverse linear programming [29, 30]); see [17] for details. Most of
this work pertains to the distance-minimization problem when we allow fractional costs, and
only a single solution is given ([26, 28] are exceptions that consider multiple solutions) that
is not required to be the unique optimal solution. These papers focus on developing fast
combinatorial algorithms. Ahuja and Orlin [2] unify and generalize many of these results.
They note that inverse polyhedral optimization can be solved in the above setting by solving
a suitable LP: a compact LP encoding this can be obtained by utilizing the CS conditions,
and even the (huge) LP that directly encodes that the given solution be optimal can be solved
via the ellipsoid method. They show that in various cases, the compact LP leads to an LP
similar to the one for optimizing over P, and hence one can obtain combinatorial algorithms
for various inverse discrete optimization problems. Similar results were also obtained by [27].
We remark that while we also solve an LP to obtain fractional cost vectors en route to
obtaining integral cost vectors, a crucial difference in our setting is that we need to devise
suitable ways of encoding (and separating over) the constraint that the costs induce the
given (multiple) solutions as the unique optimal solutions. Our algorithms for integral inverse
polyhedral optimization require either a face oracle for P, which determines if the given set
X of extreme points forms a face of P, or an oracle that determines if all maximal/minimal
points on a face of P have the same cost under a given cost vector. Devising a face oracle is
related to the problem of enumerating all vertices (i.e., extreme points) of a polyhedron, or

ESA 2018
1:6 Algorithms for Inverse Optimization Problems

all vertices on its optimal face (under an objective function), with each new vertex being
output in polynomial delay. (For instance, we can decide if X forms a face by determining if
the minimal face of P containing X contains at least |X| + 1 vertices.) Such procedures are
known for various polyhedra such as network-flow polyhedra [20], general 0/1 polytopes [10],
simplicial and simple polyhedra [6, 14], but this is NP-hard for general 0/1 polyhedra [5].

2 Problem definitions, notation, and preliminaries

For an integer n, we use [n] to denote {1, . . . , n}. Given z ∈ RE , and
S ⊆ E, we use
z(S)
P
to denote e∈S ze . We use bzc and dze to denote the vectors bze c e∈E and dze e e∈E
respectively.

Inverse discrete optimization. An inverse discrete optimization problem involves an un-

derlying discrete optimization problem specified in terms of a ground set E and a collection
F ⊆ 2E of feasible solutions, and a subset S ⊆ F of feasible solutions to the optimization
problem. We seek a cost vector c ∈ RE such that the solutions in S are the optimal solutions
to the underlying optimization problem. Formally, in an inverse minimization problem,
the underlying optimization problem is a minimization problem, and we seek a cost vector
c ∈ RE such that c(S) = minF ∈F c(F ) for all S ∈ S. In an inverse maximization problem,
the underlying optimization problem is a maximization problem, and we seek c ∈ RE such
that c(S) = maxF ∈F c(F ) for all S ∈ S. More precisely, motivated by applications of the
inverse-shortest-path problem in the context of shortest-path network-routing protocols in
telecommunication, we impose the following requirements on the cost vector c.
(C1) Positive, integer costs: ce ≥ 1, ce ∈ Z for all e ∈ E;
(C2) Unique optimal solutions: For inverse minimization, we require c(S) = minF ∈F c(F ) <
c(F 0 ) for all S ∈ S and F 0 ∈ F \ S; for inverse maximization, we require c(S) =
maxF ∈F c(F ) > c(F 0 ) for all S ∈ S and F 0 ∈ F \ S;
Our goal is to find a vector c satisfying 1 and 2 that minimizes kck∞ . We call this an integral
inverse optimization problem; we drop “integral” when it is clear from the context.
The uniqueness condition 2 is often important in applications, where the inverse optimiza-
tion problem is used to infer or perturb some system parameters so as to explain or impose
a set S of observations, since we would like to do so without introducing spurious solutions.
We impose c ≥ 1 as a normalization requirement: this prevents one from arbitrarily scaling a
vector satisfying 2 to obtain another feasible solution. Integrality is a discretization condition
that ensures that we are optimizing over a closed set (note that 2 leads to an open feasible
region). (Without an underlying objective such as minimizing kck∞ , 1 becomes redundant
as one can always scale a rational vector c to satisfy 1.)
We allow for specifying exponentially large (in the natural input size) solution sets S
(thus obtaining greater modeling power), by also considering the following implicit model for
specifying S: we specify a set U of elements, which implicitly describes the set S = {S ∈ F :
S ⊆ U } of feasible solutions. For example, in the implicit version of inverse shortest paths,
U is a set of arcs and S comprises all s t paths contained in U ; so a solution is a positive,
integral cost vector such that the collection of shortest s t paths is precisely S. Our results
typically apply to both models, and the underlying arguments are similar.
Our techniques are versatile and yield results for other variants of the above integral
inverse optimization problem such as, most notably,
(1) the `p -norm version: find a vector c satisfying 1, 2 that minimizes kckp
(2) the distance-minimization version (with `∞ norm): the input specifies a “base” vector
c(0) ∈ ZE + , and we seek a cost vector c satisfying 1, 2 that minimizes kc − c
(0)
k∞ .
S. Ahmadian et al. 1:7

At a high level, this follows because our results are obtained by first obtaining an (near-)
optimal fractional cost vector c∗ satisfying 1, 2 via an LP (or, for `p -norms where 1 < p < ∞,
via a convex program) and then rounding it to a feasible integral vector c̃ while introducing
an additive O(1) rounding error; this rounding error easily translates to a multiplicative
approximation for problems (1), (2). The following theorem makes this precise.

I Theorem 1. Let c∗ ∈ RE be a cost vector satisfying c∗e ≥ 1 ∀e ∈ E. Let c̃ ∈ ZE be a vector

satisfying 1, 2.
(i) Let O∗ p := min { kckp : c satisfies 1, 2}. Suppose that kc∗ kp ≤ O∗ p +, and c̃e ≤ αc∗e +β
p
for all e ∈ E. Then, kc̃kp ≤ (α + β)(1 + )O∗ p ; if  < 2(α+β)O∗ p , this implies that
1

kc̃kp ≤ dα + βe O∗ p .
∗ ∗
(ii) Let Odist := min { kc − c(0) k∞ : c satisfies 1, 2}. Suppose that Odist > 0,
∗ (0) ∗ ∗ (0) ∗ ∗
kc −c k∞ ≤ Odist , and kc̃−c k∞ < β. Then, kc̃−c k∞ ≤ Odist +dβe−1 ≤ dβe Odist .

Inverse polyhedral optimization. Many combinatorial optimization problems have conve-

nient polyhedral descriptions and can be modeled via linear programs that have integral
optimal solutions; this indeed holds for the problems whose integral inverse optimization
versions we investigate. With this in mind, we consider the following general inverse polyhe-
dral optimization problem, which is a natural abstraction of an inverse discrete optimization
problem. We are given a polytope P ⊆ RE + with explicitly specified constraints, and a
collection X ⊆ P of extreme points of P. In integral inverse polyhedral minimization
(IMin-Poly), we seek a cost vector c ∈ RE that minimizes kck∞ and satisfies 1, and (C2):
cT x̂ = minx∈P cT x < cT x0 for every x̂ ∈ X and every extreme point x0 of P not in X.
Similarly, in integral inverse polyhedral maximization (IMax-Poly), we seek c ∈ RE that
minimizes kck∞ and satisfies 1, and (C2’): cT x̂ = maxx∈P cT x > cT x0 for every x̂ ∈ X and
every extreme point x0 of P not in X. If the underlying discrete optimization problem is
captured by the problem of optimizing over P (e.g., if extreme points of P correspond to
feasible solutions to the discrete optimization problem), then this integral inverse polyhedral
optimization problem captures the integral inverse discrete optimization problem defined
 consider the implicit version, wherein we are given U ⊆ E, which
earlier. As before, we also
implicitly
specifies X := extreme points x̂ of P s.t. {e : x̂e > 0} ⊆ U , x̂ is maximal/minimal
in P . By x̂ being maximal in P, we mean that there is no x ∈ P such that x ≥ x̂, x 6= x̂;
minimality is similarly defined. The set X must be maximal for IMax-Poly, and minimal for
IMin-Poly, as only such points can be optimal solutions since c > 0.
We say that X forms a face of P, if X is precisely the set of extreme points of some face
of P. Integral inverse polyhedral optimization can be stated geometrically as: determine if X
forms a face, say F , of P, and if so, find a positive, integral vector (if one exists) of minimum
`∞ norm in the interior of the polyhedral cone of vectors yielding F as the optimal face.

Difference systems. We often need to obtain a solution to a system of constraints of the

following form, called a difference system with bounds, involving n variables z1 , . . . , zn :

zi − zj ≤ dij ∀(i, j) ∈ A, zi ≥ `i ∀i ∈ L, zi ≤ ui ∀i ∈ U (1)

where A ⊆ [n] × [n], L, U ⊆ [n]. The dij s can be arbitrary, so (1) can also incorporate
constraints of the form zi − zj ≥ dij . The following useful result is well known (see, e.g., [1]).

I Theorem 2. We can find a feasible solution to a difference system (1), or detect it is

infeasible, by computing a shortest path in a digraph with |A| + |L| + |U | arcs, n + 1 nodes.
If the data is integral, and (1) is feasible, this yields an integer-valued feasible solution.

ESA 2018
1:8 Algorithms for Inverse Optimization Problems

Further, given costs {bi }ni=1 , we can solve a min-cost flow problem to find an optimal
P
solution to the following LP: minimize i bi zi subject to (1). If this LP has an optimal
solution and the dij s, `i s and ui s are integral, this yields an integer-valued optimal solution.

3 The inverse shortest path problem

In the integral inverse shortest path (ISP) problem, we are given a directed graph D = (V, E),
terminals s, t ∈ V , and a collection S of simple s t paths; we seek positive, integral edge
costs {ce }e∈E such that the paths in S are the unique shortest s t paths under these edge
costs, so as to minimize kck∞ = maxe ce . In multicommodity ISP, we have k commodities,
with each commodity i = 1, . . . , k specified by a pair si , ti ∈ N of terminals, and a collection
Si of si ti paths. We seek positive, integral edge costs {ce }e∈E minimizing kck∞ such that
for each commodity i = 1, . . . , k, the paths in Si are the unique si ti shortest paths under
these edge costs. Clearly, ISP is the special case where k = 1. In the implicit version of
multicommodity ISP, we are given edge-sets E 1 , . . . , E k , which implicitly defines Si to be
the collection of all si ti paths in E i .
We show that ISP is polytime solvable (Section 3.1). For multicommodity ISP (Section 3.2),
we devise an additive 1-approximation algorithm in the setting where the Si s correspond to
node-disjoint subgraphs. Our guarantee is tight, since we show that (even) this special case
of multicommodity ISP is NP-hard to approximate within a factor better than 32 . Previously,
only a multiplicative O(|V |)-approximation guarantee was known for these problems [3, 4],
and a factor 98 hardness-of-approximation was known for general multicommodity ISP [4]. In
Section 6, we show that our techniques yield results for various other ISP variants including:
(1) the `p -norm minimization version; (2) the distance minimization version; and (3) variants
involving shortest-si ti -path distances in the objective or constraints.

3.1 A polynomial time exact algorithm for ISP

We may assume that every edge in D lies on some s t path, as otherwise we can assign
it cost 1, and so can simply delete the edge. Let O∗ denote the optimal value of the ISP
instance. We utilize the following well-known properties of shortest paths.
I Claim 3. Let D = (N, A) be a digraph with nonnegative edge costs {ce }e∈A , and s, t ∈ N .
Suppose that every edge of A lies on some s t path. Let S be a collection of s t paths.
(i) S consists of shortest s t paths (under c) iff there are node potentials {yv }v∈N such
that:
[
yv − yu ≤ cu,v for all (u, v) ∈ A, yv − yu = cu,v for all (u, v) ∈ P. (2)
P ∈S

(ii) Node potentials satisfying (2) exist iff the node potentials obtained by setting
yv = (shortest-s v-path distance) ∀v, satisfy (2).
S
(iii) S comprises shortest s t paths iff every s t path Q ⊆ P ∈S P is shortest s t
path.
If the input is in the explicit model (i.e., S is explicitly given), define E 1 := P ∈S P . By
S

Claim 3 (iii), an ISP instance in the explicit model is feasible only if S includes all s t paths
contained in E 1 . Also, since we seek positive edge costs, E 1 must be acyclic (a directed cycle
must have cost 0 due to (2)), otherwise the ISP instance is infeasible. In the explicit model,
we first check if E 1 contains an s t path not in S. This can be checked in polynomial time
in various ways: for instance, we can use topological sort to count the number of s t paths
S. Ahmadian et al. 1:9

in E 1 and check if this number is |S|. (We can also use depth-first search and backtracking
to enumerate |S| + 1 distinct s t paths in polytime (if they exist); see, e.g., [21].)
In the sequel, we assume that the ISP instance meets these feasibility requirements (so the
explicit and implicit models coincide). Let G1 = (V 1 , E 1 ) be the subgraph induced by E 1 . We
may assume that every edge e ∈ E 1 lies on an s t path contained in E 1 (which holds by def-
inition in the explicit model); otherwise, we can remove e from E 1 and solve the resulting ISP
instance. We consider the following LP-relaxation of the problem with the ce s and node po-
tentials {yv }v∈N as variables. (The objective function and constraints are easily linearized.)

min kck∞ (ISP-P)

1
s.t. max{1, yv − yu } ≤ cu,v ∀(u, v) ∈ E, yv − yu = cu,v ∀(u, v) ∈ E (3)
1 1 1
yv − yu + 1 ≤ c(P ) ∀(u, v) ∈ V × V , ∀u v paths P ⊆ E \ E . (4)

Constraints (3) follow from Claim 3, and ensure that all s t paths in E 1 are shortest s t
paths. Note that if there is no u v path in E \ E 1 , then there is no constraint (4) for (u, v).
We argue below that constraints (4) are valid; this follows because (4) encodes that every
s t path Q not contained in E 1 has length at least 1 + mins t path P :P ⊆E 1 c(P ), and with
integer edge costs, this is equivalent to the condition that every s t path Q not contained
in E 1 is not a shortest s t path.
I Lemma 4. (ISP-P) is a relaxation of ISP.
We can efficiently solve (ISP-P) via the ellipsoid method since we can efficiently separate
over constraints (4) when c ≥ 0 by solving a shortest-path problem. (We can actually avoid
the ellipsoid method and obtain a much more efficient algorithm for ISP. We retain the LP-
based exposition since this extends easily to multicommodity ISP and other variants of ISP.) If
(ISP-P) is infeasible, then the ISP instance is infeasible. Otherwise, let (c∗ , y ∗ ) be an optimal
solution to (ISP-P). Let B ∗ = kc∗ k∞ . Note that O∗ ≥ dB ∗ e. Our rounding algorithm is quite
simple. We first round the {yv∗ } node potentials by solving the following difference system:

byv∗ − yu∗ c ≤ ψv − ψu ≤ dyv∗ − yu∗ e for all (u, v) ∈ V 1 × V 1 .

Notice that ψ = y ∗ is a feasible solution to this difference system, so since the constant terms
in the above inequalities are integers, it has a feasible integer  solution ỹ (Theorem 2). We
set edge costs c̃u,v = ỹv − ỹu for all (u, v) ∈ E 1 , and c̃u,v = c∗u,v for all (u, v) ∈ E \ E 1 .


I Theorem 5. Vector c̃ satisfies bc∗ c ≤ c̃ ≤ dc∗ e, and is hence an optimal solution to ISP.

3.2 Multicommodity ISP with node-disjoint subgraphs

We now consider multicommodity ISP, where the edges in the Si s induce node-disjoint
subgraphs. More precisely, if the input is in the explicit model, define E i := P ∈Si P .
S

Let Gi = (V i , E i ) be the subgraph induced by E i . We consider the setting where the

V i s are disjoint; we call this node-disjoint multicommodity ISP. As before, by Claim 3, a
muticommodity ISP instance in the explicit model is feasible only if Si includes all si ti
paths contained in E i for all i = 1, . . . , k, which can be verified efficiently. Moreover, each
E i must be acyclic, and we may assume that for every i, and every e ∈ E i , there is some
si ti path contained in E i that contains e. We prove the following results, which together
resolve the complexity of node-disjoint multicommodity ISP.
I Theorem 6. There is an additive 1-approximation for node-disjoint multicommodity ISP.

ESA 2018
1:10 Algorithms for Inverse Optimization Problems

I Theorem 7. Node-disjoint multicommodity ISP is NP-hard. Moreover, it is NP-hard to

obtain a multiplicative ( 23 − )-approximation for any  > 0.

4 Inverse polyhedral optimization

Recall that in an abstract integral inverse polyhedral optimization problem, we are given
a polytope P ⊆ RE + with explicitly specified constraints, and a set X of extreme points
of P. We want to find a positive, integral cost vector c ∈ RE minimizing kck∞ such that:
(i) in inverse polyhedral minimization (IMin-Poly), X is the set of extreme-point optimal
solutions to minx∈P cT x; and (ii) in inverse polyhedral maximization (IMax-Poly), X is the
set of extreme-point optimal solutions to maxx∈P cT x. In the implicit version, we are given
U ⊆ E, which defines X to be all extreme points x̂ of P such that {e : x̂e > 0} ⊆ U , and x̂
is maximal (for IMax-Poly) or minimal (for IMin-Poly) in P.
Our approach consists of two main steps. We first find an optimal fractional cost vector
c∗ ≥ 1, and then round this. While prior work also deals with obtaining such a fractional
cost vector, in our case, this step is significantly more complicated due to both the existence
of multiple solutions in X, and the requirement that these be the unique optimal solutions.
Let Ax ≤ b denote the constraints of P (including nonnegativity). Let K be an integer such
1
that all entries of A, b, and all extreme points of P are integer multiples of K . We can
compute K with log K = poly(input size). (If A is totally unimodular (TU) and b is integral,
1
then K = 1.) So for any solution c to IMax-Poly or IMin-Poly, we have |cT x̂ − cT x| ≥ K for
0 ∗
any x̂ ∈ X and x ∈ / X. For IMin-Poly, we solve the following LP-relaxation to find c . (For
IMax-Poly, (6), and the arguments below, are modified appropriately.)

ce ≥ 1 ∀e ∈ E, cT x̂ = λ ∀x̂ ∈ X
(
(5)
(IMin-P) min kck∞ s.t. 1
cT x̂ ≥ λ + ∀x̂ : x̂ is an extreme point of P, x̂ ∈
/ X. (6)
K
To solve (IMin-P) in the explicit model, we require a face oracle for P. We first use this to
determine if X forms a face F of P; if not, then the inverse problem is infeasible. Otherwise,
letting J be the set of constraints that are tight for all x ∈ X, the face F is given by
F = {x ∈ P : (Ax)i = bi ∀i ∈ J}. Further, any extreme point x ∈ P \ X does not lie in F , so
1
there is some i ∈ J such that (Ax)i < bi , and hence (Ax)i ≤ bi − K . Our separation oracle
for (IMin-P) is as follows. Constraints (5) can be directly checked. For (6), we consider every
1

i ∈ J and check that the minimum value of cT x over the set x ∈ P : (Ax)i ≤ bi − K is at
1
least λ + K . This can be done in polynomial time.
In the implicit setting, to separate over constraints (5), we require what we call a
minimality oracle (or maximality oracle, for IMax-Poly), which given a set U ⊆ E and a cost
vector c, determines if every minimal (extreme) point of P whose support lies in U has the
same (minimum) cost. To verify if constraints (6) hold, first note that if x0 ∈
/ X is an extreme
0 T 0 1
point supported on U , then there is some x̂ ∈ X with x̂ ≤ x , and so c x ≥ cT x̂ + K . So we
0
only need to check if (6) holds for extreme points x not supported on U ; this can be done
by the same procedure as for the explicit model, taking J = E \ U . The problem of devising
a minimality/maximality oracle is itself an interesting and non-trivial problem for various
combinatorial optimization problems. We show how to devise such an oracle for min-cost
flow and bipartite matching (Theorems 10 and 11). Note that for a polytope P of the form
{x : Ax = b, x ≥ 0}, any two feasible points are incomparable; so the face formed by X is
simply F = {x ∈ P : xe = 0 ∀e ∈ / U }, and we can obtain a minimality/maximality oracle by
checking if the minimum and maximum values of cT x over F are equal.
S. Ahmadian et al. 1:11

The next step is to round c∗ to obtain an approximately optimal integral cost vector. We
show how to do this in two settings, when the constraint matrix A is TU, and when A is a
sparse {0, 1}-matrix. In both cases, we round an optimal solution to the dual of the problem
of optimizing c∗T x over P but the details and bounds obtained differ.

I Theorem 8. Let P = {x ∈ RE : Ax ≥ b, x ≥ 0}, where A is TU, and b is integral. We

can round an optimal fractional solution c∗ to the inverse problem to obtain: (a) an additive
1-approximation for IMin-Poly; and (b) a multiplicative 2-approximation for IMax-Poly.

I Theorem 9. Let A ∈ {0, 1}m×n have row sparsity r and column sparsity k, where n = |E|.
(Row sparsity is the maximum number of nonzero entries in a row of A; column sparsity is the
maximum number of nonzero entries in a column of A.) Let A1 and A2 be submatrices of A
with n columns, whose rows partition [m]. We can round an optimal fractional solution c∗ to
the inverse problem to obtain the following guarantees
 (in both implicit and explicit models).

(a) Additive (k −1)-approx. for IMax-Poly with P = x  ∈ RE : A1 x = b1 , A2 x ≤ b2 , x ≥ 0 .
(b) Additive
k-approximation for IMin-Poly with P = x ∈ RE : A1 x = b1 , A2 x ≥ b2 , x ≥
0 . 
(c) Multiplicative β-approximation for IMax-Poly and IMin-Poly, where we have β = min k +
√ p
O(1), O( r log n), O( k min(log(kr), log n)) .

4.1 Applications to inverse min-cost flow and inverse bipartite

matching
Inverse min-cost flow. In the integral inverse min-cost flow (IMCF) problem, we are given
a directed graph D = (N, E), integer bounds 0 ≤ `e ≤ ue on every edge e, integer demands
{bv }v∈N (which could be arbitrary) such that b(N ) := v∈N bv = 0, and a set E 1 ⊆ E of
P

edges. A flow in D is a vector x ∈ RE satisfying

x δ in (v) − x δ out (v) = bv ∀v ∈ N,

`e ≤ xe ≤ ue ∀e ∈ E. (7)
P
Given edge costs {ce }e∈E , the cost of a flow x is e ce xe . We seek positive, integral edge
costs {ce }e∈E minimizing kck∞ so that the set of min-cost integral flows is precisely the set
of acyclic integral flows supported on E 1 . As with ISP, we may assume that every e ∈ E 1 is
used by some feasible flow supported on E 1 , and then, we may further assume that E 1 is
acyclic, as otherwise the inverse problem is infeasible.
P
The min-cost flow problem is given by the LP: min e ce xe subject to (7). The constraint
matrix specifying (7) is TU (see, e.g., [22]), so IMCF is an instance of IMin-Poly with a TU
constraint matrix. Since E 1 is acyclic, any two distinct feasible flows supported on E 1 are
incomparable, so it is easy to obtain a minimality oracle and solve (IMin-P). We then obtain
the following positive result in the above implicit model as a corollary of Theorem 8 (a). We
discuss the explicit model in the full version. where we also show that IMCF is polytime
solvable in certain cases, such as, the single-source setting with no (or equivalently, very
large) capacities. As noted earlier, in the context of spanning-tree protocols, this implies
that in polynomial time, we can find the smallest positive integer link weights that enforce a
prescribed routing tree as a shortest-path tree rooted a given node s.

I Theorem 10. There is an additive 1-approximation for IMCF in the implicit model.

Inverse bipartite matching. In inverse bipartite matching, the input is an undirected bi-
partite graph G = (V, E). In integral max-cost bipartite matching (IMax-BMat), we have a
collection M1 , . . . , Mk of maximal matchings, and we seek positive, integral edge costs {ce }e∈E

ESA 2018
1:12 Algorithms for Inverse Optimization Problems

minimizing kck∞ so that M1 , . . . , Mk are the unique max-cost bipartite matchings in G. In the
implicit model, we are given E 1 ⊆ E, and we require that the set of max-cost bipartite match-
ings be the set of maximal matchings contained in E 1 . (Max-cost matchings
must be maximal.)
P
The max-cost bipartite matching LP is: max c x
e e e s.t. x δ(v) ≤ 1 ∀v ∈ V, x ≥ 0.
We also consider integral min-cost bipartite matching (IMin-BMat), where we are given per-
fect matchings M1 , . . . , Mk , and we seek positive integral edge costs {ce }e∈E minimizing kck∞
such that these are the unique min-cost perfect matchings in G. In the implicit model, we are
given E 1 ⊆ E, and the set of min-cost perfect matchings should be the set of perfect matchings
contained in E 1 . The min-cost
perfect matching problem can be modeled by the following
P
LP: min e ce xe s.t. x δ(v) = 1 ∀v ∈ V, x ≥ 0. The constraint matrix in the above
LPs is TU and has column sparsity 2. We devise a face oracle for IMax-BMat and IMin-BMat
in the explicit setting, and a maximality oracle for IMax-BMat in the implicit setting when
E 1 = E by exploiting various structural properties of bipartite matchings. (A minimality
oracle for IMin-BMat is easy since the corresponding polytope is defined by equations and
nonnegativity constraints.) The maximality oracle for IMax-BMat determines if there exist
two maximal matchings of different costs; we note that the related problem of finding a
min-cost maximal matching is NP-hard. Theorems 8(a) and 9(a) then yield the following.

I Theorem 11. We can obtain additive guarantees of 1 for IMin-BMat, and IMax-BMat in
the explicit setting, and IMax-BMat in the implicit setting when E 1 = E.

5 Inverse matroid-basis optimization

We consider the integral inverse min-cost matroid basis (IMin-Basis) and integral inverse
max-cost matroid basis (IMax-Basis) problems. In both problems, the input is a matroid
M = (E, I) (specified by an independence oracle) and a collection S of bases of M . The goal
is to find positive, integral costs {ce }e∈E such that the bases in S are the unique optimal
bases under these costs, so as to minimize kck∞ . More precisely, in IMin-Basis, we require
that the bases in S be the unique min-cost bases under the {ce } costs, while in IMax-Basis, we
require that the bases in S be the unique max-cost bases under the {ce } costs. In the implicit
model, we are given U ⊆ E, which implicitly specifies S to be all bases of M contained in U .

I Theorem 12. We can solve IMin-Basis and IMax-Basis in polynomial time.

6 Extensions and variants

Our techniques are versatile and yield guarantees for other variants of integral inverse
optimization mentioned in Section 2, including the `p -norm version (minimize kckp ) and
distance-minimization version (minimize kc − c(0) k∞ , where c(0) ∈ ZE
+ ) problems; for these
two problems our guarantees follow by simply combining our earlier results with Theorem 1.

Inverse shortest paths. We obtain multiplicative guarantees of 2 and 3 respectively for

the `p -norm variant of ISP and multicommodity ISP respectively, and obtain the optimal
solution and an additive guarantee of 1 for the distance-minimization variants. Bley [4]
considered the ISP variant where we seek positive, integral costs so as to minimize maxi=1,...,k
(shortest-si ti -path distance). A related variant specifies integer upper bounds {Di }ki=1 on
the shortest-si ti -path distances, and seeks a positive, integral cost vector c that respects
these bounds and minimizes kck∞ . The guarantees in Theorems 5, 6 hold for both variants.
S. Ahmadian et al. 1:13

I Theorem 13. We obtain the following multiplicative guarantees for the `p -norm and
distance-minimization versions of integral inverse polyhedral optimization.
(a) 3-approximation for IMin-Poly with P = {x ∈ RE : Ax ≥ b, x ≥ 0}, where A is TU and
b is integral.

(b) (k + 1)-approximation
for IMax-Poly with P = x ∈ RE : A1 x = b1 , A2 x ≤ b2 , x ≥ 0 ,
where AT = AT1 AT2 is a {0, 1} matrix, and A has column sparsity k.
 E

(c) (k + 2)-approximation for

of IMin-Poly with P = x ∈ R : A 1 x = b 1 , A 2 x ≥ b2 , x ≥ 0 ,
T T T
where A = A1 A2 is a {0, 1} matrix, and A has column sparsity k.
In the explicit model, we assume that we have a face oracle for P. In the implicit model, we
assume that we have a minimality/maximality oracle for P.

I Theorem 14. (a) There is a multiplicative 2-approximation algorithm for the `p -norm
minimization versions of IMin-Basis and IMax-Basis. (b) The distance-minimization versions
of IMin-Basis and IMax-Basis can be solved exactly in polytime.

References
1 Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows: theory,
algorithms, and applications. Prentice hall, 1993.
2 R.K. Ahuja and J.B. Orlin. Inverse optimization. Oper. Res., 49:171–783, 2001.
3 W. Ben-Ameur and E. Gourdin. Internet routing and related topology issues. SIAM J.
Discrete Math., 17:18–49, 2004.
4 A. Bley. Inapproximability results for the inverse shortest paths problem with integer
lengths and unique shortest paths. Networks, 50:29–36, 2007.
5 Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Hans Raj Tiwary. The negative cy-
cles polyhedron and hardness of checking some polyhedral properties. Annals of Operations
Research, 188(1):63–76, 2011.
6 David Bremner, Komei Fukuda, and Ambros Marzetta. Primal-dual methods for vertex
and facet enumeration. Discrete & Computational Geometry, 20(3):333–357, 1998.
7 D. Burton, W. Pulleyblank, and Ph. L. Toint. The inverse shortest paths problem with
upper bounds on shortest paths costs. In Network optimization, pages 156–171. Springer,
1996.
8 D Burton and Ph L Toint. On the use of an inverse shortest paths algorithm for recovering
linearly correlated costs. Mathematical Programming, 63(1):1–22, 1994.
9 D. Burton and Ph.L. Toint. On an instance of the inverse shortest paths problem. Math.
Program., 53:45–61, 1992.
10 Michael R Bussieck and Marco E Lübbecke. The vertex set of a 01-polytope is strongly
p-enumerable. Computational Geometry, 11(2):103–109, 1998.
11 Mikael Call and Kaj Holmberg. Complexity of inverse shortest path routing. In INOC,
pages 339–353. Springer, 2011.
12 Robert B Dial. Minimal-revenue congestion pricing part i: A fast algorithm for the single-
origin case. Transportation Research Part B: Methodological, 33(3):189–202, 1999.
13 Robert B Dial. Minimal-revenue congestion pricing part ii: An efficient algorithm for the
general case. Transportation Research Part B: Methodological, 34(8):645–665, 2000.
14 Martin E Dyer. The complexity of vertex enumeration methods. Mathematics of Operations
Research, 8(3):381–402, 1983.
15 F. Grandoni, G. Nicosia, G. Oriolo, and L. Sanità. Stable routing under the spanning tree
protocol. Operations Research Letters, 38:399–404, 2010.
16 N. Haehnle, L. Sanità, and R. Zenklusen. Stable routing and unique-max coloring on trees.
SIAM J. Discret. Math, 27:109–125, 2013.

ESA 2018
1:14 Algorithms for Inverse Optimization Problems

17 C. Heuberger. Inverse combinatorial optimization: A survey on problems, methods, and

results. J. Combin. Optim., 8:329–361, 2004.
18 Garud Iyengar and Wanmo Kang. Inverse conic programming with applications. Operations
Research Letters, 33(3):319–330, 2005.
19 Gertrud Neumann-Denzau and Jörn Behrens. Inversion of seismic data using tomographical
reconstruction techniques for investigations of laterally inhomogeneous media. Geophysical
Journal International, 79(1):305–315, 1984.
20 J. Scott Provan. Efficient enumeration of the vertices of polyhedra associated with network
LP’s. Math. Program., 63(1):47–64, 1994.
21 Robert C Read. Bounds on backtrack algorithms for listing cycles, paths and spanning
trees. Networks, 5:237–252, 1975.
22 Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
23 Albert Tarantola. Inverse problem theory and methods for model parameter estimation.
SIAM, 2005.
24 H.R. Varian. Revealed preference. Samuelsonian Economics and the Twenty-first Century,
pages 99–115, 2006.
25 S. Xu and J. Zhang. An inverse problem of the weighted shortest path problem. Japan J.
Indust. Appl. Math., 12:47–59, 1995.
26 J. Zhang and M.C. Cai. Inverse problem of minimum cuts. Mathematical Methods of Oper.
Res., 47:51–58, 1998.
27 J. Zhang and Z. Liu. A general model of some inverse combinatorial optimization problems
and its solution method under l-infinity norm. J. Combin. Optim., 6:207–227, 2002.
28 J. Zhang and Z. Ma. Solution structure of some inverse combinatorial optimization prob-
lems. J. Combin. Optim., 3:127–139, 1999.
29 Jianzhong Zhang and Zhenhong Liu. Calculating some inverse linear programming prob-
lems. Journal of Computational and Applied Mathematics, 72(2):261–273, 1996.
30 Jianzhong Zhang and Zhenhong Liu. A further study of inverse linear programming prob-
lems. Journal of Computational and Applied Mathematics, 106:345–359, 1999.