quadratic semi assignment problem

Quadratic optimal transportation problem with a positive semi definite structure on the cost function

1 introduction, 1.1 introduction.

Optimal Transportation problem (OT) has been an active research area in last decades, and many questions in the field are studied a lot. In addition, as OT gives a way to metrize a probability space, OT has a wide range of applications. While OT was used in wide application area, there were some application situations where a few aspects of OT needed to be modified to fit in the situation. As such, there has been a lot of versions of OT such as multi-marginal OT ( [ 23 ] , [ 16 ] , [ 22 ] , [ 11 ] ), optimal partial transportation problem( [ 9 ] , [ 17 ] , [ 8 ] ), congested transportation problem( [ 6 ] ), martingale transportation problem( [ 3 ] , [ 13 ] , [ 2 ] ), co-OT( [ 24 ] ), etc. In this paper, we introduce another version of OT.

Problem (0-1) .

Problem LABEL:Prbm_0-1 can be regarded as a quadratic version of OT, written in Monge’s formulation. The problem that corresponds Katorovich’s relaxed formation of OT is the following.

Problem (0-2) .

Some readers may familiar with this problem already due to the studies about Gromov-Wasserstein distance.

This type of quantity can also be found in [ 25 ] , where the author defines L p subscript 𝐿 𝑝 L_{p} italic_L start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT distortion distance between two metric measure spaces in the form of ( 1 ) and construct the space of metric measure spaces. We would like to comment that there is another result [ 4 ] by R. Cabrera about where the author studies Problem LABEL:Prbm_0-1 with dynamic setting.

The motivation of Problem LABEL:Prbm_0-1 in this paper, however, arises from a data dimension reduction algorithms such as t-SNE [ 26 ] and UMAP [ 21 ] . In data science, it is an important problem to design an algorithm which let us save the data points from very high dimension in low dimension such as ℝ 2 superscript ℝ 2 \mathbb{R}^{2} blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT or ℝ 3 superscript ℝ 3 \mathbb{R}^{3} blackboard_R start_POSTSUPERSCRIPT 3 end_POSTSUPERSCRIPT preserving some structures of the point clouds. For instance, in t-SNE algorithm which is designed in [ 26 ] , the authors define affinities p i ⁢ j subscript 𝑝 𝑖 𝑗 p_{ij} italic_p start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT and q i ⁢ j subscript 𝑞 𝑖 𝑗 q_{ij} italic_q start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT which quantifies similarity of two points x i subscript 𝑥 𝑖 x_{i} italic_x start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT and x j subscript 𝑥 𝑗 x_{j} italic_x start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT in high dimension and y i subscript 𝑦 𝑖 y_{i} italic_y start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT and y j subscript 𝑦 𝑗 y_{j} italic_y start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT in low dimension respectively, and use KL-divergence ∑ p ⁢ log ⁡ p q 𝑝 𝑝 𝑞 \sum p\log\frac{p}{q} ∑ italic_p roman_log divide start_ARG italic_p end_ARG start_ARG italic_q end_ARG to measure the difference between p i ⁢ j subscript 𝑝 𝑖 𝑗 p_{ij} italic_p start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT and q i ⁢ j subscript 𝑞 𝑖 𝑗 q_{ij} italic_q start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT . Then t-SNE algorithm seeks a set of points in the low dimension which minimizes the KL-divergence. Existence of such set of points { y i } subscript 𝑦 𝑖 \{y_{i}\} { italic_y start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT } in the low dimension was studied in [ 1 ] , and [ 14 ] . Then, letting T 𝑇 T italic_T be a function such that T ⁢ ( x i ) = y i 𝑇 subscript 𝑥 𝑖 subscript 𝑦 𝑖 T(x_{i})=y_{i} italic_T ( italic_x start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) = italic_y start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , we see that T 𝑇 T italic_T solves Problem LABEL:Prbm_0-1 with c = p ⁢ log ⁡ p q 𝑐 𝑝 𝑝 𝑞 c=p\log\frac{p}{q} italic_c = italic_p roman_log divide start_ARG italic_p end_ARG start_ARG italic_q end_ARG . Hence, to study the structure of the projection T 𝑇 T italic_T , it is necessary to study Problem LABEL:Prbm_0-1 .

The goal of this paper is to introduce the quadratic optimal transportation problem . We explore some basic properties of the quadratic optimal transportation problem analogous to OT, and discuss extra structures of the quadratic optimal transportation problem. The main theorem of this paper is the duality for the quadratic transportation problem with a structural assumption on the cost function.

Theorem (Duality, rough statement) .

For squared cost function c 𝑐 c italic_c , we have the following identity

where the infimum and supreme are taken over some admissible sets.

The squared cost function is defined in Section 3 and the admissible sets are described in Section 2 and 4 .

This paper consists as follows. In section 2 , we introduce the quadratic optimal transportation problem and compare the problem with other versions of OT. In section 3 , we explore some basic properties of the quadratic optimal transportation problem. In 4 , we provide a duality formula for a certain type of cost function. In the appendices, we derive a related partial differential equation formally and provide some background theory for the classical optimal transportation problem which are used in this paper.

1.2 Notations

2 quadratic transportation problem, 2.1 quadratic transportation problem.

We restate the problem that we consider in this paper in detail. Let c : Z × Z → ℝ : 𝑐 → 𝑍 𝑍 ℝ c:Z\times Z\to\mathbb{R} italic_c : italic_Z × italic_Z → blackboard_R be a lower semi-continuous function. Then the problem states as follows.

Problem 1 .

Find a measurable function T : X → Y : 𝑇 → 𝑋 𝑌 T:X\to Y italic_T : italic_X → italic_Y which achieves the following infimum

among the measurable functions that satisfies T ♯ ⁢ μ = ν subscript 𝑇 ♯ 𝜇 𝜈 T_{\sharp}\mu=\nu italic_T start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_μ = italic_ν , where T ♯ ⁢ μ subscript 𝑇 ♯ 𝜇 T_{\sharp}\mu italic_T start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_μ is the push-forward measure.

We call the above problem Monge formulation of the quadratic optimal transportation problem, or simply Monge QOT. We call a solution to Monge QOT a Monge solution. Monge QOT is highly non-linear with respect to T 𝑇 T italic_T . However, Using Kantorovich’s relaxation as in the classical optimal transportation theory, we can reduce the non-linearity to the quadratic dependency. We first define

Then the Kantorovich formulation of the quadratic optimal transportation problem (Kantorovich QOT) is the following.

Problem 2 .

Find π 0 ∈ Π ⁢ ( μ , ν ) subscript 𝜋 0 Π 𝜇 𝜈 \pi_{0}\in\Pi(\mu,\nu) italic_π start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ∈ roman_Π ( italic_μ , italic_ν ) that achieves the following infimum.

We call a solution to the Kantorovich QOT a Kantorovich solution. We will often use quadratic optimal transportation problem or QOT to refer one of Monge QOT or Kantorovich QOT, and we will often say solution when there is no need for distinguishing the Monge solutions and the Kantorovich solutions.

The Kantorovich formulation of the classical optimal transportation problem allow us to view the problem in the perspective of linear porgramming. In the quadratic optimal transportation case, the relaxed problem 2 can be considered as a quadratic programming.

2.2 Comparison with other variations of OT

In this subsection, we claim that the solutions of the quadratic optimal transportation are different from the solutions to other versions of the optimal transportation problem with naive modifications.

2.2.1 Classical optimal transportation problems

We start with the classical optimal transportation problems. In this problem, we consider a cost function c : X × Y → ℝ : 𝑐 → 𝑋 𝑌 ℝ c:X\times Y\to\mathbb{R} italic_c : italic_X × italic_Y → blackboard_R and measures π 𝜋 \pi italic_π which have given marginals μ ∈ 𝒫 ⁢ ( X ) 𝜇 𝒫 𝑋 \mu\in\mathcal{P}(X) italic_μ ∈ caligraphic_P ( italic_X ) and ν ∈ 𝒫 ⁢ ( Y ) 𝜈 𝒫 𝑌 \nu\in\mathcal{P}(Y) italic_ν ∈ caligraphic_P ( italic_Y ) . We define total cost 𝒞 : 𝒫 ⁢ ( X × Y ) → ℝ ∪ { ± ∞ } : 𝒞 → 𝒫 𝑋 𝑌 ℝ plus-or-minus \mathcal{C}:\mathcal{P}(X\times Y)\to\mathbb{R}\cup\{\pm\infty\} caligraphic_C : caligraphic_P ( italic_X × italic_Y ) → blackboard_R ∪ { ± ∞ } by 𝒞 ⁢ ( π ) = ∫ c ⁢ 𝑑 π 𝒞 𝜋 𝑐 differential-d 𝜋 \mathcal{C}(\pi)=\int cd\pi caligraphic_C ( italic_π ) = ∫ italic_c italic_d italic_π . Then we seek a probability measure in Π ⁢ ( μ , ν ) Π 𝜇 𝜈 \Pi(\mu,\nu) roman_Π ( italic_μ , italic_ν ) which minimize the total cost.

Problem 3 .

In the quadratic optimal transportation problem, we consider probability measures with the same marginal conditions in Π ⁢ ( μ , ν ) Π 𝜇 𝜈 \Pi(\mu,\nu) roman_Π ( italic_μ , italic_ν ) , but we integrate the cost function against the measure twice. Hence, one may consider Problem 3 with π ⊗ π tensor-product 𝜋 𝜋 \pi\otimes\pi italic_π ⊗ italic_π as a measure in 𝒫 ⁢ ( X 2 × Y 2 ) 𝒫 superscript 𝑋 2 superscript 𝑌 2 \mathcal{P}(X^{2}\times Y^{2}) caligraphic_P ( italic_X start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT × italic_Y start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) which is in Π ⁢ ( μ ⊗ μ , ν ⊗ ν ) Π tensor-product 𝜇 𝜇 tensor-product 𝜈 𝜈 \Pi(\mu\otimes\mu,\nu\otimes\nu) roman_Π ( italic_μ ⊗ italic_μ , italic_ν ⊗ italic_ν ) .

We claim that the solution to this problem is different from the solutions to the QOT in general with an example. Let us describe the idea before we give an example. The idea is to see the structure of the solutions to the two problems. If QOT has a Monge solution T 𝑇 T italic_T , then π = ( I ⁢ d × T ) ♯ ⁢ μ 𝜋 subscript 𝐼 𝑑 𝑇 ♯ 𝜇 \pi=(Id\times T)_{\sharp}\mu italic_π = ( italic_I italic_d × italic_T ) start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_μ and π ⊗ π = ( I ⁢ d × T × I ⁢ d × T ) ♯ ⁢ μ tensor-product 𝜋 𝜋 subscript 𝐼 𝑑 𝑇 𝐼 𝑑 𝑇 ♯ 𝜇 \pi\otimes\pi=(Id\times T\times Id\times T)_{\sharp}\mu italic_π ⊗ italic_π = ( italic_I italic_d × italic_T × italic_I italic_d × italic_T ) start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_μ . In particular, if π ⊗ π tensor-product 𝜋 𝜋 \pi\otimes\pi italic_π ⊗ italic_π is a Kantorovich solution of Problem LABEL:prbm:_OT2 , then ( T , T ) 𝑇 𝑇 (T,T) ( italic_T , italic_T ) will be the Monge solution to the Problem LABEL:prbm:_OT2 . Then the horizontal and vertical slices of X × X 𝑋 𝑋 X\times X italic_X × italic_X will be mapped to the horizontal and vertical slices of Y × Y 𝑌 𝑌 Y\times Y italic_Y × italic_Y respectively. This is not true for the solutions to the classical optimal transportation problem in general.

Example 1 .

𝑦 ¯ 𝑦 c(x,y,\overline{x},\overline{y})=-(x+\overline{x})(y+\overline{y}) italic_c ( italic_x , italic_y , over¯ start_ARG italic_x end_ARG , over¯ start_ARG italic_y end_ARG ) = - ( italic_x + over¯ start_ARG italic_x end_ARG ) ( italic_y + over¯ start_ARG italic_y end_ARG ) . We let μ 𝜇 \mu italic_μ and ν 𝜈 \nu italic_ν be the probability measures on [ 0 , 1 ] 0 1 [0,1] [ 0 , 1 ] defined by

Lemma 2.1 .

Define D ¯ k subscript ¯ 𝐷 𝑘 \overline{D}_{k} over¯ start_ARG italic_D end_ARG start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT and D ¯ k subscript ¯ 𝐷 𝑘 \underline{D}_{k} under¯ start_ARG italic_D end_ARG start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT by

subscript 𝑦 0 subscript ¯ 𝑦 0 l=y_{0}+\overline{y}_{0} italic_l = italic_y start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + over¯ start_ARG italic_y end_ARG start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT . Then

Corollary 2.2 .

we first note that

as π ⊗ π ∈ Π ⁢ ( μ ⊗ μ , ν ⊗ ν ) tensor-product 𝜋 𝜋 Π tensor-product 𝜇 𝜇 tensor-product 𝜈 𝜈 \pi\otimes\pi\in\Pi(\mu\otimes\mu,\nu\otimes\nu) italic_π ⊗ italic_π ∈ roman_Π ( italic_μ ⊗ italic_μ , italic_ν ⊗ italic_ν ) for any π ∈ Π ⁢ ( μ , ν ) 𝜋 Π 𝜇 𝜈 \pi\in\Pi(\mu,\nu) italic_π ∈ roman_Π ( italic_μ , italic_ν ) . Therefore, we only need to show that the equality is not attained. Suppose we have the equality

Note that by existence of the solution of QOT (Proposition 3.2 ), ∃ π ∗ ∈ Π ⁢ ( μ , ν ) superscript 𝜋 Π 𝜇 𝜈 \exists\pi^{*}\in\Pi(\mu,\nu) ∃ italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ∈ roman_Π ( italic_μ , italic_ν ) which is attains the infimum. Then π ∗ ⊗ π ∗ tensor-product superscript 𝜋 superscript 𝜋 \pi^{*}\otimes\pi^{*} italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ⊗ italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is also a solution to Problem LABEL:prbm:_OT2 . Let ( x , y ) ∈ spt ⁢ ( π ∗ ) 𝑥 𝑦 spt superscript 𝜋 (x,y)\in\mathrm{spt}(\pi^{*}) ( italic_x , italic_y ) ∈ roman_spt ( italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ) , then ( x , y , x , y ) ∈ spt ⁢ ( π ∗ ⊗ π ∗ ) 𝑥 𝑦 𝑥 𝑦 spt tensor-product superscript 𝜋 superscript 𝜋 (x,y,x,y)\in\mathrm{spt}(\pi^{*}\otimes\pi^{*}) ( italic_x , italic_y , italic_x , italic_y ) ∈ roman_spt ( italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ⊗ italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ) and by Lemma 2.1 , we observe

Explicit computation with the definitions of μ 𝜇 \mu italic_μ and ν 𝜈 \nu italic_ν , one can observe that y 𝑦 y italic_y is given by a function of x 𝑥 x italic_x . In particular, if y = T ⁢ ( x ) 𝑦 𝑇 𝑥 y=T(x) italic_y = italic_T ( italic_x ) , one can compute

On the other hand, we also have ν = T ♯ ⁢ μ 𝜈 subscript 𝑇 ♯ 𝜇 \nu=T_{\sharp}\mu italic_ν = italic_T start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_μ as spt ⁢ ( π ∗ ) spt superscript 𝜋 \mathrm{spt}(\pi^{*}) roman_spt ( italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ) is on the graph of T 𝑇 T italic_T . Then we can also compute

which is a contradiction. Therefore the equality ( 3 ) cannot be attained. ∎

Remark 2.3 .

By solving the formula of the cost function in Example 1 , one can find that the quadratic optimal transportation problem in Example 1 is in fact equivalent to a classical optimal transportation problem with c ⁢ ( x , y ) = − x ⁢ y 𝑐 𝑥 𝑦 𝑥 𝑦 c(x,y)=-xy italic_c ( italic_x , italic_y ) = - italic_x italic_y .

This shows that for some special cases, the quadratic optimal transportation problem can still be regarded as a classical optimal transportation problem, but with appropriate adjustments.

2.2.2 Multi-marginal problems

In multi-marginal optimal transport problems, we consider probability measures μ i ∈ 𝒫 ⁢ ( X i ) subscript 𝜇 𝑖 𝒫 subscript 𝑋 𝑖 \mu_{i}\in\mathcal{P}(X_{i}) italic_μ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∈ caligraphic_P ( italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) and a cost function c : ∏ i = 1 n X i → ℝ : 𝑐 → superscript subscript product 𝑖 1 𝑛 subscript 𝑋 𝑖 ℝ c:\prod_{i=1}^{n}X_{i}\to\mathbb{R} italic_c : ∏ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT → blackboard_R , and we seek a probability measure γ 𝛾 \gamma italic_γ that minimizes the total cost ∫ c ⁢ 𝑑 γ 𝑐 differential-d 𝛾 \int cd\gamma ∫ italic_c italic_d italic_γ among all the probability measures γ 𝛾 \gamma italic_γ that satisfy the marginal conditions Proj X i ♯ ⁢ γ = μ i subscript subscript Proj subscript 𝑋 𝑖 ♯ 𝛾 subscript 𝜇 𝑖 {\mathrm{Proj}_{X_{i}}}_{\sharp}\gamma=\mu_{i} roman_Proj start_POSTSUBSCRIPT italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_γ = italic_μ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT .

Problem 4 .

Then one can consider the multi-marginal problem with n = 4 𝑛 4 n=4 italic_n = 4 , X 1 = X 3 = X subscript 𝑋 1 subscript 𝑋 3 𝑋 X_{1}=X_{3}=X italic_X start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_X start_POSTSUBSCRIPT 3 end_POSTSUBSCRIPT = italic_X , X 2 = X 4 = Y subscript 𝑋 2 subscript 𝑋 4 𝑌 X_{2}=X_{4}=Y italic_X start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = italic_X start_POSTSUBSCRIPT 4 end_POSTSUBSCRIPT = italic_Y , μ 1 = μ 3 = μ subscript 𝜇 1 subscript 𝜇 3 𝜇 \mu_{1}=\mu_{3}=\mu italic_μ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_μ start_POSTSUBSCRIPT 3 end_POSTSUBSCRIPT = italic_μ and μ 2 = μ 4 = ν subscript 𝜇 2 subscript 𝜇 4 𝜈 \mu_{2}=\mu_{4}=\nu italic_μ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = italic_μ start_POSTSUBSCRIPT 4 end_POSTSUBSCRIPT = italic_ν . We claim that this modification of multi-marginal problem does not give a solution to QOT in general. To see this, we consider the dimension of the supports of the solutions. In [ 23 ] , [ 16 ] , it is shown that under suitable condition, the solution of Problem 4 is given by a function, i.e. there exists F i : X 1 → X i : subscript 𝐹 𝑖 → subscript 𝑋 1 subscript 𝑋 𝑖 F_{i}:X_{1}\to X_{i} italic_F start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT : italic_X start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT → italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , 2 ≤ i ≤ n 2 𝑖 𝑛 2\leq i\leq n 2 ≤ italic_i ≤ italic_n such that

is a solution to Problem 4 . Then if we consider X i = X subscript 𝑋 𝑖 𝑋 X_{i}=X italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = italic_X for all i 𝑖 i italic_i where dim X = d dimension 𝑋 𝑑 \dim X=d roman_dim italic_X = italic_d , we can observe that the dimension of the support of the solution will be d 𝑑 d italic_d as it lies on the graph of a function whose domain has dimension d 𝑑 d italic_d . On the other hand, if a solution π 𝜋 \pi italic_π of QOT is given by a Monge solution T 𝑇 T italic_T , then the support of the measure π ⊗ π tensor-product 𝜋 𝜋 \pi\otimes\pi italic_π ⊗ italic_π lies in the graph of the function ( T , T ) 𝑇 𝑇 (T,T) ( italic_T , italic_T ) which has 2 ⁢ d 2 𝑑 2d 2 italic_d -dimensional domain.

Example 2 .

Let X i = [ 0 , 1 ] subscript 𝑋 𝑖 0 1 X_{i}=[0,1] italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = [ 0 , 1 ] for 1 ≤ i ≤ 4 1 𝑖 4 1\leq i\leq 4 1 ≤ italic_i ≤ 4 and we consider

Let μ i = d x ⌊ [ 0 , 1 ] \mu_{i}=dx\lfloor_{[0,1]} italic_μ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = italic_d italic_x ⌊ start_POSTSUBSCRIPT [ 0 , 1 ] end_POSTSUBSCRIPT for 1 ≤ i ≤ 4 1 𝑖 4 1\leq i\leq 4 1 ≤ italic_i ≤ 4 . Then it is obvious that the infimum value of Problem 4 is 0 0 (Consider γ = ( I d × I d × I d × I d ) ♯ d x ⌊ [ 0 , 1 ] \gamma=(Id\times Id\times Id\times Id)_{\sharp}dx\lfloor_{[0,1]} italic_γ = ( italic_I italic_d × italic_I italic_d × italic_I italic_d × italic_I italic_d ) start_POSTSUBSCRIPT ♯ end_POSTSUBSCRIPT italic_d italic_x ⌊ start_POSTSUBSCRIPT [ 0 , 1 ] end_POSTSUBSCRIPT ). On the other hand, QOT with X = Y = [ 0 , 1 ] 𝑋 𝑌 0 1 X=Y=[0,1] italic_X = italic_Y = [ 0 , 1 ] , μ = ν = d x ⌊ [ 0 , 1 ] \mu=\nu=dx\lfloor_{[0,1]} italic_μ = italic_ν = italic_d italic_x ⌊ start_POSTSUBSCRIPT [ 0 , 1 ] end_POSTSUBSCRIPT and c ⁢ ( x , y , x ¯ , y ¯ ) 𝑐 𝑥 𝑦 ¯ 𝑥 ¯ 𝑦 c(x,y,\overline{x},\overline{y}) italic_c ( italic_x , italic_y , over¯ start_ARG italic_x end_ARG , over¯ start_ARG italic_y end_ARG ) where c 𝑐 c italic_c is defined above does not have the infimum value 0.

Therefore, solutions of multi-marginal problem does not directly implies solutions of QOT as

2.2.3 Co-optimal transportation problems

Co-optimal transportation problem was introduced in [ 24 ] .

Problem 5 .

This problem have the most similar look with Problem 2 as we get Problem 2 by setting π = ρ 𝜋 𝜌 \pi=\rho italic_π = italic_ρ in Problem 5 . Still, if we consider the Problem 5 with μ 1 = μ 2 = μ subscript 𝜇 1 subscript 𝜇 2 𝜇 \mu_{1}=\mu_{2}=\mu italic_μ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_μ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = italic_μ and ν 1 = ν 2 = ν subscript 𝜈 1 subscript 𝜈 2 𝜈 \nu_{1}=\nu_{2}=\nu italic_ν start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = italic_ν start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = italic_ν , Solutions to Problem 5 does not directly give solutions of QOT. Here, the idea of the example is look at the difference of the supports of π ⊗ ρ tensor-product 𝜋 𝜌 \pi\otimes\rho italic_π ⊗ italic_ρ and π ⊗ π tensor-product 𝜋 𝜋 \pi\otimes\pi italic_π ⊗ italic_π . Support of π ⊗ π tensor-product 𝜋 𝜋 \pi\otimes\pi italic_π ⊗ italic_π always contains some part of the diagonal of ( X × Y ) 2 superscript 𝑋 𝑌 2 (X\times Y)^{2} ( italic_X × italic_Y ) start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT , while π ⊗ ρ tensor-product 𝜋 𝜌 \pi\otimes\rho italic_π ⊗ italic_ρ does not have to contain any part of the diagonal of ( X × Y ) 2 superscript 𝑋 𝑌 2 (X\times Y)^{2} ( italic_X × italic_Y ) start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT . Hence, we can build an example by letting the cost function to have very high value on the diagonal of ( X × Y ) 2 superscript 𝑋 𝑌 2 (X\times Y)^{2} ( italic_X × italic_Y ) start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT .

Example 3 .

We give a discrete example. We let X = Y = { 0 , 1 } 𝑋 𝑌 0 1 X=Y=\{0,1\} italic_X = italic_Y = { 0 , 1 } and define the cost function c 𝑐 c italic_c by

1 2 subscript 𝛿 0 1 2 subscript 𝛿 1 \mu=\nu=\frac{1}{2}\delta_{0}+\frac{1}{2}\delta_{1} italic_μ = italic_ν = divide start_ARG 1 end_ARG start_ARG 2 end_ARG italic_δ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + divide start_ARG 1 end_ARG start_ARG 2 end_ARG italic_δ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT . We first consider Problem 5 . Like stated above, we construct π 𝜋 \pi italic_π and ρ 𝜌 \rho italic_ρ so that spt ⁢ ( π ⊗ ρ ) spt tensor-product 𝜋 𝜌 \mathrm{spt}(\pi\otimes\rho) roman_spt ( italic_π ⊗ italic_ρ ) does not contain any part of the diagonal of ( X × Y ) 2 superscript 𝑋 𝑌 2 (X\times Y)^{2} ( italic_X × italic_Y ) start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT . We let

Therefore, infimum of Problem 5 is 0 in this example. On the other hand, for any γ ∈ Π ⁢ ( μ , ν ) 𝛾 Π 𝜇 𝜈 \gamma\in\Pi(\mu,\nu) italic_γ ∈ roman_Π ( italic_μ , italic_ν ) , we have

Then we can compute

Therefore, we obtain

2.2.4 Other transportation problems

There are other variations of the optimal transportation problems such as weak optimal transportation problem, martingale optimal transportation problem, optimal transportation with congestion. Among these variations, optimal transportation with congestion problem considers interaction that occurs along the transportation. This problem was considered by [ 6 ] , but most of the study consider the equations describing the congestion. In [ 4 ] , however, the author adds a quadratic transportation term to describe the interaction.

3 Elementary properties

3.1 existence, non-uniqueness, and non-locality.

Existence of a Kantorovich solution to the Kantorovich QOT can be proved similarly to the existence proof of classical optimal transportation problem. Before we prove the existence, we show a short lemma about a tensor product of weakly converging sequences of probability measures.

Lemma 3.1 .

Suppose { μ k } k = 1 ∞ superscript subscript subscript 𝜇 𝑘 𝑘 1 \{\mu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT and { ν k } k = 1 ∞ superscript subscript subscript 𝜈 𝑘 𝑘 1 \{\nu_{k}\}_{k=1}^{\infty} { italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT be sequences of probability measures on Polish spaces X 𝑋 X italic_X and Y 𝑌 Y italic_Y that converge weakly to μ 0 subscript 𝜇 0 \mu_{0} italic_μ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT and ν 0 subscript 𝜈 0 \nu_{0} italic_ν start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT respectively. Then the sequence of probability measures { μ k ⊗ ν k } k = 1 ∞ superscript subscript tensor-product subscript 𝜇 𝑘 subscript 𝜈 𝑘 𝑘 1 \{\mu_{k}\otimes\nu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT weakly converges to μ 0 ⊗ ν 0 tensor-product subscript 𝜇 0 subscript 𝜈 0 \mu_{0}\otimes\nu_{0} italic_μ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT .

By Prokhorov’s Theorem, { μ k } k = 1 ∞ superscript subscript subscript 𝜇 𝑘 𝑘 1 \{\mu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT and { ν k } k = 1 ∞ superscript subscript subscript 𝜈 𝑘 𝑘 1 \{\nu_{k}\}_{k=1}^{\infty} { italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT are tight. We claim that { μ k ⊗ ν k } k = 1 ∞ superscript subscript tensor-product subscript 𝜇 𝑘 subscript 𝜈 𝑘 𝑘 1 \{\mu_{k}\otimes\nu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT is also tight. Indeed, for any ϵ > 0 italic-ϵ 0 \epsilon>0 italic_ϵ > 0 , there exist compact sets K ⊂ X 𝐾 𝑋 K\subset X italic_K ⊂ italic_X and L ⊂ Y 𝐿 𝑌 L\subset Y italic_L ⊂ italic_Y such that

for any k 𝑘 k italic_k . Then

for any k 𝑘 k italic_k . Noting that K × L 𝐾 𝐿 K\times L italic_K × italic_L is also compact, { μ k ⊗ ν k } k = 1 ∞ superscript subscript tensor-product subscript 𝜇 𝑘 subscript 𝜈 𝑘 𝑘 1 \{\mu_{k}\otimes\nu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT is also tight. Then, invoking Prokhorov again, any subsequence of { μ k ⊗ ν k } k = 1 ∞ superscript subscript tensor-product subscript 𝜇 𝑘 subscript 𝜈 𝑘 𝑘 1 \{\mu_{k}\otimes\nu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT has a subsequence { μ k i ⊗ ν k i } i = 1 ∞ superscript subscript tensor-product subscript 𝜇 subscript 𝑘 𝑖 subscript 𝜈 subscript 𝑘 𝑖 𝑖 1 \{\mu_{k_{i}}\otimes\nu_{k_{i}}\}_{i=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT which converges weakly to a probability measure γ 𝛾 \gamma italic_γ . Then, we observe

Therefore we obtain that γ = μ 0 ⊗ ν 0 𝛾 tensor-product subscript 𝜇 0 subscript 𝜈 0 \gamma=\mu_{0}\otimes\nu_{0} italic_γ = italic_μ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT . We just proved that any subsequence of { μ k ⊗ ν k } k = 1 ∞ superscript subscript tensor-product subscript 𝜇 𝑘 subscript 𝜈 𝑘 𝑘 1 \{\mu_{k}\otimes\nu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT has a subsequence that converges to μ 0 ⊗ ν 0 tensor-product subscript 𝜇 0 subscript 𝜈 0 \mu_{0}\otimes\nu_{0} italic_μ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT weakly, and this implies that the whole sequence { μ k ⊗ ν k } k = 1 ∞ superscript subscript tensor-product subscript 𝜇 𝑘 subscript 𝜈 𝑘 𝑘 1 \{\mu_{k}\otimes\nu_{k}\}_{k=1}^{\infty} { italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT converges to μ 0 ⊗ ν 0 tensor-product subscript 𝜇 0 subscript 𝜈 0 \mu_{0}\otimes\nu_{0} italic_μ start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ⊗ italic_ν start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT weakly. ∎

Proposition 3.2 .

Problem 2 admits a solution.

Let { π k } k = 1 ∞ ⊂ Π ⁢ ( μ , ν ) superscript subscript subscript 𝜋 𝑘 𝑘 1 Π 𝜇 𝜈 \{\pi_{k}\}_{k=1}^{\infty}\subset\Pi(\mu,\nu) { italic_π start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT } start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT ⊂ roman_Π ( italic_μ , italic_ν ) be a minimizing sequence.

Tabu Search Techniques for the Quadratic Semi-Assignment Problem

• Conference paper
• Cite this conference paper

• Wolfgang Domschke 4 ,
• Peter Forst 4 &
• Stefan Voß 4  

195 Accesses

20 Citations

Assigning items to sets such that a quadratic function is minimized may be referred to as the quadratic semi-assignment problem. This problem indeed is a relaxed version of the well known quadratic assignment problem. Applications may be found in floor layout planning, in certain median problems with mutual communication, and in the problem of schedule synchronization in public transit networks. The same problem also arises in certain scheduling problems where the deviation from due dates is penalized by a quadratic function.

In this paper we compare different improvement procedures for the quadratic semi-assignment problem. The main contribution will be to explore detailed tabu search techniques with respect to this specific problem and, in addition, to compare them with simulated annealing.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

A Tabu Search Matheuristic for the Generalized Quadratic Assignment Problem

Tabu Search and Solution Space Analyses. The Job Shop Case

Simplified Tabu Search with Random-Based Searches for Bound Constrained Global Optimization

Chhajed, D. and T.J. Lowe (1990). M-median and m-center problems with mutual communication: solvable special cases. Working paper, University of Illinois Urbana-Champaign.

Google Scholar  

Dammeyer, F., P. Forst and S. Voß (1991). On the cancellation sequence method of tabu search. ORSA Journal on Commuting 3, 262–265.

Article   Google Scholar  

Domschke, W. (1989). Schedule synchronization for public transit networks. OR Spektrum 11, 17–24.

Dutta, A., G. Koehler and A. Whinston (1982). On optimal allocation in a distributed processing environment. Management Science 28, 839–853.

Glover, F. (1989). Tabu search — part I. ORSA Journal on Computing 1, 190–206.

Glover, F. (1990a). Tabu search — part II. ORSA Journal on Computing 2, 4–32.

Glover, F. (1990b). Tabu search: a tutorial. Interfaces 20, 74–94.

Moretti Tomasin, E., P. Pianca and A. Sorato (1988). Heuristic algorithms for the quadratic semi-assignment problem. Ricerca Operativa 18, 65–89.

Simeone, B. (1986). An asymptotically exact algorithm for equipartition problems. Discrete Applied Mathematics 14, 283–293.

Skorin-Kapov, J. (1990). Tabu search applied to the quadratic assignment problem. ORSA Journal on Computing 2, 33–45.

Voß, S. (1990). Network design formulations in schedule synchronization. Paper presented at the 5th Workshop on Computer-Aided Scheduling of Public Transport, Montreal.

Download references

Author information

Authors and affiliations.

FB 1 / FG Operations Research, Technische Hochschule Darmstadt, Hochschulstraße 1, D - 6100, Darmstadt, Germany

Wolfgang Domschke, Peter Forst & Stefan Voß

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Institute of Production Management, Fernuniversität Hagen, D-5800, Hagen 1, Germany

Günter Fandel

The Institute of Public Policy, George Mason University, Fairfax, VA, 22030-444, USA

Thomas Gulledge

NIST B 124 Metrology, AMFR, Gaithersburg, MD, 20899, USA

Albert Jones

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin · Heidelberg

About this paper

Cite this paper.

Domschke, W., Forst, P., Voß, S. (1992). Tabu Search Techniques for the Quadratic Semi-Assignment Problem. In: Fandel, G., Gulledge, T., Jones, A. (eds) New Directions for Operations Research in Manufacturing. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-77537-6_23

Download citation

DOI : https://doi.org/10.1007/978-3-642-77537-6_23

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-642-77539-0

Online ISBN : 978-3-642-77537-6

eBook Packages : Springer Book Archive

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research