资源描述：
《2005 Convex Quadratic Programming for Exact Solution of 0-1 Quadratic Programs》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ConvexQuadraticProgrammingforExactSolutionof0-1QuadraticProgramsAlainBillionnet1,SourourElloumi2,Marie-ChristinePlateau310thJune20051LaboratoireCEDRIC,Institutd'Informatiqued'Entreprise,18alleeJeanRostand,F-91025Evrybillionnet@iie.cnam.fr2LaboratoireCEDRIC,ConservatoireNationa
2、ldesArtsetMetiers,292rueSaintMartin,F-75141Pariselloumi@cnam.fr3LaboratoireCEDRIC,ConservatoireNationaldesArtsetMetiers,292rueSaintMartin,F-75141Parismc.plateau@cnam.frAbstractLet(QP)bea0-1quadraticprogramwhichconsistsinminimizingaquadraticfunctionsubjecttolinearconstraints.I
3、nthispaper,wepresentageneralmethodtosolve(QP)byreformulationoftheproblemintoanequivalent0-1programwithaconvexquadraticobjectivefunction,followedbytheuseofastandardmixedintegerquadraticprogrammingsolver.Ourconvexi cationmethod,whichisthebestinacertainsense,usestheequalityconstra
4、intsof(QP)andrequiresthesolutionofasemide niteprogram.Weapplyittothedensestk-subgraphproblemandreportexperimentalresultsshowingthat,forthisgraphproblem,theapproachoutperformsexistingmethods.Keyword:Quadratic0-1programming,Convexquadraticprogramming,semide niteprogramming,denses
5、tk-subgraph,Experiments.11IntroductionConsiderthefollowinglinearly-constrainedzero-onequadraticprogram:tt00n(QP):Ming(x)=xQx+cx:Ax=b;Axb;x2f0;1gwherecisannrealvector,bisanmrealvector,b0isaprealvector,Qisasymmetricnnrealmatrix,AisanmnmatrixandA0isapnmatrix.Withoutlossofgene
6、rality,weassumethatalldiagonaltermsofQareequalto0.Quadraticzero-oneprogrammingwithlinearconstraintsisageneralmodelthatallowstoformulatenumerousimportantproblemsincombina-torialoptimizationincluding,forexample:quadraticassignment,graphpartitioning,taskallocation,capitalbudgeting
7、anddensestk-subgraph.Variousheuristicsandexactmethodshavebeenproposedtosolve(QP).Duetothenon-convexityoftheobjectivefunction,(QP)isoftenreformu-latedbeforesearchingforitsoptimalsolution.So,severalmethodshavebeendevelopedtosolveitexactlythrough0-1linearreformulations(see,forexam
8、ple,[2],[3],[13],[15],[30])or0-1convexquadraticreformu
