AnoteonQUBOinstancesdefinedonChimeragraphs SanjeebDashIBMT.J.WatsonResearchCenter May9,2017 arXiv:1306.1202v1[math.OC]5Jun2013 Abstract McGeoghandWang(2013)recentlyobtainedoptimalornear-optimalsolutionstosomequadraticunconstrainedbooleanoptimization(QUBO)problemsusinga439qubitD-WaveputerinmuchlesstimethanwiththeIBMILOGCPLEXmixed-integerquadraticprogrammingsolver.TheproblemsstudiedbyMcGeoghet.al.aredefinedonsubgraphsof512nodeChimeragraphs.WeobservethatafterastandardreformulationofQUBOproblemsdefinedon512nodeChimeragraphsasmixedintegerlinearprograms(MILP),theycanbesolvedtooptimalitywiththeCPLEXMILPsolverinparabletothetimereportedbyMcGeoghandWangfortheD-waveputer. 1Introduction Thequadraticunconstrainedbooleanoptimization(QUBO)problemistheproblemofminimizingaquadraticfunctionofn{0,1}variables,see[6]forapplications.Itisaspecialcaseofthemixed-integerquadraticprogramming(MIQP)problem.AQUBOinstanceonnvariablesisspecifiedbyan×nmatrixQ: MinQijxixjsubjecttox∈{0,1}n.
(1) i,j AQUBOinstanceisassociatedwithaweightedgraph,G′={G=(
V,E),w},whereGisann-nodeunweightedgraphwithnodesetVandedgesetE,w:V×V→Rdefinestheweightofnodesandedges,w((i,j))=Qij+Qjiforalli=jwith(i,j)∈E,andw((i,i))=Qiiforalli,andiszerootherwise.Giscalledtheconnectivitygraph.ThedecisionversionoftheQUBOproblemispleteevenwhenG isaplanarcubicgraph[2],andpleteforgraphscontainingaplanarcubicgraphasaminor,suchas 2DgridgraphsorChimeragraphs(seebelow).InthisnotewestudythecasewhenGisaChimeragraphasdescribedin[14].AChimeragraphCk has8k2verticesarrangedinagrid-likepattern:eachnodeinak×kgridgraphisreplacedbypletebipartitegraphK4,4,andthenodesinthe“rightpartition”areconnectedtotherespectivenodesintherightpartitionsoftheK4,4sontheleftandright(iftheyexist),andthenodesinthe“leftpartition”areconnectedtotherespectivenodesintheleftpartitionsoftheK4,4saboveandbelow. McGeoghandWang[14]solverandomlygeneratedQUBOprobleminstanceswheretheconnectivitygraphhasatmost439nodesandisasubgraphoftheChimeragraphC8(ithas512nodes)onaD-Wave Twochip[12][9]paretherunningtimestothetimetakenbytheMIQPalgorithmwithinIBMILOG CPLEX[13](henceforthcalledCPLEX).LettingQ¯=(Q+QT)/2,theproblemin(1)canbewrittenas MinxTQ¯xsubjecttox∈{0,1}n.
(2)
1 WecallthisformulationQUBO-miqp.AnMIQPsolver,suchastheoneinCPLEX,typicallyusesabranchand-boundalgorithm,wherelowerboundsonQUBO-miqpareobtainedbysolvingaquadraticprogramming(QP)relaxationoftheform MinxTQ¯xsubjecttox∈[0,1]n.
(3) IfQ¯isnotpositivesemidefinite,thentheQPproblemaboveisnonconvexandNP-hard.ForQUBOinstances,asimpletransformationmakesQ¯positivesemidefinitewithoutchangingtheoptimalsolution.LetDbean×ndiagonalmatrix.Then n MinxT(Q¯+D)x−Diixisubjecttox∈{0,1}n,
(4) i=
1 isequivalenttoQUBO-miqp.Whenxi={0,1},x2i=xiandthereforeforeveryx∈{0,1}n,theobjectivefunctionin(4)hasthesamevalueastheobjectivefunctionin
(2).TherearemanychoicesofDsuchthatQ¯+Dispositivesemidefinite:e.g.,ifD=λmin(Q¯)Iwhereλmin(Q¯)istheminimumeigenvalueofQ¯andIistheidentitymatrix,orDischosensothatQ¯+Disdiagonallydominant.ThechoiceofDinfluences thequalityofthelowerboundontheoptimalsolutionvalueof(4)fromitsconvexQPrelaxation(obtainedbysettingx∈[0,1]n),see[5]. AnalternativeapproachtosolvingQUBOinstancesisviathefollowingstandardmixed-integerlinearprogramming(MILP)formulation(hereweassume,withoutlossofgenerality,thatQisuppertriangular): Min i1 Qiixi
(5) subjectto zij≤xi ∀i(6) zij≤xj ∀i(7) xi+xj−zij≤
1 ∀i(8) zij≥
0 ∀i(9) x∈{0,1}n. (10) WecallthisformulationQUBO-milp.Foranyfixedi,j,theconstraints
(6)-(9)forcezijtoequalxixjwhenxi,xj∈{0,1},anddefinetheconvexhullof{(xi,xj,xixj):xi,xj∈{0,1}}[11].Itiswell-known(seeresultsbelow)thatQUBO-milpcanbesolvedquicklyforsparsegraphswithlinearprogramming(LP)basedbranch-and-cutalgorithms:LPrelaxationsyieldbounds,andcuttingplanesareusedtostrengthentheLPrelaxationoftheMILPformulation. TheQUBOproblemmaps,viaaone-to-onelineartransformation(andQUBO-milpmapstoanMILPformulation)totheIsingSpinModel(ISM)problemwithicfieldswiththesameconnectivitygraph,ortotheMaxCutproblem[7]onagraphwithoneextranodeconnectedtoallexistingnodes.ISMinstances(orequivalentlyQUBOinstances)on3Dgridgraphswereshowntobeeasytosolve[3]usingLPbinedwithcycleinequalities[2]fortheMaxCutproblem.Thesamebinedwithbranchand-boundwereusedin[4]tosolverandomlygeneratedQUBOinstancesonsparsegraphswith(n=)100nodes(andaveragenodedegree≤.0625n),and–withadditionalcuttingplanes–in[8]tosolveISMinstanceson100×1002Dgridgraphs.In[4],160outof162instancesweresolvedbystrengtheningtheLPrelaxationwithcycleinequalitiesandwithoutbranching;almostallinstancesin[8]weresolvedinthismanner.Itwasshownin[5]thatQUBO-milpinstancesbasedonsparse,randomlygeneratedgraphsGwith
2 n≤80(averagedegreeofanodeis.2norless)canbesolvedveryquicklyevenwithageneralMILPsolver,specificallyCPLEX8.1.Theyuseedgeweightsintherange[−50,50]andnodeweightsintherange[−100,100].DependingonthesignofQij,someinequalitiesfrom
(6)-(9)canbedeleted(see[5]),thoughwedonotdothishere.TheaveragenodedegreeofaChimeragraphisbetween5and6,andmuchlessthantheaveragedegreesconsideredin[5]. Inthisnote,motivatedbytheaboveresultsonsparsegraphs,weruntheCPLEX12.3(sameversionasin[14])MILPsolveronQUBO-milpforrandomlygeneratedQUBOinstancesonChimeragraphs.Weobservethatsuchinstancesaresolvedtooptimality(uptothedefaultoptimalitytolerance)inasmallamountoftime.Ontheaverage,theCPLEXMILPsolvertakeslessthan0.2secondsonastandardMicrosoftWindowswitha2.2GHzIntelCorei7processortosolveinstancesonC8graphswith512nodes.Totesttheincreaseindifficultywithincreasinggraphsize,weexperimentwithinstancesbasedonC20graphswith3200nodes,C35graphswith9800nodes,andC50graphswith20,000nodes,andobtainaveragesolutiontimeslessthan2.4seconds,16.5secondsand51.5seconds,respectively.WeexpectsimilarbehaviourontheMcGeogh-Wanginstances(basedonsubgraphsofC8),asremovingedges/nodesusuallymakesaQUBOinstanceeasiertosolve. Furthermore,forC4graphs,weobservethatsolvingQUBO-miqpviaQP-basedbranchandbound(withCPLEX’sMIQPsolver)takessignificantlymoretimethansolvingQUBO-milpviaLP-basedbranch-andcut(withCPLEX’sMILPsolver).Inotherwords,likeMcGeoghandWang,weobserveputationtimestosolveQUBO-miqp.Intheworstcase,weobservea10,000foldparedwithQUBOmilp,thoughtheaverageslowdownisless;seethenextsectionforapartialexplanation. Inotherwords,itseemsthatChimeragraphbasedQUBOinstancessimilartotheonesstudiedbyMcGeoghandWangareactuallyeasytosolvewithputers,evenformuchlargergraphs. 2Detailsputationalexperiments WegeneratetwogroupsofrandomQUBOinstancesonChimeragraphsCkwithvaryingk.Inthefirstgroup,eachnodeoredgeweightischosenuniformlyatrandomfrom{−1,1}asinMcGeoghandWang;whattheydodifferentlyisthattheychoosesubgraphsoftheChimeragraphC8,whereaswealwaysworkwithpleteChimeragraph.Inthesecondgroup,eachnodeoredgeweightisanintegerchosenuniformlyatrandomfromtheinterval[-100,100].Wegenerate50instancesforeachgroupforC8,C20,C35andC50.TheC8(andC4)instances(asweightedgraphs),CPLEXreadableinputsforQUBO-miqpandQUBO-milp,andcplexoutputandlogsforourtestsontheseinstances(onlyforQUBO-milpforC8)areavailableat/researcher/files/us-sanjeebd/chimera-data.zip. InTable1,wereportrunningtimes.Inthefirstcolumnwespecifythegroupofinstances,inthesecondcolumnwegivethegraph.Inthethirdandfourthcolumns,wegivethenumberofnodesandedges.Inthesixthandseventhcolumns,respectively,wegivethearithmeticmeanandgeometricmeanoftherunningtimesacrossthe50randomlygeneratedinstances.Theremainingcolumnsgivetheminimum,maximumandstandarddeviationoftherunningtimesacrossall50instances.AllinstancesaresolvedwithIBMILOGCPLEX12.3runningonan8-coreWindows7(witha2.2GHzIntelCorei7vProchip).Allrunsareexecutedonasinglecorewithdefaultsettingsandnospecializedcode(suchascutcallbacks).TherunningtimesarethetimesinsecondsreportedbyCPLEX. Thesecondgroupofinstancesseemslightlyeasierthanthefirst.Themaximumtimetosolveanyinstanceis73.6seconds.Allbut6ofthe400instancesinthistablearesolvedwithoutbranchingandthetotalnumberofbranch-and-boundnodesacrossallinstancesis345;theLPrelaxationofQUBO-milpaugmentedwithcuttingplanesisenoughtosolvealmostallinstances,justasin[3],[4]and[8].NowCPLEXdoesnot
3 Group1Group2 GraphC8C20C35C50C8C20C35C50 nodes51232009800 2000051232003200 20000 edges147294402912059600147294402912059600 Mean0.192.38 16.5251.48 0.121.8912.8732.59
G.Mean0.182.33 16.4051.14 0.111.8412.6129.86 Min0.091.0613.1742.960.060.736.3012.79 Max0.393.9024.4673.600.272.5420.4849.58 Std.Dev.0.060.432.116.300.040.382.54 12.47 Table1:RuntimesforQUBOinstancesondifferentgraphsizes generatecycleinequalitiesspecifically;howeveritgenerateszero-halfcuts[10]andGomoryfractionalcuts,whichgeneralizecycleinequalities.Indeed,thesearetheonlytwoclassesofcuttingplanesgeneratedbyCPLEXinourtestsandseemessential.ThefirstgroupofC8instancesareallsolvedwithin6.99secondsandin0.6secondsontheaveragewithpurebranch-and-boundandnocuttingplanes(thesecondgrouptakeslesstime),butlargerinstancesarehardtosolveinthisway. Finally,weparethesolutiontimesforQUBO-miqpandQUBO-milpsolvedwiththerespectivesolversofCPLEX.EvenforinstancesbasedonsmallgraphssuchasC4,thedifferenceintimecanbesignificant.ThemeansolutiontimeforQUBO-milpis0.03seconds,themaximumsolutiontimeis0.09seconds,andthestandarddeviationinsolutiontimesis0.015.ThecorrespondingnumbersforQUBO-miqpare36.62seconds,1355.85seconds,and195.33.Therefore,intheworstcase,therunningtimeforQUBOmiqpisover10,000timestherunningtimeforQUBO-milp(qchim4.12.lpversuschim4.12.lpinourdataset,availableatthelinkabove). Whydoesthishappen?
Webelieveitismorebecauseofformulationdifferencesratherthandifferencesinsolverquality(thoughCPLEX-MILPismuchmoremature,givenitsrelativeimportanceforpracticalapplications).Firstly,eventhoughtheQPrelaxationofQUBO-miqpisstrongerthantheLPrelaxationofQUBO-milp,aftermodifyingQ¯asin(4)tomakeitpositivesemidefinite,theassociatedconvexQPrelaxationyieldsnontriviallyworselowerboundsformanyofourinstances.Secondly,QUBO-milpisanextendedformulationwithextravariables(representingxixj).Onecanderivenewlinearconstraints(e.g.,cycleinequalities)togetabetterapproximationofconv(xxT:x∈{0,1}n)thanconv(xxT:x∈[0,1]n).ThisisnotpossibleinQUBO-miqp.Thatsaid,QUBO-miqpmaybemuchbetterfordensegraphs[5]. AcknowledgementsWewouldliketothankFranciscoBarahonaforhelpfuldiscussionsonsolutiontechniquesforsparseQUBOinstances. References [1]
F.Barahona,OnplexityofIsingspinglassmodels,JournalofPhysicsA:MathematicalandGeneral15(10)3241–3253(1982). [2]
F.Barahona,
A.R.Mahjoub,Onthecute,MathematicalProgramming36157-173(1986). [3]
F.Barahona,E.ioni,Ontheexactgroundstatesofthree-dimensionalIsingspinglasses,JournalofPhysicsA:MathematicalandGeneral15,611–615(1982).
4 [4]
F.Barahona,
M.Ju¨nger,
G.Reinelt,Experimentsinquadratic01programming,MathematicalProgramming44,127–137(1989). [5]A.andS.Elloumi,Usingamixedintegerquadraticprogrammingsolverfortheunconstrainedquadratic0-1problem,MathematicalProgramming109,55–68(2007). [6]
E.Boros,
P.HammerandG.Tavares,Localsearchheuristicsforquadraticunconstrainedbinaryoptimization(QUBO),JournalofHeuristics13,99–132(2007). [7]
C.DeSimone,ThecuteandtheBooleanquadriceDiscreteMathematics79
(1),71-75(1990). [8]
C.DeSimone,
M.Diehl,
M.Ju¨nger,
P.Mutzel,
G.Reinelt,andG.Rinaldi,ExactgroundstatesofIsingspinglasses:Newexperimentalresultswithabranch-and-cutalgorithmJournalofStatisticalPhysics80(1-2),487–496(1995). [9]D-WaveSystemsInc.,4401StillCreekDrive,Burnaby,BritishColumbia,CanadaV5C6G9[10]
A.CapraraandM.Fischetti,0,1/2-Chvtal-Gomorycuts,MathematicalProgramming74,221–235 (1996).[11]
R.Fortet,Applicationsdel’algebredeBooleenrechercheope´rationelle.RevueFranc¸aisede RechercheOpe´rationelle4(14),17–26(1960).[12]
R.Harris,
M.W.Johnson,
T.Lanting,
A.J.Berkley,
J.Johanson,
P.Bunyk,
E.Tolkacheva,
E.Ladizin- sky,
N.Ladizinsky,
T.Oh,et.al.,Experimentalinvestigationofaneight-qubitunitcellinasuperconductingoptimizationprocessor,Phys.Rev.B82024511(2010).[13]IBMILOGCPLEXOptimizer,merce/optimization/cplex-optimizer[14]
C.C.McGeochandC.Wang,ExperimentalEvaluationofanadiabaticquantumsystembinatorialoptimization,Proceedingsofthe2013ACMConferenceonComputingFrontiers2013,Ischia,Italy.
5