Colourful Linear Programming: MIP formulations and an algorithm for a Difference-of-Convex formulation.

(1)

Università di Pisa

Corso di Laurea Magistrale in Matematica

TESI DI LAUREA

Colourful Linear Programming: MIP formulations

and an algorithm for a Dierence-of-Convex

formulation

Relatori

Candidato

Prof. Antonio Frangioni

Tiziano Amicone

MCF Fabio Furini

Controrelatore

Prof. Dario A. Bini

(2)

(3)

Introduction

The studied problem arises from a generalization of the classical Carathéodory's theorem which states that, given a set S ⊆ Rd_{with 0 ∈ conv(S), there exists a nite subset T ⊆ S with less than}

d + 1elements such that 0 ∈ conv(T ) (in this case T is said to be positively dependent). In 1982 Imre Bárány proved a colourful extension of Carathéodory's theorem: given d + 1 nonempty sets S1, . . . , Sd+1 ⊆ Rd such that 0 ∈ Td+1_c=1conv(Sc), there exists a positively dependent set

T ⊆Sd+1

c=1Sc which is colourful in the sense that it contains at most one point for each set Sc.

Starting from this, in 1997 Bárány and Onn formulated the Colourful Linear Programming problem (CLP) as follows: given a conguration of k nite nonempty sets S1, . . . , Sk⊆ Rd, decide

whether there exists a positively dependent colourful set T and, if there is one, nd it. During the years many authors studied the complexity of the problem and proved its NP-completeness in the general case. The most studied case is when Bárány's theorem hypotheses are veried, i.e. when the existence of a positively dependent colourful set is guaranteed and the problem reduces to nd a solution. For that case, two algorithms have been developed by Bárány-Onn (1997) and Meunier-Sarrabezolles (2016). The last two authors also suggested some possible applications with Nash equilibria in the context of Bimatrix Game and with the dierentiation of Dantzig's diet problem solutions.

The work is focused on the general CLP problem which is poorly covered in literature. Three dierent Mixed-Integer Linear Programming formulations are given and an original point of view, in terms of Dierence-of-Convex (DC) modeling of the problem, is described. The latter consists in a mathematical optimization program in which the objective function is a dierence of two convex (actually, quadratic) functions and constraints are linear. A code in C++ has been written in order to use the solver CPLEX for solving both feasible and infeasible instances, in all 4 proposed models.

DC programming theory provides an algorithm which is essentially a combination of a Branch-and-Bound scheme with an Outer-Approximation method, for DC problems with linear con-straints. Nevertheless, we can not apply it to the DC model of CLP since it is required to have a point in the interior of the feasible set, which is empty in the suggested model. Thus, the original B&B algorithm is modied in order to accommodate sets with nonempty relative interior, as in the CLP case. Furthermore, the algorithm is streamlined by exploiting the specic structure of the problem (simple, with quadratic objective function, and constraints with all-0 RHS except for a single convexity constraint) in order to more eciently perform the crucial steps.

Finally, a MATLAB code has been implemented for testing the correctness and the eciency of the proposed algorithm. Results are promising: while execution time per node is larger (which is justied by the fact that CPLEX is written in highly-optimised C++), the number of nodes is much lower, indicating that the bound quality is far better. This translates in a total running time that can be smaller by an order of magnitude with respect to the state-of-the-art general-purpose solver.

(6)

(7)

Chapter 1

The Colourful Linear Programming

problem

In this rst chapter we introduce the problem which is the object of the study of all the work: we describe here its origins in literature, studies so far carried out and results achieved.

1.1 Problem denition

We begin by considering the following linear programming problem:

INPUT: a nite set S ⊆ Rd _{and a point p ∈ R}d_.

TASK: decide whether there exists T ⊆ S such that |T | ≤ d + 1 and p ∈ conv(T ); and, if there is one, nd it.

We call it Monochromatic Linear Programming (MLP). The resolution of the problem con-sists of two steps: rst, we have to extablish if there exists a solution set T . If there is not, then the problem is infeasible; otherwise, we have to exhibit such a set. Regarding the rst step, the following theorem is helpful. It is a classical result of convex geometry whose rst version is due to Constantin Carathéodory in 1907; we here describe a generalization of it, proved in 1914 by Ernst Steinitz1_.

Theorem 1 (Carathéodory). Given a set S ⊆ Rd _{and a point p ∈ conv(S), there exists a subset}

T ⊆ S such that |T | ≤ d + 1 and p ∈ conv(T ). Proof. Given p ∈ conv(S), so that we can write

p =

m

X

j=1

λjxj

where, for any j = 1, . . . , m, xj ∈ S, λj > 0and P m

j=1λj = 1. If m ≤ d + 1 there is nothing to

prove, hence suppose m > d + 1. Then the m − 1 points x2− x1, . . . , xm− x1 are at least d + 1

1_{Carathéodory proved the fact with S ⊆ R}d_{compact set, while Steinitz extended it to any set S.}

(8)

points in Rd _{thus they are linearly dependent: so ∃µ}

2, . . . , µm ∈ R not all equal to zero, such

that _m X i=2 µi(xi− x1) = 0. We dene µ1:= −P m i=2µi, therefore P m i=1µi= 0and 0 = m X i=2 µi(xi− x1) = m X i=2 µixi− x1 m X i=2 µi= m X i=1 µixi .

Thus for any α ∈ R we have p = Pm

j=1(λj− αµj)xj. In particular, choosen α := minnλj µj : 1 ≤ j ≤ m, µj > 0 o = λi µi > 0 since, for any j = 1, . . . , m it holds

if µj > 0, α ≤ λj µj =⇒ λj− αµj≥ 0 if µj = 0, λj− αµj= λj> 0 if µj < 0, − αµj> 0

we obtain λj− αµj≥ 0for any j = 1, . . . , m and λi− αµi= 0for at least an index i (that one

which denes α). Moreover

m X j=1 (λj− αµj) = m X j=1 λj− α m X j=1 µj = 1.

In conclusion, we have written p as a convex combination of less than m − 1 points xj ∈ S. This

process can be repeated until one gets a convex combination of p of at most d + 1 points of S.

Therefore, MLP admits a solution (i.e. there exists a subset T which veries the above properties) if and only if p ∈ conv(S): in fact, the condition p ∈ conv(S) is necessary since T ⊆ Simplies conv(T ) ⊆ conv(S); Carathéodory's theorem states that this condition is sucient too.

Why Linear Programming?

The feasibility of MLP, that is the problem of extablishing whether the point p ∈ conv(S) or not, can be easily written as a Linear Programming feasibility problem, in the standard form: decide whether a polyhedron {x ∈ Rd _{: Ax = b, x ≥ 0}} _{is empty or not. In fact, suppose for}

example S = {v1, . . . , vn} ⊆ Rd and p ∈ Rd; dene:

A =       ... ... v1 · · · vn ... ... 1 · · · 1       ∈ R(d+1)×n, b =       ... p ... 1       ∈ R(d+1).

(9)

1.1. PROBLEM DEFINITION 3 Then we have p ∈ conv(S) if and only if {x ∈ Rd_{: Ax = b, x ≥ 0} 6= ∅}_{. Thus the MLP problem}

reduces to the following: given a nite set S ⊆ Rd _{and a point p ∈ conv(S), nd a subset T ⊆ S}

such that |T | ≤ d + 1 and p ∈ conv(T ). The proof of Theorem 1 suggests a possible way to compute a subset T ⊆ S of size at most d + 1 containing the point p.

1.1.1 Colourful Linear Programming

In 1982 Imre Bárány [2] formulated and proved a colourful extension of Carathéodory's theo-rem, from which it is possible to generalize problem MLP. First, without loss of generality, we henceforth suppose that point p coincides with the origin, i.e. p = 0 ∈ Rd_{: in fact in the general}

case we can apply a translation which maps the point p onto the origin.

The idea of the extension is to consider several nite sets S1, . . . , Sk, each of them Sc we

imagine composed of points of the same colour c. The goal becomes to establish whether there exists a set T ⊆ ScSc which contains at most one point of each colour and such that p = 0 is in

its convex hull conv(T ).

Before analyzing the theorem, we introduce the following two denitions:

Denition 1. A nite nonempty set A = {a1, . . . , an} ⊆ Rd is said to be positively dependent

if there exists µµµ = (µi) ∈ Rn such that µi ≥ 0, µµµ 6= 000 and P n

i=1µiai = 0. Equivalently, A is

positively dependent if and only if 0 ∈ conv(A).

Denition 2. Given a conguration of k disjoint sets S1, . . . , Sk ⊆ Rd, we say that a set

T ⊆Sk

c=1Sc is colourful if it contains at most one point of each colour, that is if

T ⊆

k

[

c=1

Sc and |T ∩ Sc| ≤ 1, ∀c = 1, . . . , k.

The colourful extension of Carathéodory's theorem is the following:

Theorem 2 (Colourful Carathéodory's Theorem). Given a conguration of k nonempty sets S1, . . . , Sk ⊆ Rd such that for any c = 1, . . . , k the set Sc is positively dependent, if k = d + 1

then there exists a positively dependent colourful set T .

Proof. By Carathéodory's theorem, without loss of generality, we can assume that Sc is nite,

for any c = 1, . . . , k. Among all colourful sets, let T = {a1, . . . , ad+1} (with ac ∈ Sc) be one of

them, whose convex hull C := conv(T ) is the nearest to the origin 0. If 0 ∈ C the proof is clear, so suppose 0 /∈ C and let p be the point of C nearest to 0 (i.e. which minimizes the norm):

dist(C, 0) = min{kxk : x ∈ C} = kpk > 0.

We can see p as the projection of the origin onto the convex set C, so it is on the boundary of C (p ∈ ∂C) and it can be written as a convex combination of at most d points of T . This can be seen by Carathéodory's theorem in Rd−1_{. Let us say, for example, that the rst element a}

1is not

used in the representation of p. Then a1can be replaced in the colourful set by any other element

of S1, without increasing dist(C, 0). Moreover, the hyperplane H through p an orthogonal to the

direction of p, separates 0 from C. As said before, since S1 is positively dependent, there exists

a point b ∈ S1 on the semispace dened by H and containing 0. Set now T0= {b, a2. . . , ad+1}:

(10)

Note that for k > d + 1 the statement remains trivially true, it is sucient to consider just d + 1sets; for k < d + 1, instead, the theorem is false: a simple counterexample is given by the conguration Sj = {ej, −ej} for any j = 1, . . . , k, where ej is the j-th vector of the standard

basis of Rd_.

In his paper, Bárány also provides a conic version of the theorem, obtained by replacing the convex hull with the conic hull. Many similar theoretical results, called colourful versions of classical theorems, such as Helly's and Tverberg's ones, can be found in [1] and [4].

The colourful version of Carathéodory's theorem naturally induces the formulation of a new problem which is an extension of MLP. We call it Colourful Carathéodory problem (CC briey) as done by Meunier and Sarrabezolles in [14]:

INPUT: a conguration of k positively dependent sets S1, . . . , Sk ⊆ Rd.

TASK: nd, if there exists, a positively dependent colourful set.

The case k = d + 1, in which the Colourful Carathéodory's theorem ensures the existence of a solution, is the most studied one in literature: many authors investigated various features of the problem, such as bounds on the number of solutions [5], [6].

It is possible to generalize even more the CC problem and dene the Colourful Linear Pro-gramming problem (indicated below with CLP), which is the object of study of this work. First dened by Bárány and Onn in [3], it can be formulated as follows:

INPUT: a conguration of k nite nonempty sets S1, . . . , Sk ⊆ Rd.

TASK: decide whether there exists a positively dependent colourful set T with respect to the conguration S1, . . . , Sk and, if there is one, nd it.

We remark that the sets Sc of the conguration given in input are not positively dependent,

nor disjoint. Thus, it is necessary to specify what does it means that a set T is colourful. The meaning in itself does not change: the set T contains at most one point of each set Sc, but we

can not write simply |T ∩ Sc| ≤ 1 because the set T may contain a point in the intersection of

two or more sets Sc. So, to be more precise, we say that a set

T ⊆

k

[

c=1

Sc

is colourful in the conguration S1, . . . , Skif there exists a map ϕ: T → {1, . . . , k} injective, such

that

ϕ(a) = c =⇒ a ∈ Sc.

Note that CLP is a generalization of MLP: the latter can be obtained from CLP by putting k = d + 1and S1= · · · = Sd+1. So the dierences which generalize the problem are two:

• there are k colours or coloured sets, instead of one;

• the upper bound on the cardinality of T is given by the number of colours k and not by the dimension d of the space: in fact, k and d have no relationship in the generic formulation of CLP.

We remark that, as for MLP, also solving CLP consists of two steps: one has rst to answer if there exists or not a positively dependent colourful set (this is the feasibility problem); and, if yes, one has to exhibit a solution set T .

(11)

1.2. THE COMPLEXITY 5

1.1.2 Further colourful problems

Meunier and Sarrabezolles also provide a number of colourful linear problems which nd some applications in several areas. Below we report some of them:

• the Finding Another Colourful Simplex problem:

INPUT: a conguration S1, . . . , Sd+1⊆ Rd of d + 1 pairs of points and a positively

dependent colourful set in this conguration.

TASK: nd another positively dependent colourful set. • a conic version of CC:

INPUT: a conguration of d sets S1, . . . , Sd ⊆ Rd and a point p ∈ T d

i=1cone(Si).

TASK: nd a colourful set T such that p ∈ cone(T ). • a conic version of CLP:

INPUT: a conguration of k sets S1, . . . , Sk⊆ Rd and a point p ∈ Rd.

TASK: decide whether there exists a colourful set T such that p ∈ cone(T ).

Note that CC problem in conic version coincides with the classical CC when 0 /∈ conv(ScSc):

it can be seen geometrically that there is a shift in the dimension when going from one version to the other.

1.1.3 Special cases studied in literature

In literature the general case of CLP is poorly covered and special assumptions, which are often restrictive, lead to the study of particular cases. For example, many authors assume that all points are in general position with respect to 0, which means:

(i) Si∩ Sj = ∅for all i 6= j;

(ii) for any c = 1, . . . , k, there are no h + 1 points in Sc in the same h-dimensional linear

subspace of Rd_{, for any h = 0, . . . , d − 1.}

In this case, it is possible to normalize all points in order to have them on the unit sphere Sd ⊆ Rd. This special case has been studied, for example, in [5], [6] and [14].

Some authors dene the core of the conguration as the intersection set Tk

c=1conv(Sc). So

the core condition (or Bárány condition) is veried if 0 is in the core. If k ≥ d + 1 we have seen in Theorem 2 that this is a polinomially checkable sucient condition for the feasibility of CLP; other similar conditions are investigated in [1], [8] and [13].

Another frequently used assumption is the xed size of sets Sc. It is often supposed that

|Sc| = d + 1for all colours c (see [6]): this makes sense in the context of the CC problem, if we

do a preprocessing step. In fact, suppose that each colour set Sc has a greater number of points

(more than d + 1). We can reduce to a positively dependent set of at most d + 1 elements thanks to the monochromatic version of Carathéodory's theorem (i.e. by solving an MLP problem).

1.2 The complexity

In this section we describe main known results about the complexity of colourful linear program-ming problems. The rst outcome is due to Bárány and Onn [3]: they proved that problem CC is NP-complete in the case k = d, with no restrictions on the size of sets Sc.

(12)

Theorem 3. If k = d, the Colourful Carathéodory problem is NP-complete. Proof. The proof is done by a reduction to the 3-SAT problem.

Let f = c1∧ · · · ∧ cm be a boolean function in the 3-conjunctive normal form on variables

x1, . . . , xn where each clause ci is of the form ci = li1+ li2 + li3 and each literal ls ∈ {xs, ¯xs}.

Set d = k := m + n and let ec1, . . . , ecm, ex1, . . . , exn denote the canonical basis of R

d_{: the rst}

munit vectors correspond to the m clauses and the last n to the variables. Also a generic vector v ∈ Rd _{will have components indexed on them: v = (v}

c1, . . . , vcm, vx1, . . . , vxn).

The proof consists in constructing d positively dependent sets of points T1, . . . , Tm, S1, . . . , Sn

in Rd _{such that there is a colourful positively dependent set T if and only if f is satisable.}

For each i = 1, . . . , m we construct a set of 5 points Ti= {wi,1, wi,5, wi,9, yi, zi} and for each

j = 1, . . . , na set of 3 points Sj = {vj, ¯vj, uj}. For that purpose, consider the following m × n

incidence matrices clauses-variables A and ¯Adened by:

Ai,j = ( 1, if xj ∈ ci 0, otherwise, ¯ Ai,j= ( 1, if ¯xj ∈ ci 0, otherwise. So we dene v1= m X i=1

(3Ai,1− ¯Ai,1)eci+ n X j=1 exj, v¯ 1₌ m X i=1

(−Ai,1+ ¯Ai,1)eci+ n X j=1 exj, and for j = 2, . . . , n vj = m X i=1

(3Ai,j− ¯Ai,j)eci− exj, ¯v j ₌

m

X

i=1

(−Ai,j+ 3 ¯Ai,j)eci− exj.

Points uj _{= −(v}j_{+ ¯}_vj₎_{are chosen so that sets S}

j are positively dependent.

For i = 1, . . . , m and r = 1, 5, 9 let

wi,r = −reci−

1

mexi, y i_{= 15e}

ci+ 50exi,

zi= −(wi,1+ wi,5+ wi,9+ yi).

Now rst show that any x ∈ {0, 1}d _{satisfying assignment for f gives a positively dependent}

colourful set. For j = 1, . . . , n let

sj = ( vj_, _{if x} j= 1 ¯ vj_, _{if x} j= 0

Since the assignment is satisfying, we have

ri:= n

X

j=1

sj_c_i ∈ {1, 5, 9},

so set ti_{= w}i,ri for i = 1, . . . , m. With this choice it's easy to check that m X i=1 ti+ n X j=1 sj = 0

(13)

1.2. THE COMPLEXITY 7 that is, the set T = {t1_{, . . . , t}m_{, s}1_{, . . . , s}n_}_{is a positively dependent colourful set.}

Vice versa, suppose T = {t1_{, . . . , t}m_{, s}1_{, . . . , s}n_} _{is a positively dependent colourful set: let}

µi, λj nonnegative numbers, not all equal to zero, such that

a := m X i=1 µiti+ n X j=1 λjsj = 0.

By considering equations aci = 0 for i = 1, . . . , m and axj = 0 for j = 1, . . . , n given by the

various coordinates of a, we will exhibit a satisfying assignment x for f. First, some λjmust be zero. If not, then (for any i) 0 = aci = µit

i_{, so whenever µ}

i6= 0there

must be hold ti _{= 0}_{and so t}i_{= z}i_{. But then 0 = a} x1 =

Pm

i=1µizmx1 which would imply µi= 0

for all i, that is an absurdum. Moreover, note that λ1= λ2= · · · = λn6= 0 and sj = uj eighter

for all j or for no j: this follows by the previous claim by considering the equations axj = 0for

j = 2, . . . , n.

The next step of the proof consists in showing that sj _{∈ {v}j_{, ¯}_vj_}_{for all j = 1, . . . , n. Suppose}

this is not true: then, by the above statement, it holds sj_{= u}j _{for all j and λ := λ}

1= · · · = λn.

Thus, for all i = 1, . . . , m:

0 = aci = X lj∈ci λuj_c i+ µit i ci= 3λ(−2) + µit i ci, so it must be ti ci> 0, but then t i_{= y}i _{and µ} i= _y6λi ci = 6λ 15 = 2λ 5. Therefore, 0 = ax1 = λu 1 x1+ m X i=1 µiyix1= −2λ + m 2 5λ50 = (20m − 2)λ > 0

which is impossible. Thereafter sj _{∈ {v}j_{, ¯}_vj_} _{indeed. Let us dene now the following variable}

assignment:

xj =

(

1 if sj_{= v}j

1 if sj= ¯vj

and show that this is satisfying for f, namely that each clause ci has at least one literal lj= 1.

First observe that for all i it holds

0 = aci = X λj∈ci λsj_c i+ µit i ci. and Pλj∈ciλs j

ci 6= 0since it is a value in {−3λ, λ, 5λ, 9λ}. Thus it must be t i

ci 6= 0and so t i_{6= z}i_.

The proof ends once showed ti_{6= y}i_{, which will imply t}i

ci < 0so Pλj∈ciλs j

ci∈ {λ, 5λ, 9λ}which

implies that clause ci is satised. Let I1, I2 be the following partition of the set {1, . . . , m}:

I1= {i : ti6= yi}, I2= {i : ti= yi}

so we would show that I2= ∅. For any i, we have Pλj∈ciλs j ci ≤ 9λ. If i ∈ I1 that is t i_{= w}i,r_, then we have ti ci = −r so 0 = aci= X λj∈ci λsj_c i+ µit i ci =⇒ µir ≤ 9λ =⇒ µi≤ 9λ r ≤ 9λ.

(14)

Therefore, 0 = ax1= λs 1 x1+ m X i=1 µitix1= λ + X i∈I1 µi − 1 m +X i∈I2 50µi≥ λ − |I1| 9λ m + 50 X i∈I2 µi and so X i∈I2 µi≤ λ 50 9|I₁| m − 1 ≤8λ 50 < 1 5λ. Thus it holds µi ≤Pi∈I2µi ≤ λ/5for all i ∈ I2; now, since µit

i ci = µiy

i

ci = 15µi, we have

0 ≤ µitici< 3λ. But then, for i ∈ I2 we obtain

0 = aci = X λj∈ci λsj_c i+ µit i ci =⇒ X lj∈ci λsj_c i ≤ 0 =⇒ X lj∈ci λsj_c i = −3λ so we must have 0 = aci= −3λ + µit i ci < −3λ + 3λ = 0,

which is an absurdum. Therefore I2= ∅and the claim is proved.

More recently [14], Meunier and Sarrabezolles proved the NP-completeness of CLP when k − d = q ∈ Z is xed (while the dimension d ≥ 2 is not xed). They also gave a nice proof of the fact in the special case q = 1 (i.e. k = d + 1), we describe below.

Theorem 4. If k = d + 1, the Colourful Linear Programming is NP-complete.

Proof. The proof consists of a reduction to the SUBSET SUM problem, which can be formu-lated as follows: given n + 1 integers a1, . . . , an, bdecide whether there exists a subset of indices

I ⊆ {1, . . . , n}such that P_i∈Iai= b. This problem is NP-complete.

Let a1, . . . , an, bbe an input of SUBSET SUM and dene

• d = n + 2;

• for i = 1, . . . , d let ei be the i-th vector of the canonical basis of Rd;

• for i = 1, . . . , d − 2 let fi∈ Rd the vector fi= (0, . . . , 0, 1

i-th, 0, . . . , 0, −1, 1);

• g = (−a1, . . . , −an, b, −b) ∈ Rd.

Now dene the input of CLP as follows:

Si = {ei, fi}, ∀i = 1, . . . , d − 2,

Sd−1= {ed−1}, Sd= {ed},

Sd+1 = {g}

This is a clearly polynomial reduction, so let us check the equivalence of the two problems. First, suppose that the answer of CLP is yes. So there exists a positively dependent set T ⊆ Sd+1

c=1Sc such that |T ∩ Sc| ≤ 1 for all c = 1, . . . , d + 1. Hence there exists a vector of

coecients λ ∈ Rd_{\ {0}}_{, λ ≥ 0 such that} d+1

X

c=1

(15)

1.3. KNOWN ALGORITHMS FOR CC PROBLEMS UNDER FEASIBILITY CONDITION 9 where pc∈ T ∩ Sc for every c = 1, . . . , d + 1. Dene now

I =i ∈ {1, . . . , d − 2} : T ∩ Si= {fi} .

We can read the last two equations of system (1.1): −X i∈I λi+ λd−1+ λd+1b = 0 X i∈I λi+ λd− λd+1b = 0

Since λi≥ 0, by summing these two relations we obtain λd−1= λd = 0and so

X

i∈I

λi= λd+1b. (1.2)

Now, reading the rst d−2 equations of (1.1) leads to λi− λd+1ai= 0for i = 1, . . . , d−2. These

equalities and (1.2) imply that

X

i∈I

λd+1ai= λd+1b.

The coecient λd+ 1 6= 0otherwise we have λ ≡ 0. Therefore Pi∈Iλd+1ai= λd+1b.

On the other hand, suppose that SUBSET SUM has answer yes. So we have a subset of indices I ⊆ {1, . . . , n} such that Pi∈Iai= b. For each i = 1 . . . , n dene

pi=

(

fi if i ∈ I

ei otherwise

Then we have Pn

i=1aipi+ g = 0 and so the set T = S n

i=1pi ∪ {g}is a positively dependent

colourful set, i.e. a solution of CLP.

Remark: Known algorithms for solving CLP in feasibility conditions - like CC under Bárány condition - are not polynomial and the complexity of the problem is an object of study.

The complexity status of Colourful Carathéodory problem is an open question since 1982 [3, Question 1.2].

1.3 Known algorithms for CC problems under feasibility

condition

We now summarize some known algorithms for solving the Colourful Carathéodory problem under feasibility condition, which implies the existence of (at least) a solution. Hence, we suppose that is given a conguration S1, . . . , Sk⊆ Rd of nite sets such that:

• the number of colours is k = d + 1, where d is the dimension of the space; • (core or Bárány feasibility condition, strengthened) 0 ∈ intTk

c=1conv(Sc);

• |Sc| = d + 1, ∀c = 1, . . . , d + 1;

• all points are in general position.

(16)

1.3.1 The Bárány-Onn algorithm

In 1997 Bárány and Onn [3] rst explicited and analyzed an algorithm for solving the Colourful Carathéodory problem; the idea is the following:

Initialization: choose a colourful set T1 such that |T1| = d + 1and put i := 0.

Repeat: - put i := i + 1;

- if 0 ∈ conv(Ti)then STOP and output Ti;

- otherwise, nd F ⊆ Ti such that |F | = d and aff(F ), the ane span of F , separates 0 and

Ti\ F = {p0};

- in the semispace delimited by the hyperplane aff(F ) which contains 0, choose a point ¯p of the same colour of p0;

- update Ti+1:= F ∪ {¯p}.

The existence of such a set F in each iteration is proved, it follows from the fact that and that dim(aff(F )) = d − 1 and all points are in general position. Furthermore, the point ¯p exists because all sets Sc are positively dependent.

The main challenging and computationally hard steps are the way to nd the set F and the choice of a point ¯p. Authors suggest to do this through a calculation of a distance or a projection. Computational experiments done on the algorithm

An extensive computational study on the eciency of these algorithm is done by Deza et al.[7] and in Sui Huang master thesis [11]. They implemented Bárány-Onn algorithm in several versions, as well as a specic heuristic and a random algorithm, and compared methods on various types of instances. They also propose a modication of the Bárány-Onn algorithm in order to have a multi-updating at each iteration, which usually improves the computational eciency.

In Table 1.1 we report numerical results of their works taken from Huang's thesis: they are referred to the algorithm BO2, applied to 5 types of instances taken in several dimensions. The code is implemented in MATLAB and tests are performed on a machine with eight 64-bit CPUs, clocked at 2.6 GHz, with 64 GB RAM.

1.3.2 The Meunier-Sarrabezolles algorithm

In their paper [14] Meunier and Sarrabezolles propose a modication they call simplexication of the previous algorithm. They consider a dummy point v ∈ Rd _{and the following linear}

programming problem: min z Aλλλ + z¯v =      0 ... 0 1      , λλλ ≥ 000, z ≥ 0

(17)

1.3. KNOWN ALGORITHMS FOR CC PROBLEMS UNDER FEASIBILITY CONDITION11 Table 1.1: Numerical results obtained by Deza et al.[7]. In the rst column there is the dimension dof the instance. In other ones, 5 types of instances created by specic generators, and execution times expressed in seconds.

Random Unbalanced Highdensity Lowdensity Middensity Dimension time time time time time 3 0.7501 1.083 0.5735 0.9090 0.7613 6 1.832 3.716 0.8450 2.404 1.936 12 5.789 13.72 1.457 7.225 5.984 24 21.88 56.23 3.685 24.91 21.38 48 96.67 251.7 15.89 105.8 92.40 96 513.1 1278 82.79 542.5 488.1 192 3465 9253 559.7 3711 3274 384 34230 - 4355 37010 30150

where A is the (d+1)×(d+1)2_{matrix whose colums are the coordinates of points in S}

1, . . . , Sd+1

with an additional 1 in the last row, and vector ¯v = (v, 1)T_.

Solving this optimization problem corresponds to seek for an expression of 000 as a convex com-bination of elements in {v}∪Sd+1

c=1Sc, with a minimal weight on v. Clearly, if 000 ∈ conv(S d+1 c=1Sc),

the optimal value is 0. Using a terminology of the linear programming, they look for a colourful optimal basis. The algorithm can be described as follows:

Initialization:

- choose a colourful linearly independent set F1 such that |F1| = d;

- choose a dummy point v so that 0 is an interior point of conv(F1∪ {v});

- put i := 0.

The existence of the rst transversal set F1, whose elements are linearly independent, is proved:

the cost of this operation is linear. A possible choice for the dummy point is v = − Pd

i=1uiwhere

ui are the points of F1. Note that F1∪ {v} is a feasible colourful basis. Now, their algorithm

uses pivoting techniques in order to search an optimal colourful basis: Repeat:

- put i := i + 1;

- choose a point p of the missing colour of Fiwith negative reduced costs, computed with respect

to the current basis Fi∪ {v};

- apply a pivoting operation with p entering in the current basis; - if v leaves the basis then STOP and output T := Fi∪ {p};

- otherwise, dene Fi+1 as the new basis deprived of v.

To prove the correctness of the algorithm and so the convergence to a solution, authors showed the following property: points in the half-space delimited by aff(Fi)and containing 0, are

exactly the points with a negative reduced cost (see [14, Lemma2]). This property, jointly with the assumption that all sets Sc are positively dependent, ensures that such a point p exists and

(18)

Numerical example

In order to better understand how the Meunier-Sarrabezolles algorithm works, we describe a simple 2-dimensional example. In R2_{consider the following conguration of positively dependent}

sets: S1= {a11, a 1 2, a 1 3} = {(1, 1), (1, −1), (−3, 1)} S2= {a21, a 2 2, a 2 3} = {(2, 3), (2, −1), (−2, −1)} S3= {a31, a 3 2, a 3 3} = {(3, 0), (−1, −2), (−1, 2)}

We can choose, for example, F1= {a11, a 2

2}as a rst linearly independent colourful set, of size

d = 2, and the dummy point v = (−2, 0) so that the origin is an interior point of conv(F1∪ {v}).

Thus we investigate a classical linear program min{cx : Ax = b, x ≥ 0} that is given by:

min z (1.3) s.t.   1 1 −3 2 2 −2 3 −1 −1 −2 1 −1 1 3 −1 −1 0 −2 2 0 1 1 1 1 1 1 1 1 1 1                   λ1 λ2 λ3 λ4 λ5 λ6 λ7 λ8 λ9 z                 =   0 0 1   z ≥ 0, λi≥ 0 ∀i = 1, . . . , 9

and seek for a colourful optimal basis.

The algorithm starts with the rst feasible basis {a1

1, a22, v} corresponding to indices B =

{1, 5, 10} and to the vertex x1 = (2₇, 0, 0, 0,2₇, 0, 0, 0, 0,3₇) of the polyhedron representing the

feasible set of problem (1.3). The basis matrix and its inverse are:

AB=   1 2 −2 1 −1 0 1 1 1  , A−1_B = 1 7   1 4 2 1 −3 2 −2 −1 3  .

(19)

1.3. KNOWN ALGORITHMS FOR CC PROBLEMS UNDER FEASIBILITY CONDITION13 We can now compute reduced costs ˜cj: thanks to the above mentioned property we know

that ˜cj > 0if and only if the point corresponding to the j-th index is in the half-space containing

0 delimited by the line through a1

1 and a22: for example, ˜c7 = 3₇ > 0 since j = 7 corresponds to

the point a3

1which is in the other half-space. We have:

˜ c8= c8− cTBA−1B A8 = 0 − 1 7 0 0 1   1 4 2 1 −3 2 −2 −1 3     −1 −2 1  = −1 < 0. Hence we choose p = a3

2and apply a pivoting operation with p entering in the current basis. We

compute the decreasing direction d:   d1 d5 d10  = −A −1 B A8=   1 −1 −1  , d2= d3= d4= d6= d7= d9= 0, d8= 1.

The new vertex will be

y = x1+ θd = 2 7+ θ, 0, 0, 0, 2 7 − θ, 0, 0, θ, 0, 3 7 − θ with θ = θ∗= min i∈B, di<0 −xi di = min− 2 7 −1, − 3 7 −1 = −x5 d5 = 2 7 Thus x2= 4₇, 0, 0, 0, 0, 0, 0,2₇, 0,1₇

, the new basis {a1

1, a32, v}still includes the dummy point

v: new basis indices are ¯B = {1, 8, 10}and F2= {a11, a32}.

Similarly, at the second iteration we have:

AB=   1 −1 −2 1 −2 0 1 1 1   A−1_B = 1 7   2 1 4 1 −3 2 −3 2 1   and ˜ c6= 0 − 1 7 0 0 1   2 1 4 1 −3 2 −3 2 1     −2 −1 1  = − 5 7. The decreasing direction d:

  d1 d8 d10  = −A −1 B A8=   1 7 −3 7 −5 7  , d2= d3= d4= d5= d7= d9= 0, d6= 1.

The new vertex:

y = x2+ θd = 1 7 4 + θ, 0, 0, 0, 0, 7θ, 0, 2 − 3θ, 0, 1 − 5θ where θ = θ∗ = min i∈B, di<0 −xi di = −x10 d10 =7 5. So the point v leaves the basis which becomes {a1

1, a23, a32}: we have found a colourful positively

(20)

Table 1.2: Numerical results obtained by Meunier and Sarrabezolles in [14]. Execution time is expressed in seconds.

Random Unbalanced Highdensity Lowdensity Middensity Dimension time time time time time 3 0.0135 0.0123 0.0342 0.0138 0.0170 6 0.0180 0.0195 0.0474 0.0213 0.0164 12 0.0406 0.0396 0.0609 0.0591 0.0371 24 0.1433 0.1574 0.0871 0.2958 0.1123 48 0.9612 1.1684 1.1006 2.7946 0.7725 96 8.5069 11.244 3.1116 28.581 6.1306 192 81.017 250.1 21.675 263.14 50.299 384 1111.5 - 441.13 5987.9 846.91 Computational experiments

Authors also implemented their algorithm in C++ code and performed tests on the same in-stances of Huang's master thesis. Experiments are executed on a machine with two 64-bit CPUs, clocked at 2.1 GHz, with 4 GB RAM.

As done for Bárány-Onn algorithm, we report in Table 1.2 computational results obtained by Meunier and Sarrabezolles (which can be found and better analyzed in their paper [14]).

1.4 Possible applications

In this chapter we show a couple of possible applications of colourful linear programming proposed by F.Meunier and P.Sarrabezolles. They showed in their paper that the problem of computing a Nash equilibrium in a bimatrix game is polynomially reducible to a particular problem, rst introduced by Meunier and Deza, which is a special case of CLP. Furthermore, they suggest a possible applications related to the Dantzig's diet problem.

1.4.1 Colourful linear programming and Nash equilibria

We now describe a link between the colourful linear programming and Nash equilibria in Bimatrix Game, found by Meunier and Sarrabezolles while investigating and studying the complexity of CLP problems.

Consider the so called Finding Another Colourful Simplex problem (referred to as FACS), rst proposed in 2013 by Meunier and Deza [13], which is a colour linear programming problem:

INPUT: a conguration of d + 1 pairs of points S1, . . . , Sd+1⊆ Rd and a positively

dependent colourful set in this conguration.

TASK: nd another positively dependent colourful set.

This problem turns out as a byproduct of an existence theorem, known in literature as Octahedron lemma (see [5] and [6]), which can be formulted in this form: in CLP, if each set Sc

of the conguration is of size 2 and if points are in general position, then the number of positively dependent colourful sets (called simplicial depth) is even.

(21)

1.4. POSSIBLE APPLICATIONS 15 Now we formulate the BIMATRIX GAME problem: there are two players and two matrices A, B ∈ Rm×n_{are given. We denote them by A = (a}

i,j)and B = (bi,j). The rst player chooses a

probability distribution on the set M = {1, . . . , m} and the second one on the set N = {1, . . . , n}. Whereupon a pair (¯i, ¯j) ∈ M × N is drawn randomly, according to the selected distributions: the rst player gets a payo equal to a¯i,¯j and the second player equal to b¯i,¯j. They both try to

maximize their payo or, more precisely, the expected value of their payo.

In this context, a Nash equilibrium is a choice of probability distributions such that if one player changes his own distribution, then he will not increase the expected value of his payo. Formally, dened ∆k

= {x ∈ Rk +|

Pk

i=1xi= 1}, a Nash equilibrium is a pair (x∗, y∗) ∈ ∆m× ∆n

such that both the following properties hold: • xAy∗_{≤ x}∗_Ay∗_{, for all x ∈ ∆}m_;

• x∗_{By ≤ x}∗_By∗_{, for all y ∈ ∆}n_.

It was proved that if A, B ∈ Qm×n_{, then there exists a Nash equilibrium with small coecients.}

Thus, the Bimatrix Game problem we consider is: given A, B ∈ Qm×n_{, nd a Nash equilibrium.}

A possible way to try to solve Bimatrix Game, i.e. to compute Nash equilibria, consists in studying the complementary solutions of two systems:

[A, Im] x =    1 ... 1   , x ∈ R n+m + , (1.4a) [In, BT] x =    1 ... 1   , x ∈ R n+m + . (1.4b)

A complementary solution of the couple of systems (1.4a) and (1.4b) is a solution xA of (1.4a)

and a solution xB of (1.4b) such that xA· xB= 0. It is possible to prove that a complementary

solution satisfying supp(xA) ∩ {n + 1, . . . , n + m} = ∅or supp(xB) ∩ {1, . . . , n} = ∅gives a Nash

equilibrium2_.

Next steps, with the aim of proving that Bimatrix game is polinomially reducible to CLP, are: dene FACC, a conic version of FACS (which is equivalent to it unless a shift on the dimension) and then prove that Bimatrix game reduces to FACC. The Finding Another Colourful Cone problem is dened as follows:

INPUT: a conguration of d + 1 pairs of points S1, . . . , Sd+1 ⊆ Qd+1 such that

0 /∈ conv(S

cSc), a point p ∈ Qd+1 and a colourful set T such that p ∈ cone(T ).

TASK: nd another colourful set T0 _{such that p ∈ cone(T}0₎_.

With the following fact, we complete the prove of the link between colour linear programming and Nash equilibria in Bimatrix Game problem:

Proposition 1. The Bimatrix Game problem is polinomially reducible to FACC problem.

(22)

Proof. Consider A, B matrices m × n representing an instance of the Bimatrix Game problem. First, we can assume that these matrices have all positive entries: in fact, summing a constant to all coecients of both matrices does not change the problem.

Then dene the (m + n) × (2(m + n)) matrix

M =A Im 0 0 0 0 In BT

,

and denote by Mi the ith column of M. Note that vector u = (1, . . . , 1) ∈ Rn+m satises

u ∈ cone(T )where T = {Mn+1, . . . , Mn+m, Mn+m+1, . . . , M2n+m} = {e1, . . . , en+m}.

For i = 1, . . . , m + n dene Si= {Mi, Mn+m+i}. Since all entries of A and B are positive, we

know that 0 is not in the convex hull of the columns of M and u. A polynomial time algorithm solving FACC with the conguration given by Siand T as input colourful set, would nd another

colourful set T0 _{satisfying u ∈ cone(T}0₎_{. This means:}

u =

l

X

j=1

xltl, tj∈ T0, xj≥ 0, ∀j = 1, . . . , l.

Hence, there exists a vector x ≥ 0 such that:

M x = u, xi· xm+n+i= 0 ∀i = 1, . . . , m + n, supp(x) 6= {n + 1, . . . , 2n + m}.

We can write such x as (xA, xB) with xA, xB ∈ Rn+m+ , such that xA· xB = 0 and supp(xA) 6=

{n + 1, . . . , n + m}and supp(xB) 6= {1, . . . , n}. As we have seen, this provides a Nash equilibrium

of the original Bimatrix Game problem.

1.4.2 The Dantzig's diet problem and colourful linear programming

Another possible application, suggested to Meunier and Sarrabezolles by Max Klimm, is to use colourful linear programming as a modeling tool. We can imagine a generic colourful linear program as a mathematical program like:

min c ·x s.t. A x = b

xi≥ 0, ∀i = 1, . . . , n

| supp(x) ∩ Ic| ≤ 1, ∀i = 1, . . . , k,

where c ∈ Rn

, A ∈ Rd×n, b ∈ Rd, and where I1, . . . , Ikis a partition of indices {1, . . . , n}. In next

chapter we will analyze in depth some possible formulations of CLP in terms of Mixed-Integer linear programs. Now we focus on the so called diet problem, we rst dene it and then we show why and how it can be useful to model it as a colourful linear program.

The diet problem was introduced during the Second World War in order to decide the daily diet of US soldiers, with the purpose of minimizing costs of food. They are given a set of nutritional values and a set of foods, each of them containing a certain amount of each nutritional value. The problem is to decide what foods one soldier should eat each day, in order to respect the daily requirement of each nutriment. The problem can be modeled in a very simple way as a linear program. Formally, we have n foods and m nutritional values; a matrix A = (aij) ∈ Rm×n+ ,

(23)

1.4. POSSIBLE APPLICATIONS 17 vector b ∈ Rm

+ whose components bj are the amount of nutriment j that a man (a soldier) needs

daily; a vector r ∈ Rn

+ with components ri which indicate the maximum quatity of food i that

can be eaten daily. Finally, it is known the cost ci of one unit of food i. Thus, denoting with

x1, . . . , xnthe quantity of food i of the diet program, we can formulate the mathematical program

as follows:

min c ·x s.t. A x ≥ b

0 ≤ xi ≤ ri, ∀i = 1, . . . , n

In a paper of 1990, Dantzig demonstrated limits of this model by describing consequences when he tried to apply the model to his own diet: the main trouble is the lack of variety of the solutions obtained by solving in such a way. Even adding additional constraints, he alway got a solution including only one food, bran for example. In this context, variety of solution can be a desirable factor, also for practical reasons e.g. logistic ones.

Well, in these conditions, it can be used colourful linear programming to introduce a variety of the solution. Suppose that foods are partitioned into k dierent categories, say

{1, . . . , n} = I1∪ I2∪ · · · ∪ Ik,

and that we require a solution of diet problem with at most uc distinct foods per category Ic.

For this, we can add k new constraints to our model, that are: | supp(x) ∩ Ic| ≤ uc, ∀c = 1, . . . , k.

By making uc copies of Ic and adding corresponding variables, and using slack variables, this

model can be written in the standard of a colourful linear program. Through this process, we formulate a kind of colurful diet problem.

(24)

(25)

Chapter 2

Formulations of CLP problem

In this chapter, as in the rest of the work, we focus our attention on the more general colourful linear programming problem: CLP. Our aim is to write CLP as an optimization program, so that we can use classical approaches to treat it. First of all, it is necessary to x the notation adopted henceforth:

• dis the dimension of the space Rd _{and i = 1, . . . , d the coordinate;}

• k _{is the number of dierent colours, that is the number of sets S}1, . . . , Sk ⊆ Rd of the

conguration and c = 1, . . . , k is the colour; • S =Sk

c=1Sc is the set of all points of the conguration and N = |S| the total number of

them;

• lc is the number of points of colour c, thus |Sc| = lc, for all c = 1, . . . , k;

• ac

h ∈ Rd is the vector representing the coordinates of the h-th point of colour c, for all

h = 1, . . . , lc and c = 1, . . . , k; thus Sc= {ac1, . . . , aclc};

• ac

h,i is the i-th coordinate of the h-th point of colour c, that is:

ac_h=      ac h,1 ac_h,2 ... ac h,d      ;

• A ∈ Rd×N _{is the matrix whose columns are points coordinates:}

A =     ... ... ... ... ... a1 1 · · · a1l1 · · · a c h · · · a k 1 · · · aklk ... ... ... ... ...     ;

• T the resulting positively dependent colourful set.

For CLP problem, we propose three dierent Mixed-Integer Linear Programming formula-tions and a new - original - point of view of a Nonconvex Quadratic Programming formulation: we will treat it in terms of Dierence-of-Convex programming. For each of them we implemented a code in order to solve some classes of CLP feasible and infeasible instances through the solver IBM ILOG CPLEX Optimization Studio.

(26)

2.1 Mixed-Integer linear programming formulations

In order to get Mixed Integer linear programming formulations (MIP formulations), we introduce two sets of variables:

• binary variables (yc

h) ∈ {0, 1}, whose value is given by:

yhc =

(

1, if the h-th point of colour c is choosen, i.e. ac h∈ T

0, otherwise ,

for all h = 1, . . . , lc and c = 1, . . . , k;

• continuous variables (xc

h) ∈ [0, 1], representing the convex multiplier of the h-th point of

colour c, for all h = 1, . . . , lc and c = 1, . . . , k.

A rst mixed-integer formulation of CLP can be done in terms of feasibility problem, without an objective function. Consider the following mathematical program:

(MILP1) k X c=1 lc X h=1

ac_h,ixc_h= 0 ∀i = 1, . . . , d (2.1a) 0 ≤ xc_h≤ yc h ∀h = 1, . . . , lc, ∀c = 1, . . . , k (2.1b) k X c=1 lc X h=1 xc_h= 1 (2.1c) lc X h=1 yc_h= 1 ∀c = 1, . . . , k (2.1d) yc_h∈ {0, 1} ∀h = 1, . . . , lc, ∀c = 1, . . . , k (2.1e)

If there exists a solution xxx = (xc

h)of (MILP1), it produces a positively dependent colourful set

T = {ac h∈ R

d_{: x}c

h> 0}, solution of CLP. Constraints (2.1a),(2.1c) and the part x c

h≥ 0of (2.1b)

are necessary to ensure that a solution of (MILP1) corresponds to a positively dependent set T

(that is 0 ∈ conv(T )). Constraints (2.1d) force to choose a point for each colour and so the set T, dened from xxx, to be colourful.

A possible way to introduce a linear objective function is to minimize, among all positively dependent colourful sets, the distance between their convex hull and the origin: this minimal distance is zero if and only if CLP problem admits a solution. For this purpose, we introduce two sets of continuous variables vi and wi, for all i = 1, . . . , d. We can think that v = (vi)

is the point of conv(T ) which minimizes the distance between conv(T ) and the origin, hence constraints (2.1a) have to be modied as follows:

k X c=1 lc X h=1 ach,ix c h= vi, ∀i = 1, . . . , d. (2.2)

Therefore variables wi can be used to measure the absolute value of vi in this way:

wi≥ vi ∀i = 1, . . . , d (2.3a)

(27)

2.1. MIXED-INTEGER LINEAR PROGRAMMING FORMULATIONS 21 Thus, another Mixed-Integer formulation of the problem, which minimizes the norm k · k1 of the

vector v is given by:

(MILP2) min d X i=1 wi (2.4) s.t. k X c=1 lc X h=1 ac_h,ixc_h= vi, ∀i = 1, . . . , d (2.2) wi≥ vi, ∀i = 1, . . . , d (2.3a) wi≥ −vi, ∀i = 1, . . . , d (2.3b) 0 ≤ xc_h≤ yc h, ∀h = 1, . . . , lc, ∀c = 1, . . . , k (2.1b) k X c=1 lc X h=1 xc_h= 1 (2.1c) lc X h=1 y_hc = 1, ∀c = 1, . . . , k (2.1d) y_hc ∈ {0, 1}, ∀h = 1, . . . , lc, ∀c = 1, . . . , k. (2.1e)

Finally, we propose a Mixed-Integer formulation of the problem where the linear objective function is built in such a way as to minimize the distance between all positively dependent colourful sets and the origin, with respect to the metric induced by the uniform norm k · k∞.

Compared to (MILP2), there is just one variable w ∈ R such that:

w ≥ vi ∀i = 1, . . . , d (2.5a)

w ≥ −vi ∀i = 1, . . . , d (2.5b)

Thus, the third MIP formulation proposed is given by:

(MILP3) min w (2.6) s.t. k X c=1 lc X h=1 ac_h,ixc_h= vi, ∀i = 1, . . . , d (2.2) w ≥ vi, ∀i = 1, . . . , d (2.5a) w ≥ −vi, ∀i = 1, . . . , d (2.5b) 0 ≤ xc_h≤ yc h, ∀h = 1, . . . , lc, ∀c = 1, . . . , k (2.1b) k X c=1 lc X h=1 xc_h= 1 (2.1c) lc X h=1 y_hc = 1, ∀c = 1, . . . , k (2.1d) y_hc ∈ {0, 1}, ∀h = 1, . . . , lc, ∀c = 1, . . . , k. (2.1e)

2.1.1 Numerical experiments

We implemented a code in C++ for all three MIP formulations above described. Since they are linear programs, we solved them by using the solver CPLEX. The innovation of our program

(28)

Table 2.1: Test results obtained with our code applied on CC feasible instances created by Huang. For each dimension we tested our code on 5 instances, the result is the average of them. Execution time is expressed in seconds. TL stands for Time Limit: we set it equals to 600 seconds and in the relative column we report how many times it has been reached.

Random Unbalanced Highdensity Lowdensity d time TL time TL time TL time TL

(MILP1) 3 0.0000001 0 0.0000001 0 0.0000001 0 0.0000001 0 6 0.002 0 0.006 0 0.00001 0 0.002 0 12 0.272 0 0.216 0 0.01 0 2.786 0 24 106.692 0 19.954 0 0.05 0 - 5 48 - 5 - 5 1.74 0 32.14 4 96 - 5 - 5 6.678 0 360.835 3 192 - 5 - 5 1.375 3 - 5 (MILP2) 3 0.000001 0 0.000001 0 0.000001 0 0.000001 0 6 0.006 0 0.008 0 0.00002 0 0.008 0 12 0.296 0 0.318 0 0.014 0 1.332 0 24 37.418 0 27.29 0 0.124 0 341.028 0 48 - 5 - 5 2.076 0 597.75 4 96 - 5 - 5 229.588 0 - 5 192 - 5 - 5 - 5 - 5 (MILP3) 3 0.000001 0 0.000001 0 0.000001 0 0.000001 0 6 0.004 0 0.002 0 0.00004 0 0.006 0 12 0.322 0 1.098 0 0.02 0 3.374 0 24 96.44 0 269.082 0 2.64 1 293.072 0 48 - 5 - 5 5.534 0 43.87 4 96 - 5 - 5 221.712 0 - 5 192 - 5 - 5 - 5 - 5

stands in the fact that we can solve any kind of CLP instance, in contrast with Huang's and Meunier-Sarrabezolles programs, which just nd a solution of CC problems under feasibility conditions. With our code we can both generate random instances or read others created before. In the rst case, input data are F, d, k, lmin, lmax, pmin, pmax, T L. A CLP instance is created

in dimension d, with k dierent colours, whose size is between lmin and lmax; each point is

pseudo-randomly generated with components choosen in the interval [pmin, pmax]. We construct

a MILP model according to the formulation F ∈ {1, 2, 3} and solve it through CPLEX with a time limit equal to T L.

First, we tested our code on some of CC feasible instances in which Bárány-Onn and Meunier-Sarrabezolles algorithms were tested, that is on instances created by Huang in [11]. We report our results in Table 2.1. As it can be seen, the eciency of Bárány-Onn and Meunier-Sarrabezolles algorithms is much better than our approach in terms of linear programming. Nevertheless, their algorithms are suitably developed for CC feasible instances which represent a particular

(29)

2.1. MIXED-INTEGER LINEAR PROGRAMMING FORMULATIONS 23 Table 2.2: Test results obtained with our code applied on CLP infeasible instances with d = k and two points per colour. Time is expressed in seconds and the time limit is set to 600 (it is reached only in dimension d = 10000 with formulation MILP3).

Infeasible instances (MILP1) (MILP2) (MILP3)

d = k time time time

100 0.0001 0.001 0.01 200 0.002 0.02 0.06 500 0.01 0.04 0.3 1000 0.03 0.14 1.23 2000 0.12 0.55 5.56 5000 0.68 3.7 37.97 10000 2.63 15.8 TL

class of CLP ones. Anyway, for all kinds of tested instances, best results are obtained by using formulation (MILP1), i.e. without an objective function.

We also tested our code on some general CLP instances. We tried to apply our MIP models on infeasible instances with the number of colours equal to the dimension (d = k) and with two points per colour c : ± ec = (0, . . . , 0, ±1, 0, . . . , 0). We have already stressed that in this case,

even if each set Sc is positively dependent, CLP has no solution. Results achieved are described

in Table 2.2 : also in this case, execution times are shorter for (MILP1) formulation than for

(MILP2) and (MILP3) models.

We executed other tests on CLP instances generated in this way: the dimension d is greater than the number of colours k and the number of point per colour l = lc, for any c, is small

(we take l = 2, 3, 4, 5); points are choosen randomly. Rarely this kind of instances CLP has a solution: in fact, all instances we generated were infeasible. Results can be found in Table 2.3 : MILP1model is always the best. Note that as the number of points per colour l raises, execution

time increases signicantly.

Finally, we tested our program on CLP instances generated from instances of the Knapsack Problem, seen as particular cases of SUBSET SUM problem (we showed the reduction during the proof of Theorem 4). Results with execution times can be found in Table 2.4. Once again, (MILP1) is more ecient than (MILP2), which is in turn better than (MILP3).

(30)

Table 2.3: Test results obtained with our code applied on CLP instances with d > k and few points per colour. We tested the code on 5 instance for each type. Time results are averages, expressed in seconds; time limit is set to 600 and in the column TL we report how many times it is reached.

(MILP1) (MILP2) (MILP3)

d k lc time TL time TL time TL

10 8 2 0.00002 0 0.0004 0 0.0004 0 10 8 3 0.005 0 0.006 0 0.004 0 10 8 4 0.001 0 0.052 0 0.068 0 10 8 5 0.162 0 0.248 0 0.278 0 20 16 2 0.001 0 0.008 0 0.014 0 20 16 3 0.018 0 0.722 0 0.344 0 20 16 4 2.884 0 5.538 0 7.484 0 20 16 5 415.544 0 - 5 - 5 40 30 2 0.002 0 0.266 0 0.144 0 40 30 3 0.438 0 97.154 0 21.1 0 40 30 4 264.208 0 - 5 - 5 40 30 5 - 5 - 5 - 5 80 60 2 0.004 0 3.588 0 9.496 0 80 60 3 9.162 0 - 5 - 5 80 60 4 - 5 - 5 - 5 80 60 5 - 5 - 5 - 5 100 80 2 0.084 0 30.860 0 25.892 0 100 80 3 - 5 - 5 - 5 100 80 4 - 5 - 5 - 5 100 80 5 - 5 - 5 - 5

(31)

2.1. MIXED-INTEGER LINEAR PROGRAMMING FORMULATIONS 25

Table 2.4: Test results obtained with MILP formulations on CLP instances reduced from KP. Experiments were done on 5 instances per dimension. Time is expressed in seconds and the time limit is set to 600. (MILP1) N d k time TL GAP 100 102 103 1.974 0 -200 202 203 3.722 0 -400 402 403 5.928 0 -800 802 803 11.046 0 -1600 1602 1603 21.518 0 -3200 3202 3203 54.424 0 -(MILP2) 100 102 103 3.838 0 -200 202 203 12.494 0 -400 402 403 20.196 0 -800 802 803 108.958 0 -1600 1602 1603 271.973 2 0.584065 3200 3202 3203 - 5 0.141541 (MILP3) 100 102 103 2.536 0 -200 202 203 3.78 0 -400 402 403 12.118 0 -800 802 803 83.432 0 -1600 1602 1603 399.37 2 0.00095 3200 3202 3203 - 5 0.0004668

(32)

2.2 Dierence-of-Convex formulation

Following a I. Pólik suggestion, in his thesis Huang [11] presents a Nonconvex Quadratic Program-ming formulation of CLP problem. It is mathematical optimization program with a quadratic nonconvex objective function and linear constraints:

(NC-QP) min xxxTTT· Q · xxx (2.7) A · xxx = 000 N X i=1 xi = 1 xi≥ 0, ∀i = 1, . . . , N

where Q ∈ RN ×N _{is a block diagonal matrix, whose blocks B}

1, . . . , Bk represents colours and

are symmetrical submatrices of the type:

Bc=       0 1 · · · 1 1 0 ... ... ... ... ... 1 1 · · · 1 0       ∈ Rlc×lc_.

We propose an original point of view of that formulation in terms of Dierence of Convex (DC) programming. A DC program is an optimization problem dealing with functions that can be written as dierence of two convex ones (DC functions). Basic concepts of DC programming theory will be discussed in next chapter.

The idea arises from the fact that each block Bc can be equivalently rewritten as e · eT− Ilc,

with e ∈ Rlc being the vector with all 1 entries and I

lc the identity matrix. Thus (NC-QP) can

be seen as the following DC program:

(DC) min k X c=1   lc X h=1 xc_h !2 − lc X h=1 xc_h2   (2.8a) s.t. k X c=1 lc X h=1

ac_h,ixc_h= 0 ∀i = 1, . . . , d (2.1a)

xc_h≥ 0 ∀c = 1, . . . , k, ∀h = 1, . . . , lc (2.8b) k X c=1 lc X h=1 xc_h= 1 (2.1c)

As for (MILP2) and (MILP3), the optimal value of (DC), or else (NC-QP), is equal to zero

if and only if CLP is feasible and, if xxx = (xc

h)is an optimal solution, then a solution of CLP is

given by the set

T =ac h| x

c

h> 0, c = 1, . . . , k, h = 1, . . . , lc .

In fact, the DC objective function (2.8a) can be rewritten as

k

X

c=1

kxc_k2

(33)

2.2. DIFFERENCE-OF-CONVEX FORMULATION 27 where xc_{= (x}c

1, . . . , xclc) ∈ R

lc. Now, since for every x it holds that

kxk1≥ kxk2 and kxk1= kxk2 ⇐⇒ x = λej, for some λ ∈ R ,

it follows that the objective function is always nonnegative and

k X c=1 kxc_k2 1− kx c_k2 2= 0 ⇐⇒ kx c_k 1= kxck2, ∀c = 1, . . . , k ,

which means that for any colour c = 1, . . . , k the vector xc

∈ Rlc has at most one nonzero (hence

positive) coordinate. If it happens, we have that for any colour c = 1, . . . , k at most one point in Sc is choosen for the resultant set T , namely the set T is colourful.

Another way to see this, is to write the objective function explicitly:

k X c=1   lc X h=1 xc_h !2 − lc X h=1 xc_h2  = 2 k X c=1   lc X h=1 lc X p=h+1 xc_hxc_p  . It is nonnegative on the feasible region (since x ≥ 0) and it equals zero if and only if

lc X h=1 lc X p=h+1 xc_hxc_p= 0, ∀c = 1, . . . , k

which is equivalent to say that, for any colour c, at most one coecient xc

h is nonzero (i.e. T is

colourful). Finally, constraints (2.1a) guarantee that T is positively dependent.

2.2.1 Examples of DC formulation

We describe two easy examples of this formulation. First, consider in R6 _{the instance of}

CLP given by the following conguration:

S1=                        1 0 −3 2 4 −1         ,         −3 2 0 −1 0 1         ,         2 0 1 0 −4 −5         ,         0 0 −2 −3 −1 2                        , S2=                        5 −1 −2 0 −3 1         ,         6 4 0 −2 0 2         ,         0 0 5 −3 1 0                        , S3=                        1 0 1 0 1 0         ,         1 1 1 1 1 1         ,         0 −1 0 −1 0 −1         ,         −2 0 0 2 1 −1         ,         1 −2 −5 4 3 0         ,         −1 −3 4 2 −1 −1                        , S4=                        0 0 1 0 0 0         ,         2 0 0 −2 −1 1                        .

So, in this case we have d = 6, k = 4, l = (4, 3, 6, 2) and a total number of points N = 15. Matrix A ∈ R6×15 is obtained by coordinates of points ach:

A =         1 −3 2 0 5 6 0 1 1 0 −2 1 −1 0 2 0 2 0 0 −1 4 0 0 1 −1 0 −2 −3 0 0 −3 0 1 −2 −2 0 5 1 1 0 0 −5 4 1 0 2 −1 0 −3 0 −2 −3 0 1 −1 2 4 2 0 −2 4 0 −4 −1 −3 0 1 1 1 0 1 3 −1 0 −1 −1 1 −5 2 1 2 0 0 1 −1 −1 0 −1 0 1         .

(34)

The DC objective function f(xxx) can be written as f (xxx) = x1₁+ x1₂+ x1₃+ x1₄2 + x2₁+ x2₂+ x2₃2 + x3₁+ x3₂+ x3₃+ x3₄+ x3₅+ x3₆2 + x4₁+ x4₂2 −h(x1₁)2+ (x₂1)2+ (x1₃)2+ (x1₄)2+ (x2₁)2+ (x2₂)2+ (x2₃)2 + (x3₁)2+ (x3₂)2+ (x3₃)2+ (x3₄)2+ (x3₅)2+ (x3₆)2+ (x4₁)2+ (x4₂)2i = 2h x1₁x1₂+ x1₁x₃1+ x1₁x1₄+ x1₂x1₃+ x₂1x1₄+ x1₃x1₄ + x2₁x2₂+ x2₁x2₃+ x2₂x2₃ + x3₁x3₂+ x3₁x3₃+ x3₁x3₄+ x3₁x3₅+ x3₁x3₆+ x3₂x3₃+ x3₂x₄3+ x3₂x3₅+ x3₂x3₆ + x3₃x3₄+ x3₃x3₅+ x3₃x3₆+ x3₄x3₅+ x3₄x₆3+ x3₅x3₆ + x4 1x 4 2 i

The DC formulation is then: min {f(xxx) : Axxx = 000, eT_x_x_{x = 1, x}_x_{x ≥ 0}₀_0}_{. Its optimal value is zero}

and an optimal solution ¯x¯x¯x is

         ¯ x1 1 = 0 ¯ x1₂ =1₂ ¯ x1 3 = 0 ¯ x1₄ = 0 ,      ¯ x1 1 = 0 ¯ x1 1 = 14 ¯ x1 1 = 0 ,                    ¯ x1₁ = 0 ¯ x1 1 = 0 ¯ x1₁ = 0 ¯ x1 1 = 1 8 ¯ x1₁ = 0 ¯ x1 1 = 0 , ( ¯ x1₁ = 0 ¯ x1 1 = 1 8 .

From ¯x¯x¯x we get a positively dependent colourful set

T =a1 2, a 2 2, a 3 4, a 4 2 =                        −3 2 0 −1 0 1         ,         6 4 0 −2 0 2         ,         −2 0 0 2 1 −1         ,         2 0 0 −2 −1 1                        which is a solution of CLP.

Now we show an example in which CLP is infeasible, but (DC) admits optimal solution (therefore) with strictly positive optimal value. Consider the following conguration in R3 _with

d = k = 3and l = (2, 2, 2): S1=      1 0 0  ,   −1 0 0      , S2=      0 1 0  ,   0 −1 0      , S3=      0 0 1  ,   0 0 −1      .

We said that this CLP instance is infeasible. The objective function of the DC formulation is f (xxx) = 2 x1

1x12+ x21x22+ x31x32

_{and the optimal solution is}

¯ x¯ x¯ x = 1 6, 1 6, 1 6, 1 6, 1 6, 1 6 thus f(¯x¯x¯x) =1 6 > 0.

(35)

2.2. DIFFERENCE-OF-CONVEX FORMULATION 29 Table 2.5: Test results obtained with our code and (NC-QP) formulation applied on CC instances created by Huang. For each dimension we tested the code on 5 instances, the result is the average of them. Execution time is expressed in seconds and the time limit is set to 600 seconds: in the relative column we report how many times it has been reached.

(NC-QP) Random Unbalanced Highdensity Lowdensity d time TL time TL time TL time TL 3 0.004 0 0.001 0 0.0001 0 0.0001 0 6 0.001 0 0.004 0 0.001 0 0.002 0 12 0.044 0 0.036 0 0.024 0 8.512 0 24 - 5 - 5 0.57 2 169.2725 1 48 - 5 - 5 - 5 7.05 4 96 - 5 - 5 - 5 90.63 3 192 - 5 - 5 44.27 4 - 5

Table 2.6: Test results obtained with our code, by using the (NC-QP) formulation, applied on CLP infeasible instances with d = k and two points per colour. Execution time is expressed in seconds. Infeasible instances (NC-QP) d = k time 100 1.58 200 6.54 500 12.72 1000 23.89 2000 46.67 5000 120.44 10000 268.58

2.2.2 Numerical experiments

We wrote a code in C++ in order to solve the (NC-QP) formulation of CLP. We still use the solver CPLEX which allows, in its latest versions, to solve models with nonconvex but quadratic objective function, provided that constraints are linear, as in our case. Moreover, we set the upper cuto parameter CPX_PARAM_CUTUP to 0, which forces to discard any solution greater than it. So, in case of infesibile instances, we got a signicant eciency improvement.

As done for MIP models, rst tests were done on CC feasible instances generated by Huang in his thesis [11]. Results are in Table 2.5: it can be seen that execution times are greater than ones obtained by using MIP formulations. Nevertheless, for types Highdensity and Lowdensity in dimension d ≥ 24, some instances are eciently solved while others reach time limit.

Second test regards CLP infeasible instances with d = k and two points per colour. Results achieved are described in Table 2.6 : execution times are worse than (MILP1) and (MILP2)

formulations, but better than (MILP3) formulation for larger dimension (d ≥ 10000).

Finally, we tested the (NC-QP) model on infeasible CLP instances randomly generated with d > k and on instances reduced from Knapsack Problem. Results are described in Table 2.7 and Table 2.8, respectively.

(36)

Table 2.7: Test results obtained with our code applied on CLP instances with d > k and few points per colour. We tested the code on 5 instance for each type. Time results are averages, expressed in seconds; time limit is set to 600 and in the column TL we report how many times it is reached. (NC-QP) d k lc time TL 10 8 2 0.0002 0 10 8 3 0.0032 0 10 8 4 0.158 0 10 8 5 13.48 0 20 16 2 0.001 0 20 16 3 0.688 0 20 16 4 - 5 20 16 5 - 5 40 30 2 0.002 0 40 30 3 - 5 40 30 4 - 5 40 30 5 - 5 80 60 2 0.034 0 80 60 3 - 5 80 60 4 - 5 80 60 5 - 5 100 80 2 0.068 0 100 80 3 - 5 100 80 4 - 5 100 80 5 - 5

Table 2.8: Test results obtained with (NC-QP) formulation solved through CPLEX on CLP in-stances reduced from KP. Experiments were done on 5 inin-stances per dimension. Time is expressed in seconds and the time limit is set to 600.

(NC-QP) n d k time TL GAP 100 102 103 0.272 0 -200 202 203 0.194 0 -400 402 403 0.02 0 -800 802 803 0.048 0 -1600 1602 1603 0.412 0 -3200 3202 3203 0.99 0

(37)

-Chapter 3

DC programming applied to CLP

problem

In this chapter we describe fundamental concepts about DC programming theory by introducing DC functions and their main properties, DC programs in canonical form. Then we analyze an existing algorithmic scheme for a special class of DC programs. Finally we streamline and adapt it to our specic case of model (DC) for CLP.

3.1 DC functions

Denition 3. Let C ⊆ Rn _{be a convex set. A function f : C → R is called DC on C if there}

exist two convex functions g, h: Rn

→ R such that f(x) = g(x) − h(x) for any x ∈ C. If C = Rn

then f is simply called DC function.

A representation of the form f = g − h is said a DC decomposition of f. Convex and concave functions are particular examples of DC functions. Also a quadratic form f(x) = xT_{Q x}_{is a DC}

function: in fact, for any n × n symmetric matrix Q, dened two positive semidenite matrices A = 1₂(QT_+Q)_{and B =} 1

2(Q

T_−Q)_{it holds that f(x) = x}T_{A x−x}T_{B x}_{. Actually most functions}

encountered in practice are DC, but it may be not really immediate to nd a DC decomposition. The rst property of these functions we present is their stability under some operations frequently used in optimization theory.

Proposition 2. Let f, fi, for i = 1, . . . , k, be DC functions. Then the following are also DC

functions: 1. Pk

i=1λifi(x), with λi∈ R, i = 1, . . . , k;

2. maxifi(x) and minifi(x);

3. |f(x)|, f+_{(x) = max{0, f (x)}}_{and f}+_{(x) = − min{0, f (x)}}_;

4. Qk

i=1fi(x).

Proof. The result can be proved constructively, giving an explicit DC decomposition for each function dened above. Regarding point (1.) it is trivially to see that a linear combination of DC function is DC. Let us show for (2.) that

f (x) = max {fi(x) = gi(x) − hi(x) : i = 1, . . . , k}

Colourful Linear Programming: MIP formulations and an algorithm for a Difference-of-Convex formulation.

Università di Pisa

Corso di Laurea Magistrale in Matematica

TESI DI LAUREA

Colourful Linear Programming: MIP formulations

and an algorithm for a Dierence-of-Convex

formulation

Relatori

Candidato

Prof. Antonio Frangioni

Tiziano Amicone

MCF Fabio Furini

Controrelatore

Prof. Dario A. Bini

Contents

Introduction

Chapter 1

The Colourful Linear Programming

problem

1.1 Problem denition

Why Linear Programming?

1.1.1 Colourful Linear Programming

1.1.2 Further colourful problems

1.1.3 Special cases studied in literature

1.2 The complexity

1.3 Known algorithms for CC problems under feasibility

condition

1.3.1 The Bárány-Onn algorithm

1.3.2 The Meunier-Sarrabezolles algorithm

1.4 Possible applications

1.4.1 Colourful linear programming and Nash equilibria

1.4.2 The Dantzig's diet problem and colourful linear programming

Chapter 2

Formulations of CLP problem

2.1 Mixed-Integer linear programming formulations

2.1.1 Numerical experiments

2.2 Dierence-of-Convex formulation

2.2.1 Examples of DC formulation

2.2.2 Numerical experiments

-Chapter 3

DC programming applied to CLP

problem

3.1 DC functions

and an algorithm for a Dierence-of-Convex

1.1 Problem denition

2.2 Dierence-of-Convex formulation