Fractional 0–1 programming and Submodularity

Shaoning Han^a, Andrés Gómez^a and Oleg A. Prokopyev^b,∗¹¹1^∗Corresponding author. Phone: +1-412-624-9833. E-mail: [email protected]. ^aIndustrial & Systems Engineering, University of Southern California, Los Angeles, CA 90089
^bIndustrial Engineering, University of Pittsburgh, Pittsburgh, PA 15261

Abstract.

In this note we study multiple-ratio fractional 0–1 programs, a broad class of $\mathcal{NP}$ -hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0–1 programs can be found via simple greedy algorithms. Keywords Fractional 0–1 programming, hyperbolic 0–1 programming, multiple ratios, single ratio, submodularity, assortment optimization, facility location, greedy algorithm.

1. Introduction

We consider a multiple-ratio fractional 0–1 program given by:

\max_{x\in\mathcal{F}}\;\sum_{k\in M}\frac{\sum_{i\in N}a_{ki}x_{i}}{b_{k0}+\sum_{i\in N}b_{ki}x_{i}},

(1)

where $M=\{1,\dots,m\}$ , $N=\{1,\dots,n\}$ and $\mathcal{F}:=\{x\in\{0,1\}^{n}:\ Dx\leq d\}$ for given $D\in\mathbb{R}^{q\times n}$ and $d\in\mathbb{R}^{q}$ . Problem (1) is often referred to as a multiple-ratio hyperbolic 0–1 program. Problems of the form (1) can also be viewed as a class of set-function optimization problems that seek a subset $S$ of $N$ with its indicator variable $\mathbbm{1}_{S}\in\mathbb{R}^{n}$ , where the $i$ -th element of $\mathbbm{1}_{S}$ is 1 if and only if $i\in S$ .

Throughout the paper, we make the following assumptions:

A1: The denominator is strictly positive for each ratio in (1), i.e., $b_{k0}+\sum_{i\in N}b_{ki}x_{i}>0$ for all $k\in M$ and all $x\in\mathcal{F}$ .

A2: $a_{ki}\geq 0$ , $b_{k0}\geq 0$ and $b_{ki}>0$ for all $k\in M$ and $i\in N$ .

Assumption A1 is standard in fractional optimization [10, 11, 34]. In particular, it ensures that the objective function is well defined. Assumption A2 is not too restrictive as it naturally holds in many application settings, see examples in [11], including those considered in this note, see Section 4. Finally, for our results developed in this note we also require an additional relatively mild assumption on the structure of the feasible region, $\mathcal{F}$ , in (1); it is formalized in Section 2.

Applications of single- and multiple-ratio fractional 0–1 programs as in (1) appear in many diverse areas. For example, Méndez-Díaz et al., [35] discuss an assortment optimization problem under mixed multinomial logit choice models (MMNL). Tawarmalani et al., [49] consider a facility location problem, where a fixed number of facilities need to be located to service customers locations with the objective of maximizing a market share. Arora et al., [2] study a class of set covering problems in the context of airline crew scheduling that aim at covering all flights operated by an airline company. Furthermore, many combinatorial optimization problems can be formulated in the form (1) including the minimum fractional spanning tree problem [13, 50], the maximum mean-cut problem [26, 42] and the maximum clique ratio problem [45]. More application examples can be found in the studies by [8, 18, 14], the recent survey by Borrero et al., [11] and the references therein.

Generally speaking, problem (1) is $\mathcal{NP}$ -hard even in the case of a single ratio [24, 40]. Moreover, this problem is even hard to approximate, see, e.g., [40]. Also, Rusmevichientong et al., [44] show that for the unconstrained multi-ratio problem, there is no approximation algorithm with polynomial running time that has an approximation factor better than $\mathcal{O}(1/m^{1-\delta})$ for any $\delta>0$ . Other related theoretical computational results are discussed in [40, 41].

Exact solution methods for (1) encompass mixed-integer programming reformulations [10, 18, 34], branch and bound algorithms [49], and other enumerative methods [11, 22, 23]. However, due to $\mathcal{NP}$ -hardness of (1), these methods do not scale well when the size of the problem increases. Motivated by these computational complexity considerations, a number of studies rely on approximation schemes and heuristics for solving (1). Rusmevichientong et al., [43], Mittal and Schulz, [36] and Désir et al., [16] all propose approximation algorithms for assortment optimization under the MMNL model when the number of customer segments, $m$ , is fixed. Amiri et al., [1] develop a heuristic algorithm based on Lagrangian relaxation in the context of stochastic service systems. Prokopyev et al., 2005b [41] present a GRASP-based (Greedy Randomized Adaptive Search) heuristic for solving the cardinality constrained problems. Finally, simple greedy algorithms are also used in the literature [19, 28]. However, it is often not well understood when such algorithms perform well.

Contributions and outline. The remainder of the note is organized as follows. In Section 2, we overview some necessary preliminaries and formulate our model (1) in terms of set functions.

In Section 3, we provide the main result of the note that characterizes the submodularity of a single ratio. Submodularity is often a key property for devising approximation algorithms [20, 38]. If the objective function can be identified as a submodular function, then simple greedy algorithms are capable of delivering high-quality solutions. In fact, it is possible to obtain $(1-e^{-1})$ -approximations under a variety of feasible regions – independently of the number of the ratios, $m$ , involved–, thus improving over existing approximation methods for (1). We also discuss the connections between submodularity and monotonicity in the context of fractional 0–1 optimization.

In Section 4, we consider our theoretical results in the context of two applications – the assortment optimization and the $p$ -choice facility location problems. For the assortment optimization problem, our results suggest that submodularity is linked to a phenomenon known as cannibalization [37], and naturally arises in several important scenarios. The results can also be applied in the case when there is a fixed cost associated with offering a product in the assortment [4, 29], which arises, for example, in online advertisement with costs-per-impression. For the $p$ -choice facility location problem [49], we show how to reformulate the original problem in a desirable form that can be then exploited to benefit from the submodularity property. Finally, we conclude the note in Section 5.

2. Preliminaries

Notation and additional assumption.Let $a^{k}=(a_{ki})_{i\in N}$ and $b^{k}=(b_{ki})_{i\in N\cup\{0\}}$ for all $k\in M$ , and for given $a^{k}\in\mathbb{R}^{n}$ and $b^{k}\in\mathbb{R}^{n+1}$ , define

h(x;a^{k},b^{k}):=\frac{\sum_{i\in N}a_{ki}x_{i}}{b_{k0}+\sum_{i\in N}b_{ki}x_{i}}.

Then equation (1) can be rewritten as

\max_{x\in\mathcal{F}}\;\sum_{k\in M}h(x;a^{k},b^{k}).

(2)

This form appears in many applications such as the retail assortment and the $p$ -choice facility location problems. Note that for each $x\in\{0,1\}^{n}$ , there is a unique set $S=\{i\in N:\ x_{i}=1\}\subseteq N$ , and conversely, each $S\subseteq N$ corresponds to an indicator vector $\mathbbm{1}_{S}\in\{0,1\}^{n}$ . Thus, we can rewrite $h(x;a^{k},b^{k})$ as a set function

h(S;a^{k},b^{k}):=h(\mathbbm{1}_{S};a^{k},b^{k}),

and regard $\mathcal{F}$ as the domain of sets, i.e., $\mathcal{F}\subseteq 2^{N}$ . Thereafter, we may use the vector form and the set form of (2) interchangeably for convenience.

We also need the following additional assumption:

A3: $\mathcal{F}$ is downward closed, i.e., if $S\in\mathcal{F}$ then $T\in\mathcal{F}$ for all $T\subseteq S$ .

We note that many types of feasible regions considered in the literature, such as $\mathcal{F}=2^{N}$ (unconstrained problem), $\mathcal{F}=\left\{S\subseteq N:\ |S|\leq p\right\}$ for some positive integer $p$ (cardinality constraint) and $\mathcal{F}=\left\{S\subseteq N:\ \sum_{i\in S}w_{i}\leq c\right\}$ for some weights $w\geq 0$ and $c\geq 0$ (capacity constraint) all satisfy Assumption A3.

Submodularity and greedy algorithms. A set function $f:2^{N}\to\mathbb{R}$ from the subsets of $N$ to the real numbers is submodular over $\mathcal{F}$ if it exhibits diminishing returns, i.e., $f(S\cup\{i\})-f(S)\geq f(T\cup\{i\})-f(T)$ for all $S\subseteq T\subseteq N\setminus\{i\}$ such that $T\cup\{i\}\in\mathcal{F}$ . Equivalently, function $f$ is submodular over $\mathcal{F}$ if

f(S\cup\{i,j\})-f(S\cup\{j\})\leq f(S\cup\{i\})-f(S)

(3)

for all $S\subseteq N$ and $i,j\not\in S$ such that $S\cup\{i,j\}\in\mathcal{F}$ .

The greedy algorithm, see its pseudo-code in Algorithm 1, is a popular choice for tackling monotone submodular maximization problems because it is easy to implement and gives a constant-factor approximation in many cases. When the feasible region is a matroid, the greedy algorithm produces a solution with 1/2 approximation factor; see [20]. When the feasible region is given by a cardinality constraint, the approximation ratio can be improved to ( $1-e^{-1}$ ); see [38]. Other ( $1-e^{-1}$ )-approximation algorithms or near-optimal algorithms have also been provided for other classes of feasible regions over the years [12, 27, 46], for example, when $\mathcal{F}$ is defined with a single or multiple capacity constraints.

Algorithm 1 Greedy Algorithm for Submodular Function Maximization

Step 1.

Set $S:=\emptyset$ .
Step 2.

Set $A:=\{\ell\in N\setminus S:\ S\cup\{\ell\}\in\mathcal{F}\}$ .
Step 3.

If $A\neq\emptyset$ , set $\ell^{*}\in\operatorname*{arg\,max}_{\ell\in A}f(S\cup\{\ell\})$ and $S:=S\cup\{\ell^{*}\}$ . Go to Step 2.
Step 4.

Return $S$ .

3. Submodularity of a single ratio and its implications

3.1. A necessary and sufficient condition

In this section, we give a necessary and sufficient condition for the submodularity of the function $h(\cdot)$ , see Theorem 1. As a direct consequence, if $h(\cdot;a^{k},b^{k})$ satisfies the condition of Theorem 1 for every $k\in M$ , then it follows that the fractional 0–1 program (2) admits a constant-factor approximation algorithm. For convenience, we drop the superscript $k$ in $a^{k}$ and $b^{k}$ and use the notation $h(\cdot;a,b)$ throughout this section.

We first consider the case where $b_{0}>0$ . The key result of this note is as follows:

Theorem 1.

If $b_{0}>0$ , then function $h(\cdot;a,b)$ is submodular over $\mathcal{F}$ if and only if

h(S\cup\{i\};a,b)+h(S\cup\{j\};a,b)\leq\frac{a_{i}}{b_{i}}+\frac{a_{j}}{b_{j}}

(4)

for all $S\subseteq N$ , and $i,j\not\in S$ with $i\neq j$ such that $S\cup\{i\}\cup\{j\}\in\mathcal{F}$ .

Proof.

Recall that Assumption A2 holds. Thus, the right-hand side of (4) is well-defined. Let $S\subseteq N$ , let $i,j\not\in S$ with $i\neq j$ satisfying $S\cup\{i\}\cup\{j\}\in\mathcal{F}$ , and define $A_{S}=\sum_{j\in S}a_{j}$ and $B_{S}=b_{0}+\sum_{j\in S}b_{j}$ . Observe that $h(S;a,b)={A_{S}}/{B_{S}}$ . From (3) we find that $h(\cdot;a,b)$ is submodular if and only if

\displaystyle\frac{A_{S}+a_{i}+a_{j}}{B_{S}+b_{i}+b_{j}}-\frac{A_{S}+a_{j}}{B_{S}+b_{j}}\leq\frac{A_{S}+a_{i}}{B_{S}+b_{i}}-\frac{A_{S}}{B_{S}}.

Multiplying both sides by $B_{S}(B_{S}+b_{i}+b_{j})$ , we get the equivalent condition

		$\displaystyle B_{S}\left(A_{S}+a_{i}+a_{j}\right)-B_{S}\left(1+\frac{b_{i}}{B_{S}+b_{j}}\right)(A_{S}+a_{j})$
		$\displaystyle\leq B_{S}\left(1+\frac{b_{j}}{B_{S}+b_{i}}\right)(A_{S}+a_{i})-(B_{S}+b_{i}+b_{j})A_{S}$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle a_{i}B_{S}-b_{i}B_{S}\frac{(A_{S}+a_{j})}{B_{S}+b_{j}}\leq a_{i}B_{S}-b_{i}A_{S}-b_{j}A_{S}+\frac{b_{j}}{B_{S}+b_{i}}B_{S}(A_{S}+a_{i})$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle a_{i}B_{S}-b_{i}B_{S}\frac{(A_{S}+a_{j})}{B_{S}+b_{j}}\leq a_{i}B_{S}-b_{i}A_{S}+\frac{b_{j}}{B_{S}+b_{i}}\Big{(}B_{S}A_{S}+B_{S}a_{i}-(B_{S}+b_{i})A_{S}\Big{)}$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle a_{i}B_{S}-b_{i}B_{S}\frac{(A_{S}+a_{j})}{B_{S}+b_{j}}\leq a_{i}B_{S}-b_{i}A_{S}+\frac{b_{j}}{B_{S}+b_{i}}(a_{i}B_{S}-b_{i}A_{S}).$

Adding $b_{i}A_{S}+b_{i}B_{S}\frac{A_{S}+a_{j}}{B_{S}+b_{j}}-a_{i}B_{S}$ to both sides, we find

		$\displaystyle b_{i}A_{S}\leq b_{i}B_{S}\frac{(A_{S}+a_{j})}{B_{S}+b_{j}}+\frac{b_{j}}{B_{S}+b_{i}}(a_{i}B_{S}-b_{i}A_{S})$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle b_{i}A_{S}\left(B_{S}+b_{i}\right)\left(B_{S}+b_{j}\right)\leq b_{i}B_{S}(A_{S}+a_{j})(B_{S}+b_{i})+b_{j}(B_{S}+b_{j})(a_{i}B_{S}-b_{i}A_{S})$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle b_{i}A_{S}B_{S}^{2}+b_{i}A_{S}B_{S}(b_{i}+b_{j})+b_{i}^{2}b_{j}A_{S}$
		$\displaystyle\leq b_{i}A_{S}B_{S}^{2}+b_{i}a_{j}B_{S}^{2}+B_{S}A_{S}b_{i}^{2}+a_{j}b_{i}^{2}B_{S}+a_{i}b_{j}B_{S}^{2}+a_{i}b_{j}^{2}B_{S}-b_{i}b_{j}A_{S}B_{S}-b_{i}b_{j}^{2}A_{S}.$

After rearranging and canceling out some terms in the above expression, we obtain:

		$\displaystyle 2b_{i}b_{j}A_{S}B_{S}+b_{i}^{2}b_{j}A_{S}+b_{i}b_{j}^{2}A_{S}\leq B_{S}^{2}(a_{i}b_{j}+a_{j}b_{i})+a_{j}b_{i}^{2}B_{S}+a_{i}b_{j}^{2}B_{S}$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle b_{i}b_{j}A_{S}(b_{i}+b_{j}+2B_{S})\leq b_{i}b_{j}\left(a_{j}/b_{j}B_{S}^{2}+a_{j}/b_{j}b_{i}B_{S}+a_{i}/b_{i}B_{S}^{2}+a_{i}/b_{i}b_{j}B_{S}\right)$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle A_{S}(b_{i}+b_{j}+2B_{S})\leq a_{j}/b_{j}B_{S}^{2}+a_{j}/b_{j}b_{i}B_{S}+a_{i}/b_{i}B_{S}^{2}+a_{i}/b_{i}b_{j}B_{S}$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle(B_{S}+b_{i})(A_{S}-a_{j}/b_{j}B_{S})+(B_{S}+b_{j})(A_{S}-a_{i}/b_{i}B_{S})\leq 0.$

Finally, dividing by $(B_{S}+b_{i})(B_{S}+b_{j})$ and then adding $a_{i}/b_{i}+a_{j}/b_{j}$ on both sides, we get

	$\displaystyle\Leftrightarrow\;$	$\displaystyle\left(\frac{A_{S}-a_{j}/b_{j}B_{S}}{B_{S}+b_{j}}+a_{j}/b_{j}\right)+\left(\frac{A_{S}-a_{i}/b_{i}B_{S}}{B_{S}+b_{i}}+a_{i}/b_{i}\right)\leq a_{i}/b_{i}+a_{j}/b_{j}$
	$\displaystyle\Leftrightarrow\;$	$\displaystyle\frac{A_{S}+a_{j}}{B_{S}+b_{j}}+\frac{A_{S}+a_{i}}{B_{S}+b_{i}}\leq a_{i}/b_{i}+a_{j}/b_{j},$

which is precisely inequality (4). ∎

As we discuss next, submodularity is closely linked to monotonicity.

3.2. Monotonicity implies submodularity

The function $h(\cdot;a,b)$ is monotone nondecreasing if

h(S;a,b)\leq h(S\cup\{j\};a,b)

(5)

for every set $S$ and $j\not\in S$ such that $S\cup\{j\}\in\mathcal{F}$ . Monotonicity is often a prerequisite for greedy algorithms, see, e.g., [38], to guarantee a constant approximation factor. Also, it arises naturally in many applications; see Section 4.1.1 for details. As we show next, monotonicity is a sufficient condition for submodularity.

Proposition 1.

If function $h(\cdot;a,b)$ is monotone nondecreasing, then $h(\cdot;a,b)$ is submodular.

Proof.

Condition (5) is equivalent to

	$\displaystyle\frac{\sum_{i\in S}a_{i}}{b_{0}+\sum_{i\in S}b_{i}}\leq\frac{\sum_{i\in S}a_{i}+a_{j}}{b_{0}+\sum_{i\in S}b_{i}+b_{j}}$
$\displaystyle\Leftrightarrow\;$	$\displaystyle\left(1+\frac{b_{j}}{b_{0}+\sum_{i\in S}b_{i}}\right)\sum_{i\in S}a_{i}\leq\sum_{i\in S}a_{i}+a_{j}$
$\displaystyle\Leftrightarrow\;$	$\displaystyle\frac{\sum_{i\in S}a_{i}}{b_{0}+\sum_{i\in S}b_{i}}\leq\frac{a_{j}}{b_{j}}$
$\displaystyle\Leftrightarrow\;$	$\displaystyle h(S;a,b)\leq\frac{a_{j}}{b_{j}}$	(6)

for all $S$ and $j\not\in S$ . Therefore, if $i,j\not\in S$ , then $h(S\cup\{i\};a,b)\leq{a_{i}}/{b_{i}}$ and $h(S\cup\{j\};a,b)\leq{a_{j}}/{b_{j}}$ , and inequality (4) follows. ∎

Inequality (6) needs to hold for every combination of set $S$ and element $i$ for the function to be monotone. Thus, checking monotonicity can be done by verifying that

\min_{i\in N}\frac{a_{i}}{b_{i}}\geq\max_{S\in\mathcal{F}}h(S;a,b),

(7)

and the optimization problem on the right-hand side of (7) can be solved using existing algorithms for single-ratio fractional optimization; see [33, 42]. In fact, in some cases monotonicity can be verified without solving an optimization problem.

Corollary 1.

Function $h(\cdot;a,b)$ is monotone nondecreasing (and submodular) over $2^{N}$ if and only if

\min_{i\in N}\frac{a_{i}}{b_{i}}\geq h(N;a,b).

Proof.

The forward direction follows directly from (7). For the backward direction, let ${a^{*}}/{b^{*}}=\min_{i\in N}\{a_{i}/b_{i}\}$ , and then we find that

\displaystyle h(N;a,b)\leq\frac{a^{*}}{b^{*}}

\displaystyle\Leftrightarrow\frac{\sum_{i\in N}a_{i}}{b_{0}+\sum_{i\in N}b_{i}}\leq\frac{a^{*}}{b^{*}}\Leftrightarrow\sum_{i\in N}\left(\frac{a_{i}}{b_{i}}-\frac{a^{*}}{b^{*}}\right)b_{i}\leq\frac{a^{*}}{b^{*}}b_{0}.

Since ${a_{i}}/{b_{i}}\geq{a^{*}}/{b^{*}}$ , we find that $\sum_{i\in S}({a_{i}}/{b_{i}}-{a^{*}}/{b^{*}})b_{i}\leq\left({a^{*}}/{b^{*}}\right)b_{0}$ for any $S\subseteq N$ , i.e., $h(S;a,b)\leq{a^{*}}/{b^{*}}$ for any $S\subseteq N$ . ∎

3.3. On non-monotone submodular functions

From Proposition 1, we know that monotonicity implies submodularity. In general, as Example 1 below shows, the converse does not hold.

Example 1.

Assume we have three variables, i.e., $N=\{1,2,3\}$ , with the setting $(a_{1},a_{2},a_{3})=(3,2,1)$ and $(b_{0},b_{1},b_{2},b_{3})=(2,1,1,1)$ . Then from Theorem 1 we can verify that $h(\cdot;a,b)$ is submodular over $2^{N}$ : since $a_{i}/b_{i}+a_{j}/b_{j}\geq 3$ for any $i\neq j$ and, for any $S\subseteq N$ , $h(S;a,b)\leq h(\{1,2\};a,b)=5/4\leq 3/2$ , we find that inequality (4) holds. However, $h(\{3\};a,b)=1/3<h(\{1,2,3\};a,b)=6/5<h(\{1,2\};a,b)=5/4$ , and monotonicity does not hold.∎

Nonetheless, if $h(\cdot;a,b)$ is submodular, then it is in fact very close to a nondecreasing function as shown in Proposition 2 below. In particular, if the decision variable with the smallest value $a_{i}/b_{i}$ is fixed, then the resulting function is monotone.

Assume for the remainder of this section, without loss of generality, that $a_{1}/b_{1}\geq a_{2}/b_{2}\geq\dots\geq a_{n}/b_{n}$ . Define $\mathcal{F}_{1}:=\{S\in\mathcal{F}:\ n\in S\}$ and $\mathcal{F}_{2}:=\{S\in\mathcal{F}:\ n\notin S\}$ .

Proposition 2.

If $h(\cdot;a,b)$ is submodular over $\mathcal{F}$ , then the following holds:
(i) function $h(\cdot;a,b)$ is monotone nondecreasing over $\mathcal{F}_{1}$ ;
(ii) for any $S\in\mathcal{F}_{2}$ and any $j\neq n$ such that $S\cup\{j\}\in\mathcal{F}$ and $S\cup\{n\}\in\mathcal{F}$ , we have $h(S\cup\{j\};a,b)\geq h(S;a,b)$ .

Proof.

We first prove $h(\cdot;a,b)$ is monotone nondecreasing over $\mathcal{F}_{1}$ by contradiction. Assume there exists $S$ and $j\neq n$ such that $n\notin S$ and $h(S\cup\{j,n\};a,b)<h(S\cup\{n\};a,b)$ . Because $h(S\cup\{j,n\};a,b)$ is a convex combination of $h(S\cup\{n\};a,b)$ and ${a_{j}}/{b_{j}}$ , we have ${a_{j}}/{b_{j}}<h(S\cup\{n\};a,b)$ . Since ${a_{n}}/{b_{n}}\leq{a_{j}}/{b_{j}}$ , we find that ${a_{n}}/{b_{n}}<h(S\cup\{n\};a,b)$ . Note that

\displaystyle h(S\cup\{n\};a,b)

\displaystyle=\left(\frac{b_{0}+\sum_{i\in S}b_{i}}{b_{0}+b_{n}+\sum_{i\in S}b_{i}}\right)h(S;a,b)+\frac{b_{n}}{b_{0}+b_{n}+\sum_{i\in S}b_{i}}\frac{a_{n}}{b_{n}}

is a convex combination of $h(S;a,b)$ and $a_{n}/b_{n}$ , and since $a_{n}/b_{n}<h(S\cup\{n\};a,b)$ , it follows that $h(S\cup\{n\};a,b)<h(S;a,b)$ . By submodularity, $h(S\cup\{j,n\};a,b)-h(S\cup\{j\};a,b)\leq h(S\cup\{n\};a,b)-h(S;a,b)<0$ , which indicates that $h(S\cup\{j,n\};a,b)<h(S\cup\{j\};a,b)$ . Thus, ${a_{n}}/{b_{n}}<h(S\cup\{j\};a,b)$ . However, this implies $h(S\cup\{j\};a,b)+h(S\cup\{n\};a,b)>{a_{j}}/{b_{j}}+{a_{n}}/{b_{n}}$ , which is a contradiction based on Theorem 1. Thus, (i) holds.

Next, we prove (ii) by contradiction. Assume there exists $S$ and $j\neq n$ such that $n\notin S$ and $h(S\cup\{j\};a,b)<h(S;a,b)$ . Because $h(S\cup\{j\};a,b)$ is the weighted average of $a_{j}/b_{j}$ and $h(S;a,b)$ , we have that ${a_{j}}/{b_{j}}<h(S\cup\{j\};a,b)<h(S;a,b)$ . Recall that ${a_{n}}/{b_{n}}\leq{a_{j}}/{b_{j}}$ . Hence, ${a_{n}}/{b_{n}}<h(S;a,b)$ , which implies ${a_{n}}/{b_{n}}<h(S\cup\{n\};a,b)$ – using similar arguments as in the proof of (i). Hence, $h(S\cup\{j\};a,b)+h(S\cup\{n\};a,b)>{a_{j}}/{b_{j}}+{a_{n}}/{b_{n}}$ , which contradicts the submodularity of $h(\cdot;a,b)$ . ∎

Corollary 2.

If either $\mathcal{F}=2^{N}$ or $\mathcal{F}=\{S\subseteq N:\ |S|\leq p\}$ for any $p\in\{1,\ldots,n-1\}$ , then submodularity of $h(\cdot;a,b)$ over $\mathcal{F}$ implies that $h(\cdot;a,b)$ is monotone nondecreasing over $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ .

Example 1 (Continued).

Observe that $h(\cdot;a,b)$ is indeed monotone over $\mathcal{F}_{1}$ , since $h(\{3\};a,b)=1/3$ , $h(\{1,3\};a,b)=1$ , $h(\{2,3\};a,b)=3/4$ and $h(\{1,2,3\};a,b)=6/5$ . Similarly, we can verify that $h(\cdot;a,b)$ is monotone over $\mathcal{F}_{2}$ since $h(\emptyset;a,b)=0$ , $h(\{1\};a,b)=1$ , $h(\{2\};a,b)=2/3$ and $h(\{1,2\};a,b)=5/4$ .∎

3.4. On homogeneous fractional functions

In this section, we show that the assumption $b_{0}>0$ is indeed necessary in Theorem 1, as otherwise submodularity does not hold in most practical situations. Proposition 3 below formalizes this statement.

Proposition 3.

Assume $b_{0}=0$ . If there exists a feasible set $S$ such that there are at least three distinct values for ${a_{i}}/{b_{i}},\ i\in S$ , then $h(\cdot;a,b)$ is not submodular.

Proof.

Assume without loss of generality that ${a_{1}}/{b_{1}}<{a_{2}}/{b_{2}}<{a_{3}}/{b_{3}}$ . Then the following inequality

\frac{b_{1}}{b_{1}+b_{3}}\left(\frac{a_{3}}{b_{3}}-\frac{a_{1}}{b_{1}}\right)+\frac{b_{2}}{b_{2}+b_{3}}\left(\frac{a_{3}}{b_{3}}-\frac{a_{2}}{b_{2}}\right)\geq\frac{b_{1}}{b_{1}+b_{2}+b_{3}}\left(\frac{a_{3}}{b_{3}}-\frac{a_{1}}{b_{1}}\right)+\frac{b_{2}}{b_{1}+b_{2}+b_{3}}\left(\frac{a_{3}}{b_{3}}-\frac{a_{2}}{b_{2}}\right).

holds since denominators are greater on the right-hand side. Subtracting $2\cdot\left({a_{3}}/{b_{3}}\right)$ on both sides, we find that

-\frac{a_{1}+a_{3}}{b_{1}+b_{3}}-\frac{a_{2}+a_{3}}{b_{2}+b_{3}}\geq-\frac{a_{1}+a_{2}+a_{3}}{b_{1}+b_{2}+b_{3}}-\frac{a_{3}}{b_{3}},

which is equivalent to $h(\{1,3\};a,b)+h(\{2,3\};a,b)\leq h(\{1,2,3\};a,b)+h(\{3\};a,b)$ , violating the definition of submodularity. ∎

4. Applications

In this section, we discuss the implications of our theoretical results in the context of the assortment optimization and the $p$ -choice facility location problems.

4.1. Assortment optimization problem

In the assortment optimization problem, a firm offers a set of products to utility-maximizing customers. The goal of the firm is to choose an assortment of products that maximizes its expected revenue. It is a core revenue management problem pervasive in practice [47]. In this subsection, we mainly consider this problem under the mixed multinomial logit model (MMNL); see, e.g., [9, 32].

Formally, let $N$ be the set of products that can be offered to customers. Denote by $r_{i}$ the revenue perceived by the firm if a customer chooses product $i\in N$ . Under the MMNL model, each product $i\in N$ is associated with a random weight $v_{ki}>0$ , and the no-purchase option is associated with weight $v_{k0}>0$ ; these weights encode the relative preferences for the products by a customer of type $k\in M$ , i.e., set $M$ describes market segments.

Given the preference weights $v^{k}$ , if assortment $S\subseteq N$ is offered, then the probability that a customer in $k\in M$ chooses product $i\in S$ is given by

q(i,S;v^{k})=\frac{v_{ki}}{v_{k0}+\sum_{i\in S}v_{ki}}.

The conditional expected revenue from offering assortment $S\subseteq N$ is

r(S;v^{k})=\sum_{i\in S}r_{i}q(i,S;v^{k}).

Taking the expectation over the random vector $v^{k}$ , we formulate the assortment optimization problem under the MMNL model as

\max_{S\in\mathcal{F}}\mathbb{E}_{v}\left[r(S;v)\right]=\sum_{k\in M}p_{k}r(S;v^{k}),

(8)

where $p_{k}$ is the probability of a customer to be in segment $k$ and each realization of $v$ can be interpreted as the preferences associated with a given customer of customer segment. We assume that the support of $v$ is finite. Hence, (8) can be posed in the form of (1), where $a_{ki}=p_{k}r_{i}v_{ki}$ , $b_{ki}=v_{ki}$ and $b_{k0}=v_{k0}$ for all $k\in M$ and $i\in N$ . Thus, ${a_{ki}}/{b_{ki}}=p_{k}r_{i}$ .

Finally, we note that $p_{k}\geq 0$ for each $k\in M$ . Hence, for submodularity of the objective function in (8) it is sufficient to consider the single-ratio functions $r(\cdot;v^{k})$ , $k\in M$ . Therefore, in our discussion below when applying the results of Theorem 1 and Corollary 1 (with ratio $a_{i}/b_{i}$ ), the multiplier $p_{k}$ can be dropped from consideration.

4.1.1. Cannibalization and submodularity

Intuitively, in retail assortment problems, monotonicity of the revenue function implies that there is limited cannibalization, i.e., the introduction of a new product $i$ (when feasible) always increases the expected revenue perceived by the firm – despite that the revenue obtained from previously offered products in $S$ might decrease slightly. To be more specific, this limited cannibalization phenomenon arises in online advertising: the probability that a given customer clicks on an ad is often quite low, and the advertiser usually profits from offering more ads within the limited number of spots on the webpage.

Let $r_{\min}=\min_{i\in N}r_{i}$ and $r_{\max}=\max_{i\in N}r_{i}$ . By Proposition 1 and Corollary 1, we obtain the following results in terms of revenue functions immediately.

Corollary 3.

If function $r(\cdot;v)$ is monotone nondecreasing, then $r(\cdot;v)$ is submodular.

Corollary 4.

Function $r(\cdot;v)$ is monotone nondecreasing (and submodular) over $2^{N}$ if and only if $r_{min}\geq r(N;v)$ .

4.1.2. Revenue spread, no-purchase probability and submodularity

When the revenues $r$ of all products are identical, assortment optimization problems are known to be submodular maximization problems [4, 15]. Intuitively, one would expect that if the revenues are sufficiently close (but not identical), then submodularity should be preserved. Proposition 4 formalizes this intuition: if the gap between the largest and the smallest revenues is bounded above by the odds of no-purchase, then the function is nondecreasing and submodular.

Proposition 4.

\frac{r_{\max}-r_{\min}}{r_{\min}}\leq\min\limits_{S\in\mathcal{F}}\frac{1-q(S;v)}{q(S;v)},

(9)

then $r(\cdot;v)$ is nondecreasing and submodular, where $r_{\max}$ and $r_{\min}$ are the largest and smallest revenues, respectively, and $q(S;v)=\sum_{i\in S}q(i,S;v)$ is the probability that an item is purchased.

Proof.

Equation (9) can be rewritten as $r_{\max}q(S;v)\leq r_{\min}$ for all $S\in\mathcal{F}$ . Since for any $S$ and $i\not\in S$ it follows that $r(S;v)\leq r_{\max}q(S;v)\leq r_{\min}\leq r_{i}$ , we find that (6) is satisfied and the function $r(\cdot;v)$ is monotone submodular. ∎

Proposition 4 provides us with additional intuition on the industries in which the expected revenues are submodular functions of the assortment offered. In the online advertisement, where the revenues obtained from clicks are usually similar and the odds of no-purchase are high, we would expected to obtain submodular revenue functions. In a monopoly, the firm offering the assortment would have a large flexibility in setting prices (resulting in a large revenue spread) and the odds of no-purchase would be low (due to the lack of competing alternatives), resulting in a revenue function that is not submodular. In contrast, in a competitive market, the odds of no-purchase would be larger and firms have little or no control over prices (and if the values $r_{i}$ are interpreted as profits instead of revenues, the spread would typically be low), resulting in submodular revenue functions.

From Proposition 4 we also gain insights on the differences between revenue management in the airline and hospitality industries, two industries that are often treated as equivalent in the literature [48]. In the hospitality industries, no-purchase odds can be high as shown by the relatively low occupancy rates – 66.1% in the US [25] in 2018; in addition, revenue differences between products are often due to ancillary charges (e.g., breakfast, non-refundable, long stay), which account for a small portion of the baseline price for a room. In such circumstances we would expect revenue functions to be submodular and simple greedy heuristics to perform well. In contrast, in the airline industries no-purchase odds are often smaller – the load factor was 86.1% in the US in 2018 [21] –, and air fares can change dramatically depending on the conditions. Thus, in the airline industry we would expect to encounter non-submodular revenue functions, and simple heuristics may be inadequate.

4.1.3. On the greedy algorithm and revenue-ordered assortments

Revenue-ordered assortments are optimal for unconstrained assortment optimization under the MNL model, and tend to perform well in practice [47]. Berbeglia and Joret, [7] study the revenue-ordered assortments under the general discrete choice model and prove performance guarantees.

Proposition 5 (Berbeglia and Joret, [7]).

Revenue-ordered assortments are a $\frac{1}{1+\log\left(\frac{r_{\max}}{r_{\min}}\right)}$ -approximation for the unconstrained assortment optimization problem under the MMNL choice model, where $r_{\max}$ and $r_{\min}$ are the largest and smallest revenues, respectively.

Thus, the quality of revenue-ordered assortments depend on the ratio $r_{max}/r_{min}$ ; in particular, if $r_{max}/r_{min}=1$ , then the revenue-ordered assortments strategy delivers an optimal solution, and the guarantee degrades as the value of the ratio increases.

From Proposition 4, we can also obtain guarantees depending on the ratio $r_{max}/r_{min}$ . Define:

\alpha(S)=\max_{k\in M}q(S;v^{k})=\max_{k\in M}\sum_{i\in S}q(i,S;v^{k})

(10)

as the maximum probability that a customer from any segment purchases an item when assortment $S$ is offered.

Proposition 6.

If $\mathcal{F}=\{S:\ |S|\leq p\}$ for some positive integer $p$ and $r_{max}/r_{min}\leq 1+\frac{1-\alpha(S)}{\alpha(S)}$ for all $S\in\mathcal{F}$ , then Algorithm 1 delivers a $(1-1/e)$ -optimal solution for the assortment optimization problem under the MMNL choice model.

Unlike Proposition 5, we impose a condition on the ratio $r_{max}/r_{min}$ in Proposition 6; however, if such condition is satisfied, then we obtain an approximation guarantee of $(1-1/e)\approx 0.63$ for the more general assortment optimization problem under a cardinality constraint.

Finally, we also point out that Rusmevichientong et al., [44] prove that if customers are value conscious, i.e., ${v}_{1}\leq v_{2}\leq\ldots\leq v_{n}$ and $r_{1}v_{1}\geq r_{2}v_{2}\geq\ldots\geq r_{n}v_{n}$ for all realizations of ${v}$ , then the revenue ordered assortments are optimal for the unconstrained and cardinality constrained cases. It is easy to check that in this case the solutions obtained from the greedy algorithm correspond precisely with the revenue ordered assortments. Thus, Algorithm 1 delivers optimal solutions as well.

4.2. $p$ -choice facility location problem

Facility location problems deal with deciding where to locate facilities across a finite set of feasible points, taking into account the needs of customers to be served in such a way that a given economic index is optimized [6]. Submodularity often arises in facility location problems; see [3, 17, 30, 39]. In this subsection, we consider a particular class of facility location problems with a fractional 0–1 objective function, referred to as the $p$ -choice facility location problem, which is considered in [49]. In the $p$ -choice facility location problem, a decision-maker has to decide where to locate $p$ facilities in $n$ possible locations to service $m$ demand points, in order to maximize the market share.

Formally, let $d_{k}>0$ be the demand at customer location $k\in M=\{1,\dots,m\}$ , and $v_{ki}>0$ be the utility of location $i$ to customers at $k$ . Let $S\subseteq N:=\{1,\ldots,n\}$ , $|S|=p$ , be the set of facilities chosen by the decision-maker. It is assumed that the market share provided by facility $j\in S$ with respect to demand point $k$ is given by:

d_{k}\frac{v_{kj}}{\sum_{i\in S}v_{ki}}.

Let $w_{i}>0$ be some weight parameter that represents the importance of locating facility in location $i\in N$ . Then the problem of determining the set of facility locations $S$ that maximizes the weighted market share can be formulated as:

\max_{|S|=p}\;\sum_{i\in S}w_{i}\sum_{k\in M}d_{k}\frac{v_{ki}}{\sum_{i\in S}v_{ki}},

which can be reorganized as

\max_{|S|=p}\;\sum_{k\in M}d_{k}\frac{\sum_{i\in S}v_{ki}w_{i}}{\sum_{i\in S}v_{ki}}.

(11)

Clearly, the model in (11) can be formulated as a fractional 0–1 program given by (1).

Note that from Proposition 3, the objective function in (11) is, in general, not submodular since it is homogeneous. Nonetheless, exploiting the equality constraint, we can convert the objective function to a non-homogeneous one. Define $v_{\min}^{k}=\delta\cdot\min_{i\in N}\{v_{ki}\}$ for some fixed $\delta\in(0,1)$ . For any feasible solution $S$ , where $|S|=p$ , we also have that:

\sum_{i\in S}v_{ki}=\sum_{i\in S}v_{\min}^{k}+\sum_{i\in S}(v_{ki}-v_{\min}^{k})=pv_{\min}^{k}+\sum_{i\in S}(v_{ki}-v_{\min}^{k}).

As a result, (11) can be equivalently stated as:

\max_{|S|=p}\;\sum_{k\in M}d_{k}\frac{\sum_{i\in S}v_{ki}w_{i}}{pv_{\min}^{k}+\sum_{i\in S}(v_{ki}-v_{\min}^{k})},

(12)

where $v_{ki}-v_{\min}^{k}>0$ and $v_{\min}^{k}>0$ for all $i\in N$ and $k\in M$ by our construction procedure.

Recall our discussion on the links between monotonicity and submodularity in Section 3.2. Applying inequality (7), we find that a given ratio $k$ in the objective function of (12) is monotone nondecreasing over set $\mathcal{F}:=\{S\subseteq N:\ |S|\leq p\}$ if

\min_{i\in N}\frac{v_{ki}w_{i}}{v_{ki}-v_{\min}^{k}}\geq\max_{|S|\leq p}\frac{\sum_{i\in S}v_{ki}w_{i}}{pv_{\min}^{k}+\sum_{i\in S}(v_{ki}-v_{\min}^{k})}.

(13)

Hence, if (13) holds for all ratios $k\in M$ , then the feasibility set in (12) can be relaxed to $|S|\leq p$ . Consequently, Assumption A3 is satisfied and (12) reduces to the maximization problem of a submodular function by Proposition 1.

The right-hand side of (13) can be interpreted as the best average revenue weighted by market share, or simply the best total revenue that can be obtained from customer segment $k$ . The intuition for (13) to hold in the $p$ -choice facility location problem is rather similar to our observations in the assortment optimization problem. Indeed, it is easy to verify, for example, that if all locations have the same utilities and weights, i.e., $v_{ki}=v^{k}$ and $w_{i}=w$ for all $i\in N$ and some $v^{k}$ and $w$ , then (13) holds. Moreover, from (13) we obtain the following sufficient condition.

Proposition 7.

Let $w_{\max}$ and $w_{\min}$ be the maximum and minimum weights, and let $v_{\max}^{k}$ be the maximum utility associated with customer segment $k$ . If

\frac{w_{\min}}{w_{\max}}+1\geq\frac{v_{\max}^{k}}{v_{\min}^{k}},

(14)

then the revenue of customer segment $k$ is submodular.

Proof.

Observe that since $w_{i}\geq w_{\min}$ and $\frac{v_{ki}}{v_{ki}-v_{\min}^{k}}\geq\frac{v_{\max}^{k}}{v_{\max}^{k}-v_{\min}^{k}}$ , we find that

\frac{v_{ki}w_{i}}{v_{ki}-v_{\min}^{k}}\geq\frac{v_{\max}^{k}}{v_{\max}^{k}-v_{\min}^{k}}w_{\min}.

Moreover, we also find that

\max_{|S|\leq p}\frac{\sum_{i\in S}v_{ki}w_{i}}{pv_{\min}^{k}+\sum_{i\in S}(v_{ki}-v_{\min}^{k})}\leq\max_{|S|\leq p}\frac{w_{\max}\sum_{i\in S}v_{ki}}{pv_{\min}^{k}}\leq\frac{w_{\max}v_{\max}^{k}}{v_{\min}^{k}}.

After rearranging terms corresponding to the sufficient condition

\frac{v_{\max}^{k}}{v_{\max}^{k}-v_{\min}^{k}}w_{\min}\geq\frac{w_{\max}v_{\max}^{k}}{v_{\min}^{k}},

we obtain precisely (14). ∎

Simply speaking, if the considered facility locations are sufficiently similar with respect to their utilities, i.e., $\frac{v_{\max}^{k}}{v_{\min}^{k}}\approx 1$ , then ratios in (12) are submodular. Submodularity may be preserved for larger spread of utilities, provided that the weights are sufficiently close. If all the considered facility locations are sufficiently similar with respect to their utilities and weights, then (11) can be reduced to maximizing a submodular function; consequently, high-quality solutions can be obtained by a greedy approach, e.g., Algorithm 1.

4.3. On minimization problems

In this note we focus on identifying submodularity in maximization problems, in which case greedy algorithms can be used to obtain near optimal solutions. However, submodularity can be exploited in minimization problems as well. Indeed, the epigraph of a submodular set function is described by its Lovász extension [31], which can be used to improve mixed-integer programming formulations via cutting planes. Moreover, even if a given ratio is not submodular, the results presented in this paper can be used to decompose any ratio into two components such that one of which is submodular (and strengthening can be done using the submodular component); see, e.g., [5].

5. Conclusion

In this note we explore submodularity of the objective function for a broad class of fractional 0–1 programs with multiple-ratios. Under some mild assumptions, we derive the necessary and sufficient condition for a single ratio of two linear functions to be submodular. Therefore, if the derived condition holds for every considered single-ratio function, then simple greedy algorithms can be used to deliver good quality solutions for multiple-ratio fractional 0–1 programs. Finally, we also illustrate applicability of our results in the context of the assortment optimization and facility location problems.

Acknowledgements. This note is based upon work supported by the National Science Foundation under Grant No. 1818700.

References

Amiri et al., [1999] Amiri, A., Rolland, E., and Barkhi, R. (1999). Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures. European Journal of Operational Research, 112(3):635–645.
Arora et al., [1977] Arora, S., Puri, M., and Swarup, K. (1977). The set covering problem with linear fractional functional. Indian Journal of Pure and Applied Mathematics, 8(5):578–588.
Atamtürk et al., [2012] Atamtürk, A., Berenguer, G., and Shen, Z.-J. (2012). A conic integer programming approach to stochastic joint location-inventory problems. Operations Research, 60(2):366–381.
Atamtürk and Gómez, [2017] Atamtürk, A. and Gómez, A. (2017). Maximizing a class of utility functions over the vertices of a polytope. Operations Research, 65(2):433–445.
Atamtürk and Narayanan, [2019] Atamtürk, A. and Narayanan, V. (2019). Submodular function minimization and polarity. arXiv preprint arXiv:1912.13238.
Barros, [2013] Barros, A. I. (2013). Discrete and fractional programming techniques for location models, volume 3. Springer Science & Business Media.
Berbeglia and Joret, [2017] Berbeglia, G. and Joret, G. (2017). Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, pages 345–346, New York, NY, USA. ACM.
Bertsimas et al., [2019] Bertsimas, D., Korolko, N., and Weinstein, A. M. (2019). Identifying exceptional responders in randomized trials: An optimization approach. Informs Journal on Optimization, 1(3):187–199.
Bonnet and Simioni, [2001] Bonnet, C. and Simioni, M. (2001). Assessing consumer response to protected designation of origin labelling: a mixed multinomial logit approach. European Review of Agricultural Economics, 28(4):433–449.
Borrero et al., [2016] Borrero, J. S., Gillen, C., and Prokopyev, O. A. (2016). A simple technique to improve linearized reformulations of fractional (hyperbolic) 0–1 programming problems. Operations Research Letters, 44(4):479–486.
Borrero et al., [2017] Borrero, J. S., Gillen, C., and Prokopyev, O. A. (2017). Fractional 0–1 programming: applications and algorithms. Journal of Global Optimization, 69(1):255–282.
Calinescu et al., [2011] Calinescu, G., Chekuri, C., Pál, M., and Vondrák, J. (2011). Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740–1766.
Chandrasekaran, [1977] Chandrasekaran, R. (1977). Minimal ratio spanning trees. Networks, 7(4):335–342.
Chen and Tian, [2020] Chen, R. and Tian, Q. (2020). Exact approaches for competitive facility location with discrete attractiveness. Optimization Letters. forthcoming.
Désir et al., [2015] Désir, A., Goyal, V., Segev, D., and Ye, C. (2015). Capacity constrained assortment optimization under the Markov chain based choice model. Working paper, Columbia University, New York, NY. http://dx.doi.org/10.2139/ssrn.2626484.
Désir et al., [2014] Désir, A., Goyal, V., and Zhang, J. (2014). Near-optimal algorithms for capacity constrained assortment optimization. Working paper, Columbia University, NY. http://dx.doi.org/10.2139/ssrn.2543309.
Du et al., [2012] Du, D., Lu, R., and Xu, D. (2012). A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica, 63(1-2):191–200.
Elhedhli, [2005] Elhedhli, S. (2005). Exact solution of a class of nonlinear knapsack problems. Operations research letters, 33(6):615–624.
Feldman and Topaloglu, [2015] Feldman, J. and Topaloglu, H. (2015). Bounding optimal expected revenues for assortment optimization under mixtures of multinomial logits. Production and Operations Management, 24(10):1598–1620.
Fisher et al., [1978] Fisher, M. L., Nemhauser, G., and L.and Wolsey, L. A. (1978). An analysis of approximations for maximizing submodular set functions—II. In Balinski, M. L.and Hoffman, A. J., editor, Polyhedral Combinatorics, pages 73–87. Springer.
Goldstein, [2018] Goldstein, M. (2018). Forbes. https://www.forbes.com/sites/michaelgoldstein/2018/07/09/meet-the-most-crowded-airlines-load-factor-hits-all-time-high/\#90f0b4354fbd. Accessed: 2019-04-12.
Granot and Granot, [1976] Granot, D. and Granot, F. (1976). On solving fractional (0, 1) programs by implicit enumeration. INFOR: Information Systems and Operational Research, 14(3):241–249.
Hansen et al., [1990] Hansen, P., De Aragão, M. V. P., and Ribeiro, C. C. (1990). Boolean query optimization and the 0-1 hyperbolic sum problem. Annals of Mathematics and Artificial Intelligence, 1(1-4):97–109.
Hansen et al., [1991] Hansen, P., De Aragão, M. V. P., and Ribeiro, C. C. (1991). Hyperbolic 0–1 programming and query optimization in information retrieval. Mathematical Programming, 52(1-3):255–263.
Hoisington, [2018] Hoisington, A. (2018). Hotel management. https://www.hotelmanagement.net/own/occupancy-hits-30-year-high-u-s. Accessed: 2019-04-12.
Iwano et al., [1994] Iwano, K., Misono, S., Tezuka, S., and Fujishige, S. (1994). A new scaling algorithm for the maximum mean cut problem. Algorithmica, 11(3):243–255.
Kulik et al., [2009] Kulik, A., Shachnai, H., and Tamir, T. (2009). Maximizing submodular set functions subject to multiple linear constraints. In Mathieu, C., editor, Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 545–554. Society for Industrial and Applied Mathematics.
Kunnumkal, [2015] Kunnumkal, S. (2015). On upper bounds for assortment optimization under the mixture of multinomial logit models. Operations Research Letters, 43(2):189–194.
Kunnumkal and Martínez-de-Albéniz, [2019] Kunnumkal, S. and Martínez-de-Albéniz, V. (2019). Tractable approximations for assortment planning with product costs. Operations Research.
Li et al., [2015] Li, Y., Du, D., Xiu, N., and Xu, D. (2015). Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica, 73(2):460–482.
Lovász, [1983] Lovász, L. (1983). Submodular functions and convexity. In Mathematical programming the state of the art, pages 235–257. Springer.
McFadden and Train, [2000] McFadden, D. and Train, K. (2000). Mixed MNL models for discrete response. Journal of Applied Econometrics, 15(5):447–470.
Megiddo et al., [1979] Megiddo, N. et al. (1979). Combinatorial optimization with rational objective functions. Mathematics of Operations Research, 4(4):414–424.
Mehmanchi et al., [2019] Mehmanchi, E., Gómez, A., and Prokopyev, O. A. (2019). Fractional 0–1 programs: links between mixed-integer linear and conic quadratic formulations. Journal of Global Optimization, 75(2):273–339.
Méndez-Díaz et al., [2014] Méndez-Díaz, I., Miranda-Bront, J. J., Vulcano, G., and Zabala, P. (2014). A branch-and-cut algorithm for the latent-class logit assortment problem. Discrete Applied Mathematics, 164:246–263.
Mittal and Schulz, [2013] Mittal, S. and Schulz, A. S. (2013). A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. Operations Research, 61(2):386–397.
Moorthy and Png, [1992] Moorthy, K. S. and Png, I. P. (1992). Market segmentation, cannibalization, and the timing of product introductions. Management Science, 38(3):345–359.
Nemhauser et al., [1978] Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294.
Ortiz-Astorquiza et al., [2017] Ortiz-Astorquiza, C., Contreras, I., and Laporte, G. (2017). Formulations and approximation algorithms for multilevel uncapacitated facility location. INFORMS Journal on Computing, 29(4):767–779.
[40] Prokopyev, O. A., Huang, H.-X., and Pardalos, P. M. (2005a). On complexity of unconstrained hyperbolic 0–1 programming problems. Operations Research Letters, 33(3):312–318.
[41] Prokopyev, O. A., Meneses, C., Oliveira, C. A., and Pardalos, P. M. (2005b). On multiple-ratio hyperbolic 0–1 programming problems. Pacific Journal of Optimization, 1(2):327–345.
Radzik, [1998] Radzik, T. (1998). Fractional combinatorial optimization. In Du, D.-Z. and Pardalos, P. M., editors, Handbook of Combinatorial Optimization, pages 429–478. Springer-Verlag New York.
Rusmevichientong et al., [2009] Rusmevichientong, P., Shen, Z.-J. M., and Shmoys, D. B. (2009). A PTAS for capacitated sum-of-ratios optimization. Operations Research Letters, 37(4):230–238.
Rusmevichientong et al., [2014] Rusmevichientong, P., Shmoys, D., Tong, C., and Topaloglu, H. (2014). Assortment optimization under the multinomial logit model with random choice parameters. Production and Operations Management, 23(11):2023–2039.
Sethuraman and Butenko, [2015] Sethuraman, S. and Butenko, S. (2015). The maximum ratio clique problem. Computational Management Science, 12(1):197–218.
Sviridenko, [2004] Sviridenko, M. (2004). A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43.
Talluri and van Ryzin, [2004] Talluri, K. and van Ryzin, G. (2004). Revenue management under a general discrete choice model of consumer behavior. Management Science, 50(1):15–33.
Talluri and van Ryzin, [2006] Talluri, K. T. and van Ryzin, G. J. (2006). The theory and practice of revenue management, volume 68. Springer Science & Business Media.
Tawarmalani et al., [2002] Tawarmalani, M., Ahmed, S., and Sahinidis, N. V. (2002). Global optimization of 0-1 hyperbolic programs. Journal of Global Optimization, 24(4):385–416.
Ursulenko et al., [2013] Ursulenko, O., Butenko, S., and Prokopyev, O. A. (2013). A global optimization algorithm for solving the minimum multiple ratio spanning tree problem. Journal of Global Optimization, 56(3):1029–1043.

Fractional 0–1 programming and Submodularity

Abstract.

1. Introduction

2. Preliminaries

3. Submodularity of a single ratio and its implications

3.1. A necessary and sufficient condition

Theorem 1.

Proof.

3.2. Monotonicity implies submodularity

Proposition 1.

Proof.

Corollary 1.

Proof.

3.3. On non-monotone submodular functions

Example 1.

Proposition 2.

Proof.

Corollary 2.

Example 1 (Continued).

3.4. On homogeneous fractional functions

Proposition 3.

Proof.

4. Applications

4.1. Assortment optimization problem

4.1.1. Cannibalization and submodularity

Corollary 3.

Corollary 4.

4.1.2. Revenue spread, no-purchase probability and submodularity

Proposition 4.

Proof.

4.1.3. On the greedy algorithm and revenue-ordered assortments

Proposition 5 (Berbeglia and Joret, [7]).

Proposition 6.

4.2. pp-choice facility location problem

Proposition 7.

Proof.

4.3. On minimization problems

5. Conclusion

References

4.2. $p$ -choice facility location problem