1 Introduction

Combinatorial optimization is one of the most active fields in Discrete Mathematics and Operations Research. Problems in this area have been widely studied, due to their many applications, but also because the analysis of their structural properties has had deep implications for understanding some difficult aspects of discrete optimization. Most classical combinatorial optimization problems have been studied for additive objective functions. Nevertheless, other objectives have also been considered, particularly for some applications. Some examples include minimax problems (Hansen 1980; Schrijver 1983), combining minisum and minimax (Averbakh et al. 1995; Hansen and Labbé 1988; Hansen et al. 1991; Minoux 1989; Punnen et al. 1995; Tamir et al. 2002), k-centrum optimization (Garfinkel et al. 2006; Kalcsics et al. 2002; Punnen 1992; Slater 1978a, 1978b; Tamir 2000), lexicographic optimization (Calvete and Mateo 1998; Della Croce et al. 1999), k-th best solutions (Lawler 1972; Martello et al. 1984; Pascoal et al. 2003; Yen 1970/1971), most uniform solutions (Galil and Schieber 1998; López de los Mozos et al. 2008), minimum-envy solutions (Espejo et al. 2009), solutions with minimum deviation (Gupta et al. 1990), regret solutions (Averbakh 2001; Conde 2004; Puerto and Rodríguez-Chía 2003), equity measures (Gupta and Punnen 1988; López de los Mozos et al. 2008; Mesa et al. 2003; Punnen and Aneja 1997), discrete ordered median location problems (Boland et al. 2006; Marín et al. 2009; Puerto 2008; Puerto and Tamir 2005), and covering objectives (Balas and Padberg 1972; Breuer 1970; Christofides and Korman 1974–1975; Kelly 1944; Lawler 1966); among many others. (The reader is referred to the comprehensive list of references in Schrijver 2003 for different objectives functions and applications in combinatorial optimization.)

Despite the long and incomplete list of objective functions mentioned above, there is one aspect that has been only partially covered in the literature and will be the goal of this paper: optimization with ordering. In this work we address discrete optimization problems in which the objective function is defined over the subsets of a ground set E, but it is not necessarily additive over all the elements of each subset. In particular, we consider discrete optimization problems with ordering requirements. That is, we are given a ground set E, an implicit ordering on the elements of E, and a cost function that evaluates each subset S of E in such a way that it may assign a different value to a given element depending on its ordering relative to the remaining elements of S. This type of problems generalizes most of the objective functions mentioned above. Moreover, new meaningful objective functions can be easily cast within this framework.

Our models share some common points with problems that consider ordering, in particular with the well-known linear ordering problem (Grötschel et al. 1984; Reinelt 1985) in which the objective is to find the best ordering or permutation of a finite set of elements relative to some criterion. Unlike the linear ordering problem, discrete problems with ordering requirements aim at finding the feasible subset of E whose evaluation relative to the cost function induced by the ordering is optimized. From this point of view, these problems can be seen as complementary to Linear Ordering Problems.

The interest of the problems that we study comes not only from a theoretical point of view, but also from the potential applications of the considered models. For instance, problems where decisions must be made according to a given priority or hierarchy, sequencing problems with precedence constraints, discrete multiperiod problems where the cost of any element depends on the period when the decision is made and, from a more general point of view, ordered median problems (see for instance, Kalcsics et al. 2010 and Nickel and Puerto 2005 for a description of several ordered median problems on different contexts, Möhring 1989, Schulz 1996 for scheduling problems or Boyd 1993, Stanley 1986 for problems with precedence constraints). We can think of matching or spanning tree problems on networks where matched (connected) nodes interchange information. Assume that setup costs are proportional to distance and quality of communication (noise) depends on the distance between pairs, so that the system wants to penalize long distances, in such a way that longest distances receive higher penalties, to enforce as much as possible homogeneous (not noisy), short connections. One way to model such a situation is to establish, in any solution, a priori correcting factors associated with edges sorted by length: the largest weight will always correct the longest edge in the solution, the second largest corrects the second longest, and so on. In this setting, we would solve the corresponding combinatorial problem (matching, spanning tree…) with an objective function that looks for a minimum total sorted weighted distance. These problems have not been considered in the literature of combinatorial optimization; yet being of interest.

In all the problems that we study, the evaluation of feasible subsets depends on the relative position of the elements with respect to the sorted sequence of their costs. As we will see, the solutions to the considered problems can be seen as ordered sequences that induce a structure of an independence system. In most cases we will describe the set of feasible solutions in terms of an integer polytope. The first problem that we study, the Simple Ordering Problem (SOP), is such that any subset of the ground set defines a feasible solution, whereas in the Simple Ordering Problem with Cardinality Constraint (SOPC) feasible solutions are required to have a fixed number of elements. For these two problems we give a full description of the integer polytope of the feasible set by means of an exponential number of inequalities. We show that these inequalities can be separated in polynomial time, thus providing polynomial time resolution methods. Moreover, we prove that both problems can be equivalently stated as shortest path problems on specialized networks which gives alternative polynomial time solution schemes.

The goal in this paper is twofold. On the one hand, we have a theoretical interest in analyzing the combinatorial structure of the simple ordering problem, thus relating it to some known problems and providing some polyhedral description of its polytope. On the other hand, we want to incorporate this information to some other combinatorial optimization problems where we wish to impose specific ordering constraints induced by the position of the elements in sorted lists that fit exactly with the structure of SOP. Specifically, we are interested in combinatorial problems that look to minimize ordered weighted averages (ordered median) of the elements in a solution set. Examples of such type of problems are the generalized balanced optimization problem (Punnen and Aneja 2004; Turner et al. 2011) which generalizes the k-sum optimization problem (Gupta and Punnen 1988), the balanced optimization problem and the lexicographical balanced optimization problem (Martello et al. 1984), the generalized bottleneck problem (Punnen et al. 1995), the robust combinatorial optimization problem (Bertsimas and Sim 2003) and the ordered median objective applied to spanning trees (Puerto and Tamir 2005), assignments, matchings, paths or matroids; among others. In these problems, any elements e in the ground set have a weight w(e) and the goal is to find, for a given set of λ-weights, the combinatorial structure that minimizes the λ-ordered weighted sum of its elements where the λ-weight of an element is dependent on its sorted position with respect to sequence of its w-weight. For example, if \(T=\{e_{i_{1}},\ldots,e_{i_{n-1}}\}\) are the edges of a spanning tree of a graph and \(w(e_{i_{1}})\ge\cdots\ge w(e_{i_{n-1}})\) then the objective function evaluation would be \(\sum_{j=1}^{n-1} \lambda_{j} w(e_{i_{j}})\). All these problems share a common structure that is compatible with the Simple Order Polytope analyzed in this paper. Assuming simple shapes of the λ-weights, there exist combinatorial algorithms for some of the above mentioned problems. However, for general λ-weights most of them have either unknown complexity or they are already NP-hard. We expect that the properties and description of SOP will be useful to be combined with the specific characteristics of each particular problem to develop algorithmic procedures for its exact or approximate resolution.

The paper is organized in four sections. Section 1 is devoted to the SOP. There, we formulate the problem and give a polyhedral description of its feasible solutions set. In addition, we prove that SOP reduces to a shortest path problem on an ad hoc graph and thus, that the problem is polynomially solvable. Section 3 deals with the SOPC. We prove that properties similar to those of SOP also hold for this problem and we give a polyhedral description and a polynomial resolution approach. The last section draws some conclusions and outlines future research continuations of this work.

2 The simple ordering problem and some properties

Let E={e 1,…,e n } be a finite ground set, and assume that we are given a hierarchy on E induced by an order function c:E⟶ℝ, such that c 1:=c(e 1)≥⋯≥c n :=c(e n ). A sequence of elements \(F=\{e_{j_{1}},\ldots, e_{j_{r}}\}\), F⊆E, is an ordered chain if \({c(e_{j_{i}})}\ge c(e_{j_{i+1}})\) for i=1,…,r−1. Consider the sets of indices N={1,…,n}, K={1,…,p} and let \((d_{i}^{j})_{i\in N, j\in K}\) be a given real matrix. Furthermore, let Γ denote the set of monotonic functions from N to K. That is, Γ contains all functions γ:N⟶K, such that γ(i)≤γ(j) iff i≤j. Let also \(\widehat{d}:E \times \Gamma \longrightarrow \mathbb{R}\) be such that for an ordered chain F⊆E, \(F=\{e_{j_{1}}, \dots, e_{j_{r}}\}\), with r≤p, and for a given γ∈Γ, \(\widehat{d} (F,\gamma)=\sum_{k=1}^{r} d_{j_{k}}^{\gamma(j_{k})}\). The Simple Ordering Problem (SOP) is to find the ordered chain of E and the function γ∈Γ of maximal total weight with respect to \(\widehat{d}\).

One of the main difficulties for addressing SOP is that the objective function d E is not additive. Next we present an alternative statement of the problem that allows to reformulate the SOP as an optimization problem with an additive objective function.

Let us consider the multiset E K that contains p copies of each element e∈E. For each e∈E, k∈K, e k∈E K denotes the k-th copy of element e, and E k denotes the subset of E K that contains the k-th copy of all the elements, that is E K =E 1∪⋯∪E p. Without loss of generality, we will represent any subset of elements F⊆E K by \(F=\{e_{j_{1}}^{k_{1}}, \ldots,e_{j_{r}}^{k_{r}}\}\) with k 1≤⋯≤k r . Notice that any element of F is associated both with an element of E and with an order index (element of K).

Let also d be a given weight function on E K defined as

Throughout, d will be represented by means of a n×p matrix, where the rows indicate the elements of E and the columns indicate the index k∈K.

We use the standard compact notation \(f(A)\equiv\sum_{e_{j}^{k}\in A}f_{j}^{k}\) when A⊆E K , and f is a vector or a function defined on E K .

Definition 2.1

  1. 1.

    F⊆E K is an ordered sequence if \(F=\{e_{j_{1}}^{k_{1}},\ldots, e_{j_{r}}^{k_{r}}\}\) is such that k i <k i+1 and j i <j i+1 for i=1,…,r−1.

  2. 2.

    Given F⊆E K , a subset S⊆F is a maximal ordered sequence in F if S is an ordered sequence and there does not exist any ordered sequence R⊆F such that S⊂R.

One of the main characteristics of any subset F⊆E K is the length of the maximal ordered sequence in F, that we denote ℓ(F),

$$\ell(F)=\max\{|S|: S\subseteq F, \; S \mbox{ is an ordered sequence}\}.$$

Note that F is an ordered sequence if and only if ℓ(F)=|F|.

We can now reformulate the SOP as the problem of finding the ordered sequence of E K of maximal total weight with respect to d. In particular, the SOP can be stated as the problem of finding a subset F ∗⊆E K such that

Remark 2.1

When different weight functions d are considered, the optimal solutions to the SOP do not necessarily have the same cardinality. For instance, when all the components of d are non-positive the empty set is an optimal solution, i.e. an ordered sequence with null cardinality. Nevertheless, it is indeed possible to find examples in which an optimal solution has any number of ordered elements in the range [1,p].

Remark 2.2

When F⊆E K is an ordered sequence, then S is also an ordered sequence, for all S⊆F. Therefore, \(I=(E_{K},\mathcal{F})\) is an Independence System, where \(\mathcal{F}=\{F\subset E_{K}: F\) is an ordered sequence}. However, \(I=(E_{K},\mathcal{F})\) is not a matroid since, for a given F, it is possible to find two maximal ordered sequences S,T⊆F such that ℓ(S)≠ℓ(T), as the following example shows.

Let E={e 1,e 2,e 3} and K={1,2,3}. Suppose c 1≥c 2≥c 3. The set \(F=\{e_{2}^{1}, e_{3}^{2},e_{1}^{3}\}\) contains two maximal ordered sequences \(S^{1}=\{e_{2}^{1}, e_{3}^{2}\}\) and \(S^{2}=\{e_{1}^{3}\}\), which have different lengths: ℓ(S 1)=2, ℓ(S 2)=1.

Remark 2.3

The function ℓ(⋅) is not submodular, since for some given F⊂E K , \(e_{j_{1}}^{k_{1}}, e_{j_{2}}^{k_{2}}\notin F\),

$$\ell(F\cup\{e_{j_1}^{k_1}\})- \ell(F)\ge \ell(F\cup\{e_{j_1}^{k_1}, e_{j_2}^{k_2}\})-\ell(F\cup\{e_{j_1}^{k_1}\})$$

does not necessarily hold. For instance, in the above example, when \(F=\{e_{1}^{3}\}\), \(e_{j_{1}}^{k_{1}}=e_{2}^{2}\), \(e_{j_{2}}^{k_{2}}=e_{3}^{3}\), then \(\ell(\{e_{1}^{3},e_{2}^{2}\})- \ell(\{e_{1}^{3}\})=1-1=0<1= \ell(\{e_{1}^{3},e_{2}^{2},e_{3}^{3} \})- \ell(\{e_{1}^{3},e_{2}^{2}\})\).

As a consequence, the polytope

$$P(\ell)=\{x\in R^{n\times p}: x(F)\le \ell(F), F\subseteq E_K\}$$

is not a polymatroid (Groetschel et al. 1993).

Remark 2.4

Given that \(I=(E,\mathcal{F})\) is not a matroid nor P(ℓ) is a polymatroid, the greedy algorithm needs not produce an optimal solution. Consider, the above example with d given by

$$d=\left( \begin{array}{c@{\quad}c@{\quad}c}2 & 0 & 1\\2 & 2 & 1\\3 & 0 & 0\end{array} \right).$$

The greedy algorithm would give the solution \(S=\{e_{3}^{1}\}\) with objective function value 3. However the optimal solution is \(\overline{S}=\{e_{1}^{1},e_{2}^{2}\}\), with objective function value 4.

The next lemma states the SOP as a special case of the longest path problem on a directed acyclic graph.

Lemma 2.1

The SOP can be stated as a longest path problem on a directed acyclic graph (DAG) with \(\mathcal{O}(np)\) nodes and \(\mathcal{O}(n^{2}p^{2})\) arcs.

Proof

Consider the auxiliary digraph \(\overline{G}=(V_{0}\cup \{s,t\}, \mathcal{A})\) where V 0=E K and each pair \(e_{j}^{k}, e_{j'}^{k'} \in E_{K}\) with j<j′ is connected by an arc \((e_{j}^{k}, e_{j'}^{k'})\) if and only if k′>k. The cost of arc \((e_{j}^{k}, e_{j'}^{k'})\) is \(d_{j'}^{k'}\). There is a fictitious source node s that is connected with each node \(e_{j}^{k}\in V_{0}\) with an arc \((s, e_{j}^{k})\) of cost \(d_{j}^{k}\). Similarly, t is a fictitious sink node that is connected with the source node s with an arc (s,t) of cost zero, and with each node \(e_{j}^{k}\in V_{0}\) with an arc \((e_{j}^{k}, t)\) of cost zero. Note that \(\overline{G}\) is an acyclic graph, where arcs correspond to ordered pairs of elements of E K that can be part of a feasible solution to the SOP. Therefore, every s−t-path in \(\overline{G}\) corresponds to a feasible solution to the SOP and for each feasible solution to SOP there is a s−t-path in \(\overline{G}\) that represents it. The objective function value of a solution to SOP and that of its associated s−t-path coincide. Thus, the SOP can be stated as the problem of finding a longest path in \(\overline{G}\). □

As the longest path problem on a directed acyclic graph can be solved in \(\mathcal{O}(|E|)\), the SOP can be solved in \(\mathcal{O}(n^{2}p^{2})\). More efficient ad hoc dynamic programming algorithms can be used to solve the SOP in \(\mathcal{O}(np)\) (Tamir 2009). However, as mentioned in the introduction, our goal is not to propose the most efficient solution algorithm for the SOP, but to study the polyhedral structure of the SOP, as a basis for the study of the polyhedral structure of more complex discrete optimization problems with ordering, which cannot be solved in polynomial time.

Let \(\overline{A}\) denote the node-arc incidence matrix of \(\overline{G}\) (as introduced in the proof of Lemma 2.1), \(\overline{d}\) the cost function on its arcs and b a column vector of dimension |V 0|+2 whose components are associated with the nodes of \(\overline{G}\), and take value zero excepting those corresponding to the source and sink nodes that take values 1 and −1, respectively. As a consequence of Lemma 2.1, by defining decision variables z associated with the arcs of \(\mathcal{A}\), the SOP can be formulated as

where \(P_{\overline{G}}=\{z \in [0,1]^{|\mathcal{A}|}:\overline{A}z = b\}\). Given that \(\overline{A}\) is a node-arc incidence matrix, it is totally unimodular and, thus, all the vertices of \(P_{\overline{G}}\) are integer. The dimension of the space where \(P_{\overline{G}}\) is defined is n 2×p 2, which becomes quite big even for a moderate number of nodes n. Also, the definition of the variables may seem unnatural for the SOP. Therefore, a question that arises is whether there is an “easier” polytope (for instance, of lower dimension) that is still integral for this problem. Next we give a positive answer to the above question which, not surprisingly, is given in terms of the “natural” decision variables for the SOP. Define the binary decision variables:

$$x_{jk}=\left\{\begin{array}{l@{\quad}l}1, & \mbox{if element $e_{j}^{k} \in E^{k}$ is selected,}\\0, & \mbox{otherwise}.\end{array} \right.$$

The condition that the selected elements define an ordered sequence can be modeled by means of the set of constraints:

$$x_{jk} + \sum_{j'\leq j} x_{j'k'}\leq 1, \quad \forall j\in N,\ \forall k, k'\in K,k'>k$$

which, for all j∈N,k∈K, guarantee that if element \(e_{j}^{k}\) is selected, then no element with j′≤j will be selected for any k′>k. Given that in an ordered sequence, at most one element in E k can be chosen, the above constraints can be easily reinforced to (see Fig. 1):

$$\sum_{j'\ge j}x_{j'k} + \sum_{j'\leq j} x_{j'k'}\leq 1, \quad \forall j\in N,\ \forall k, k'\in K, \,k'>k.$$
Fig. 1
figure 1

Successive reinforcement of order constraints: inequalities (4), (6) and (7)

Full size image

Therefore, we propose the following new integer linear programming formulation for the SOP

(1)
(2)
(3)
(4)
(5)

Constraints (2) guarantee that at most one element is selected from each E k, k∈K. Constraints (3) ensure that at most one copy of any original element is selected. As indicated above, inequalities (4) imply that solutions are ordered sequences. Finally, (5) are the integrality conditions on the variables.

It is easy to check that when integrality constraints on the variables are removed the polytope of the resulting linear program has fractional vertices. Consider, for instance, the SOP, where E={e 1,e 2,e 3,e 4}, p=3 and d given by the matrix

$$d=\left( \begin{array}{c@{\quad}c@{\quad}c}4 & 0 & 0 \\0 & 4 & 20 \\20 & 0 & 0 \\0 & 0 & 4\end{array} \right). $$

For any order function c such that c 1≥c 2≥c 3≥c 4, the optimal solution to the Linear Programming relaxation to program (1)–(4) is given by \(x_{11}=x_{31}=x_{22}=x_{23}=x_{43}=\frac{1}{2}\).

Inequalities (4) can be reinforced to the following set of inequalities (6) (see Fig. 1 where we have added to the right hand side of constraint (4) all the elements in the j-th row between the k-th and k′-th columns):

(6)

As can be seen the fractional solution of the above example is cut-off with the inequality of type (6) with j=2, k=1 and k′=3. However, the polytope of the linear program associated with constraints (2), (3) and (6) still has fractional vertices as the following example shows.

Example 2.1

Consider the SOP, where E={e 1,e 2,e 3,e 4}, p=4 and d given by the following matrix:

$$d=\left(\begin{array}{c@{\quad}c@{\quad}c@{\quad}c}4 & 0 & 0 & 24 \\0 & 0 & 20 & 0 \\0 & 20 & 0 & 0 \\24 & 0 & 0 & 0\end{array} \right).$$

For any order function c such that c 1≥c 2≥c 3≥c 4, the optimal solution of the Linear Programming relaxation to the program with objective function (1) and set of constraints (2), (3) and (6) is given by \(x_{11}=x_{41}=x_{32}=x_{23}=x_{14}=\frac{1}{3}\).

Next, we introduce some new inequalities that are stronger than constraints (6). As we will see the new constraints cut-off all fractional vertices of (2), (3), (6).

Definition 2.2

A set H⊂E K is called a staircase if \(e_{j}^{k}, e_{j'}^{k'}\in H\) and j′≤j, then k≤k′.

In the next proposition we see that no two elements of a staircase may belong to an ordered sequence.

Proposition 2.1

Let H be a staircase. Then the inequality

(7)

is valid for SOP.

Proof

Note that \(e_{j}^{k}\), \(e_{j'}^{k'}\in H\) and at the same time being part of a feasible solution \(\hat{x}\), i.e. \(\hat{x}_{jk}=\hat{x}_{j'k'}=1\) is impossible since by definition of staircase the first condition requires j′≤j and k≤k′, whereas feasibility implies j<j′ and k<k′. Hence, no feasible solution to the SOP contains more than one element of any staircase. □

Inequalities (7) generalize all the inequalities considered so far since, inequalities (2), (3), (4) and (6) are particular cases of inequalities (7). In particular:

  • inequalities (2) correspond to staircases \(H_{2}^{k}=E^{k}\), k∈K;

  • inequalities (3) correspond to staircases \(H_{3}^{j}=\{e_{j}^{k}, k\in K\}\), j∈N;

  • inequalities (4) correspond to staircases \(H_{4}^{j, k, k'}=\{e_{j'}^{k}, j'\ge j\}\cup \{e_{j'}^{k'}, j'\le j\}\) j∈N and k,k′∈N, such that, k′>k; and

  • inequalities (6) correspond to staircases \(H_{6}^{j, k, k'}=\{e_{j'}^{k}, j'\ge j\}\cup\{e_{j}^{h}, k<h<k'\}\cup \{e_{j'}^{k'}, j'\le j\}\) j∈N and k,k′∈N, such that, k′>k.

A staircase H is maximal if there does not exist another staircase H′ such that H⊂H′. Since non-maximal staircases are contained in maximal staircases, the only non dominated inequalities (7) are associated with maximal staircases. Observe that the number of elements in maximal staircases is n+p−1 and that both \(e_{n}^{1}\) and \(e_{1}^{p}\) belong to any maximal staircase. Note also that there is an exponential number of maximal staircase inequalities.

The successive reinforcement of the inequalities can be appreciated graphically in Fig. 1.

Remark 2.5

Maximal staircases of E K are associated with maximal cliques in the undirected graph G=(V 0,E 0) defined such that, V 0=E K and \(e_{j}^{k},e_{j'}^{k'} \in E_{K}\) with j′≤j are connected by an edge if and only if k≤k′. (Observe that the directed version of the complement of G, is the graph \(\overline{G}\) defined in Lemma 2.1.) Indeed, given a maximal staircase H and \(e_{s}^{t} \in V_{0} \setminus H\), we have that there exist either \(e_{s-1}^{k} \in {H}\) with k<t or \(e_{s+1}^{k} \in {H}\) with k>t. Therefore, \({H} \cup \{e_{s}^{t}\}\) is not a clique for any maximal staircase H and for any \(e_{s}^{t} \in V_{0} \setminus {H}\).

Consider now the polytope associated with maximal staircases:

$$P_{S}=\Big\{x\in [0,1]^{n\times p}: x({H})\leq 1, \ \mbox{for all maximal staircase } {H} \subset E_K \Big\}.$$

The next theorem states that P S is all integer proving that the graph G in Remark 2.5 is a perfect graph. This argument given in Loos et al. (2009) simplifies an earlier proof by the authors.

Theorem 2.1

The polytope P S is all integer.

Proof

First, we observe that staircases describe all the cliques of the graph G=(V 0,E 0). Thus, P S is the so called fractional node packing polytope. Therefore, proving that P S is integer is equivalent to prove that the graph G is perfect, see Nemhauser and Wolsey (1998, Definition 5.5).

To this end, we prove that G itself is a comparability graph (and therefore perfect, Schrijver 2003, Corollary 66.2a), with respect to the partial order

$$(i,j) < (i',j')\quad \mbox{iff}\quad i\ge i', j\le j',\quad \mbox{and}\quad (i,j) \ne (j,j').$$

Indeed one can orient each arc of G according to the direction given by this partial order: (i,j)→(k,l) for k≤i and l≥j. Then such an orientation is transitive since (s,t)→(i,j)→(k,l) implies \(s\ge i\ge k,\;t\le j\le l\), and this is a sufficient condition for the graph G being a comparability graph. □

As we have seen, P S is an integer polyhedron. However, it has a number of inequalities (7) that is exponential on the number of elements of E K . Thus, the solution to the separation problem is fundamental to guarantee the usefulness of P S in an algorithmic framework. Polynomial time separation algorithms based on semidefinite programming exist for the separation problem on a general perfect graph (see for instance Groetschel et al. 1984).

In our framework, taking advantage of the structure of the problem, we present an ad-hoc, simpler separation algorithm. For a given \(\hat{x}\in \mathbb{R}^{n\times p}\) such that \(0\leq \hat{x}_{jk}\leq 1\), for all j∈N,k∈K, the separation problem for inequalities (7) consists of finding a staircase H⊂E K such that \(\hat{x}(H)>1\), or to determine that no such set exists. We define an auxiliary network \(N(\hat{x})=(V_{\hat{x}}\cup\{s,t\}, A(\hat{x}))\) to be the directed version of the subgraph of G defined in Remark 2.5 induced by the solution \(\hat{x}\). That is, \(V_{\hat{x}}=\{e_{j}^{k}\in E_{K}:\hat{x}_{jk}>0\}\) is the support of \(\hat{x}\), s and t are a fictitious source and sink node, respectively. The set \(A(\hat{x})\) contains the following arcs:

  1. 1.

    One arc \((s, v_{j}^{k})\) of cost \(\hat{x}_{jk}\), associated with each node \(v_{j}^{k}\in V_{\hat{x}}\).

  2. 2.

    One arc \((v_{j}^{k}, v_{j'}^{k'})\) of cost \(\hat{x}_{j'k'}\), connecting each pair of nodes \(v_{j}^{k}, v_{j'}^{k'}\in V_{\hat{x}}\), with j≥j′ and k≤k′.

  3. 3.

    One arc \((v_{j}^{k}, t)\) of cost zero, for each node \(v_{j}^{k}\in V_{\hat{x}}\).

Proposition 2.2

For a given \(\hat{x}\in \mathbb{R}^{n\times p}\) such that \(0\leq \hat{x}_{jk}\leq 1\), for all j∈N,k∈K, the separation problem for inequalities (7) can be solved in polynomial time by finding the s−t-path of maximum cost in \(N(\hat{x})\).

Proof

Let \(P_{\hat{x}}\) be an s−t-path in \(N(\hat{x})\), and let \(H_{P_{\hat{x}}}\) denote its set of nodes after eliminating s and t. By construction of \(N(\hat{x})\), \(H_{P_{\hat{x}}}\) defines a staircase. Also, by the definition of the cost function on the arcs of \(N(\hat{x})\), the cost of \(P_{\hat{x}}\) gives \(\hat{x}(H_{P_{\hat{x}}})\). Thus, the staircase H ∗ with a maximum value of the left hand side of constraint (7) can be obtained by finding the s−t-path \(P_{\hat{x}}^{*}\) with maximum cost. If the value of \(P_{\hat{x}}^{*}\) is strictly greater than 1, then \(H^{*}=H_{P^{*}_{\hat{x}}}\) is a staircase that defines a violated inequality (7). Otherwise, if the cost of \(P_{\hat{x}}^{*}\) is smaller than or equal to one, there is no inequality (7) violated by \(\hat{x}\).

Finally, note that \(N(\hat{x})\) is acyclic by construction. Again, an ad hoc dynamic programming algorithm of complexity \(\mathcal{O}(np)\) can be used to find the maximum s−t-path in \(N(\hat{x})\). □

We finish this section with an informal comparison between polyhedra \(P_{\overline{G}}\) and P S . While \(P_{\overline{G}}\) has a polynomial number of constraints \(\mathcal{O}(np)\), it has \(\mathcal{O}(n^{2}p^{2})\) variables. On the other hand, P S has a considerably smaller number of variables \(\mathcal{O}(np)\) but an exponential number of constraints. However, as we have just shown, these constraints can be separated in \(\mathcal{O}(np)\) time. A deep comparison between the two polyhedra is beyond the scope of this work and would require a thorough computational experimentation to evaluate the usefulness of each of them.

3 The simple ordering problem with cardinality constraints

The Simple Ordering Problem with Cardinality Constraint (SOPC) is the variant of the SOP that arises when |K| cardinality constraints requiring that feasible solutions contain exactly one element of each E k, k∈K are posed. Therefore, in the SOPC feasible solutions consist of p elements \(\{e_{j_{1}}^{1}, \ldots, e_{j_{p}}^{p}\}\), \(e_{j_{k}}^{k}\in E^{k}\), k∈K such that \(c_{j_{1}}\ge \cdots \ge c_{j_{p}}\). The requirement that exactly one element of each E k, k∈K, is selected can be modeled by means of the constraints

$$ \sum\limits_{j\in N}x_{jk}=1,\quad\mbox{for all } k\in K.$$
(8)

Given that feasible solutions to the SOPC must also fulfill the ordering constraints, the maximal staircase inequalities must hold. Recall that, in particular, these constraints forbid solutions that contain more than one element of any set E k, k∈K. Thus, in the SOPC the set of constraints (8) can be substituted by one single constraint of the form

$$ \sum\limits_{k\in K}\sum\limits_{j\in N}{x_{jk}}=p.$$
(9)

Consider now the polyhedron

$$P_{SC}=\Big\{x\in [0,1]^{n\times p}: x(H)\leq 1, \mbox{ for all maximal staircase } H\subset E_K,\mbox{ and } \sum\limits_{k\in K}\sum\limits_{j\in N}{x_{jk}}=p\Big\}.$$

The goal is to prove the integrality of the above polytope. The reader may note now that we cannot use the comparability graph argument of the previous section. Indeed, that argument applies for polytopes of the form x(H)≤1 but in this case we have an additional constraint with right-hand-side equal to p>1. Moreover, the analogous of graph G (see the proof of Theorem 2.1) required in this case does not satisfy transitivity and therefore cannot be a comparability graph. In order to prove the integrality of P SC , we give the following result.

Theorem 3.1

The polytope P SC is all integer.

Proof

In order to address the integrality condition of P SC , we will prove that the set of optimal solutions to the linear relaxation for SOPC defined on P SC coincides with the set of optimal solutions to the linear relaxation for SOP defined on P S when we add a huge number to the weight of each element. Once, this assertion has been proved, as the linear relaxation for SOP is integral it also follows that SOPC is integral.

First, given an instance τ of SOPC, consider the instance τ W obtained by adding a big weight W to the weight associated with each element of E K , i.e., \(\overline{d}_{j}^{k}=d_{j}^{k}+W\). For W sufficiently big (for instance, \(W=\sum_{k \in K} \sum_{j \in N } |d_{j}^{k}|\)) τ and τ W have the same set of optimal solutions (as we only changed the objective function by a constant value pW). Moreover, the sets of optimal solutions to the linear programs associated with τ and τ W also coincide (again only their values differ by pW).

Furthermore, due to the effect of the big weight W, the set of optimal solutions to τ W considered as a SOP instance (without cardinality constraint) also coincides with that of τ W considered as a SOPC instance. Again, this also holds for their corresponding linear programming relaxations.

Consider now the set of extreme points of P SC and suppose toward contradiction that there exists an extreme point x∈P SC which is not an extreme point of P S . Since x is an extreme point of P SC there exists an SOPC instance τ such that x is the unique optimal solution to τ. From the above discussion, x is also the unique optimal solution to τ W considered both as SOPC and as SOP. Thus, x must be an extreme point of P S and therefore P SC is also integral. □

Therefore, analogously to the case of P S we can prove the following result:

Theorem 3.2

The polytope P SC is all integer and the SOPC can be solved in polynomial time.

4 Conclusions

Nowadays, ordering requirements appear in many real life situations as, for instance, those related to scheduling, multiperiod decision-making, and hierarchical problems, among others. Therefore, it is challenging to consider models that are better suited for such real world situations by capturing the ordering nature. However, the inclusion of the ordering requirements within a discrete problem implies additional difficulties that need to be addressed and solved. We have obtained interesting properties of the polyhedral structure of the considered problems. In this regard, our study can be considered as an initial analysis on these types of problems, and it opens new avenues of research for discrete optimization problems with ordering requirements. In particular, in an ongoing research, we are applying the results in this paper to analyze the polyhedral structure of more general optimization problems with ordering requirements (ordered median maximum weighted spanning tree and ordered median maximum weighted matching problems). At a longer term we believe that our results can be useful for addressing more general ordered median combinatorial optimization problems. The valid inequalities developed in this paper are the basis for obtaining new ones in these alternative problems.

Another future line of research would be to consider the problem of finding a maximum weight chain of cardinality p within a general partial order with weights on the elements. In particular, we wonder whether one can generalize the result of SOPC to this problem.