[PDF] Theoretical and computational study of several linearisation

View - Download Theoretical and computational study of several linearisation

Previous PDF

Next PDF

Theoretical and computational study of several linearisation techniques for Binary Quadratic Problems

Fabio Furini

1and Emiliano Traversi2

1 PSL, Universit´e Paris Dauphine, CNRS, LAMSADE UMR 7243

75775 Paris Cedex 16, France.fabio.furini@dauphine.fr

2 Laboratoire d"Informatique de Paris Nord, Universit´e de Paris 13,

Sorbonne Paris Cit

´e, 99, Avenue J.-B. Clement 93430 Villetaneuse, France. emiliano.traversi@lipn.univ-paris13.fr

Abstract

We perform a theoretical and computational study of the classical Linearisation Techniques (LT)andweproposeanewLTforBinaryQuadraticProblems(BQPs). Wediscusstherelations between the Linear Programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the Maximum Cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance , we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the Knapsack and Stable Set problems. keywords:LinearisationTechniques, BinaryQuadraticProblems, MaxCutProblem, Quadratic

Knapsack Problem, Quadratic Stable Set Problem.

1. Introduction

A widely used technique for solving Binary Quadratic Problems (BQPs) is by formulating them as Mixed Integer Linear Programs (MILPs). The main adv antageof these linear reformulations is the use of generic MILP solvers which k eepimpro vingtheir computational performance (see for example Lodi [19]) . Several Linearisation Techniques (LTs) have been proposed in the literature, the seminal works of this stream of research are Fortet [9] and Glover and Woolsey [12], both based on introducing additional binary variables

Other L Tsha vebeen proposed based only on

introducing additional continuous variables; in this stream of research we cite the follo wingw orks: Glover and Woolsey [13], Glover [11], and Sherali and Smith [24]. All these L T s are presented in detail in Section 2 and compared in Section 3, which is de votedto computational results . The LT of Chaovalitwongse et al. [6] is deeply related to the L T of Sherali and Smith and, for this reason, these two techniques will be discussed together.

A further

L T is presented by Adams and Sherali [2], this approach is generalized to design the reformulation-linearisation technique (RLT) in Sherali and Adams [23]. Recently ,other interesting L Tsha vebeen introduced in Gue ye and Michelon [14] and Hansen and Meyer [15]. In [14], the authors propose a framework for unconstrained BQP based on two steps: in the first step the objective function is decomposed with 1 a clique covering heuristic algorithm, while in the second step, valid inequalities are added to the model to get a better dual bound. In [15], a new family of LTs with a linear number of additional variables and constraints is presented. These LTs are based on a polyform representation of the objective function. The authors show that the best LT among the ones proposed is as tight as the LT of Glover and Woolsey [13] and it requires the solution of an auxiliary LP with a quadratic number of additional variables and constraints. Paper Contribution.A first contribution of this paper is an overview of the strength of the Linear Programming (LP) relaxations of several LTs. Our analysis points out new interconnections between the classical LTs and an alternative LT, called Extended Linear Formulation (ELF). This new LT has been inspired by the ideas proposed in Jaumard et al. [17], where a reformulation specifically conceived for the Quadratic Stable Set Problem (QSSP) is proposed. For generic BQPs, the LT proposed by Glover and Woolsey in [13] and ELF are stronger than the LTs proposed by Glover in [11] and Sherali and Smith in [24]. The first two LTs require a quadratic number of additional variables and constraints, while the third and the forth require only a linear number. A new theoretical result presented is the equivalence between the LP-relaxation value of all the LTs introduced for a specific class of BQPs. This class is rather generic and it contains the BQP formulation of the Max-Cut Problem. An additional contribution of this paper is an extensive computational comparison of the LTs for four different classes of problem with and without linear constraints. In particular, we tested the Unconstrained BQP, the Max Cut Problem and the quadratic extensions of the Knapsack and the Stable Set problems.

2. Linearisation techniques for Binary Quadratic Problems

A generic Binary Quadratic Problem (BQP), withnvariables andpconstraints, can be formulated using the following quadratic formulation min nX i=1n X j=1Q ijxixj+nX i=1L ixi:x2K; x2 f0;1gn) whereQ2Rnn,L2Rn,K=fx2Rn:Axbg,A2Rpnandb2Rp.Qis a generic symmetric matrix, not restricted to being convex.

W ithoutloss of generality ,we may assume

Q ii= 0, since we may incorporate those elements in the linear termsLi(for a given binary variable xwe havex2=x).In the follo wing,we define as the Linear Programming (LP) Relaxation of a formulation, the same formulation where the constraintsx2 f0;1gnare substituted byx2[0;1]n.

In the next sections,

we describe se veralalternati vesfor

L Tsfor

BQPs present in the literature and

then we introduce the ne wExtended Linear F ormulation(ELF)

2.1 Glover-Woolsey Linear Formulation

The standard method for linearising the quadratic terms is the one introduced by Glover and Woolsey and described in [13]. This linear formulation, called GW [13], reads as follows. 2 GW [13]: minnX i=1n X j=i+12Qijyij+nX i=1L ixi y ijxii;j= 1;:::;n; i < j(1) y ijxji;j= 1;:::;n; i < j(2) y ijxi+xj1i;j= 1;:::;n; i < j(3) y ij0i;j= 1;:::;n; i < j(4) x2K x2 f0;1gn: A new variableyijtakes the place of the product between the original variablesxiandxjin the objective function. We recall that GW [13]increases the size of the problem by addingn(n1)=2 variables and4n(n1)=2constraints. These constraints enforceyij=xixjfor allcouples of binary variablesxiandxj. A constraint is redundant for a formulation if its removal does not change the set of optimal solution s of its LP-relaxation.

Accordingly ,the number of co nstraintsof GW

[13]can be reduced as follows: Proposition 1.Inequalities(1)and(2), corresponding tonon-ne gativeentries of Q, and inequal- ities(3)and(4), corresponding tonon-positive entries of Q, are redundant forGW[13]. Proof.See for example Forrester and Greenberg [8].GW [13]can be strengthened by applying the so-called Reformulation Linearisation Technique (RLT) presented in Sherali and Adams [23]. The RLT is a procedure divided into two steps: the reformulation step creates additional nonlinear constraints by multiplying the constraints inKby product factors of the binary variablesxand their complements(1x), and subsequently enforces the identityx2=x. The linearisation step then substitutes a continuous variable for each distinct product of variables. Hence, GW [13]can be viewed as first level RLT applied only on the bound constraints0x1.An alternati vew ayto impro vethe strength of GW [13]is to include the so-called triangle and cycle inequalities (see for example [14] or [20] ). In our analysis we do not consider these enhancements since we are interested in the basic version of GW [13].

2.2 Glover Linear Formulation

In this section we introduce the linearisation described in Glover [11]. This linear formulation, called G [11], reads as follows. 3 G [11]: minnX i=1w i+nX i=1L ixi w iQ+ ixii= 1;:::;n(5) w iQ ixii= 1;:::;n(6) w inX j=1Q ijxjQ i(1xi)i= 1;:::;n(7) w inX j=1Q ijxjQ+ i(1xi)i= 1;:::;n(8) x2K x2 f0;1gn; whereQ+ iandQ iare suitable upper and lower bounds on the expressionPn j=1Qijxj, respec-

tively. The main idea behind this linearisation is the introduction of the additional set of variables

w irepresenting the quantityPn j=1Qijxjifxi= 1, or taking a value of0otherwise. Formulation G [11]has the big advantage of using less variables and constraints than GW[13]. On the other hand,

it requires the introduction of the so-called "big-M" constraints, leading to a weaker LP-relaxation.

An important point concerns the computation ofQ

iandQ+ i. In Glover [11], the author sug- gest s to impose: Q i=nX j=1minf0;Qijg; Q+ i=nX j=1maxf0;Qijg:(9) Subsequently, in several works (see for example Adams et al. [1] and Wang et al. [25]) this approach has been improved by taking into account the feasible regionKand hence computing the values forQ iandQ+ iwith more accuracy. This can be done as follows: Q i= minx2Kn X j=1Q ijxj; Q+ i= maxx2Kn X j=1Q ijxj:(10) It is easy to check that equations (9) and equations (10) coincide whenK=;. From now on, when we refer to G [11]we imply the version withQ iandQ+ idefined in (9), since computing equations (10) may require the solution of an optimization problem which depends on the structure ofK. Regardless of the method used for computingQ iandQ+ i, G[11]increases the size of the problem by adding onlynvariables and4nconstraints. However, since we are minimizing and the coefficients of thewvariables are positive, it is possible to reduce the number of constraints: Proposition 2.Inequalities(5)and(7)are redundant forG[11].

Proof.See Adams et al. [1].4

2.3 Sherali-Smith Linear Formulation

The third method linearises the quadratic terms using the techniques described in Sherali and

Smith [24]. This linear formulation, called SS

[24], reads as follows: SS [24]: minnX i=1s i+nX i=1(Li+Q i)xi y i=nX j=1Q ijxjsiQ ii= 1;:::;n(11) y i(Q+ iQ i)(1xi)i= 1;:::;n(12) s i(Q+ iQ i)xii= 1;:::;n(13) y i0i= 1;:::;n(14) s i0i= 1;:::;n(15) x2K x2 f0;1gn; whereQ+ iandQ iare defined as in (9) or in (10). Since the latter case requires the computation of an additional optimization problem, we use (9) as for G [11].In Sherali and Smith [24], the authors introduce three formulations, calledBP,BPandBP-strong. However, in absence of quadratic constraints, they are all equivalent and they can be written as SS [24]. The idea behind SS [24]is similar to the one behindG [11], i.e., the introduction of additional variables representing the sumPn j=1QijQ iand using big-M constraints. SS[24]increases the size of the problem by adding2nvariables,4ninequalities andnequations.More precisely ,v ariablesycan be projected out using equations (11), thus resulting in onlynadditional variables and4ninequalities (12)-(15).

FormulationSS

et al. [6] called CPP [6]which uses instead the followingweak er(see Sherali and Smith [24]) definition ofQ+ iandQ i: Q i= maxin X j=1jQijj; Q i=maxin X j=1jQijj:

Like for G

[11], also for SS[24](and analogously for CPP[6]) some constraints can be eliminated: Proposition 3.Inequalities(13)and(14), are redundant forSS[24].

Proof.See Sherali and Smith [24].5

2.4 Extended Linear Formulation

We now introduce a new linearisation, called Extended Linear Formulation (ELF).

ELF : min

nX i=1n X j=1Q ij+nX i=1L ixinX i=1n X j=i+12Qij(ziij+zj ij) z iij+zj ij1i;j= 1;:::;n; i < j(16) x i+ziij1i;j= 1;:::;n; i < j(17) x j+zj ij1i;j= 1;:::;n; i < j(18) x i+ziij+zj ij1i;j= 1;:::;n; i < j(19) x j+ziij+zj ij1i;j= 1;:::;n; i < j(20) x2K x2 f0;1gn: This linearisation increases the size of the problem by addingn(n1)variables and5n(n1) constraints . A pair of new variablesziijandzj ijis used instead of the product of variablesxiand x j. These new variables modify the objective function and appear in the new set of constraints. The total sum of the quadratic costs is paid in the objective function (Pn i=1P n j=1Qij) and then the correct value is reconstructed with the use of thezvariables (Pn i=1P n j=i+12Qij(ziij+zj ij)). The values of thezvariables are set according to the values of thexvariables thanks to constraints (16)-(20), i.e., ifxi=xj= 1thenziij=zj ij= 0,on the other hand, if one or both v ariablesxiand x jhave a value of0, then we haveziij+zj ij= 1, which implies the correctness of the formulation. Finally, the following Proposition allows the reduction of the number of constraints also for ELF: Proposition 4.Inequalities(19)and(20), corresponding to non-negative entries ofQ, and in- equalities(16),(17)and(18), corresponding to non-positive entries ofQare redundant for ELF. Proof.Let(~x;~zi;~zj)be an optimal solution of the LP-relaxation of ELF satisfying all inequalities except one of the constraints (19) associated to an entryQkl0. Letxk+zikl+zj kl1be the violated inequality.

And w .l.o.g,we assume that ~zj

kl0, since the other constraints impose:0 z ikl+zj kl1.W ecan increase the v alueof ~ziklto~zikl+with = minf1~zikl~zj kl;1~xk~ziklg.

The constraint is violated hence~xk+ ~zikl+ ~zj

kl<1, this implies: (i)0<1~zikl~zj kl;since0~xk and~xk<1~zikl~zj kl; (ii)0<1~xk~zikl;since~xk+ ~zikl<1and~zj kl0; and therefore,is positive. By observing that corresponds to the minimum between the slacks of constraints (16) and (17) associated tokandl, the new solution is feasible by construction. The objective function value decreases byQkjThis contradicts the fact of being optimal and violating one of the constraints (19). The same holds for constraints (20). Similar considerations can be done for inequalities (16), (17) and (18) whenQkl0. Hence,quotesdbs_dbs22.pdfusesText_28

[PDF] HISTOIRE DES ARTS Christian Boltanski, Personnes, 2010

[PDF] Ocho participantes del BOmm 2017 estarán en el mercado de

[PDF] bon de commande - Corsica Ferries

[PDF] BREVET D 'ÉTUDES PROFESSIONNELLES option cuisine épreuve

[PDF] Bon de commande - ECPA

[PDF] Chorus Portail Pro 2017 - Communauté Chorus Pro

[PDF] Prestations sur bon de commandes

[PDF] La bonne utilisation de l 'e-mail dans l 'entreprise - Medef

[PDF] Guide de bon usage de la messagerie électronique - Thales Group

[PDF] les aides financières individuelles aux familles - Caf

[PDF] Une aide ? votre portée - Afe

[PDF] guide de la retraite 2016 dans la fonction publique d 'état - Solidaires

[PDF] dictionnaire fang - français français - fang - (DDL), Lyon

[PDF] Bonjour Vietnam - MCFV

[PDF] Les mails d 'accompagnement - Université Rennes 2