简介：Inthispaper,theapproximationforfourkindsofknapsackproblemswithmultipleconstraintsisstudied:0/1MultipleConstraintKnapsackProblem(0/1MCKP),IntegerMultipleConstraintKnapsackProblem(IntegerMCKP),0/1k-ConstraintKnapsackProblem(0/1k-CKP)andIntegerk-ConstraintKnapsackProblem(Integerk-CKP).Thefollowingresultsareobtained:1)UnlessNP=co-R,nopolynomialtimealgorithmapproximates0/1MCKPorIntegerMCKPwithinafactrok^(1/2)-σforanyσ>0;unlessNP=P,nopolynomialtimealgorithmapproximates0/1MCKPorInterMCKPwithinafactork^(1/4)^-σforanyσ>0wherekstandsforthenumberofconstraints.2)Foranyfixedpositiveintegerk,0/1k-CKPhasafullypolynomialtimeapproximationscheme(FPTAS).3)Foranyfixedpositiveintegerk,Integerk-CKPhasafastFPTASwhichhastimecomplexityO(n+1/ε^3+1/ε^3k+1-2)andspacecomplexityO(n+(1/ε^3)),andfindsanapproximatesolutiontowithinεoftheoptimalsolution.

简介：InthispaperwestudythesolutionofSATproblemsformulatedasdiscretedecisionanddiscreteconstrainedoptimizationproblems.Constrainedformulationsarebetterthantraditionalunconstrainedformulationsbecauseviolatedconstraintsmayprovideadditionalforcestoleadasearchtowardsasatisfiableassignment.Wesummarizethetheoryofextendedsaddlepointsinpenaltyformulationsforsolvingdiscreteconstrainedoptimizationproblemsandtheassociateddiscretepenaltymethod(DPM).Wethenexaminevariousformulationsoftheobjectivefunction,choicesofneighborhoodinDPM,strategiesforupdatingpenalties,andheuristicsforavoidingtraps.ExperimentalevaluationsonhardbenchmarkinstancespinpointthattrapscontributesignificantlytotheinefficiencyofDPMandforceatrajectorytorepeatedlyvisitthesamesetofornearbypointsintheoriginalvariablespace.Toaddressthisissue,weproposeandstudytwotrap-avoidancestrategies.Thefirststrategyaddsextrapenaltiesonunsatisfiedclausesinsideatrap,leadingtoverylargepenaltiesforunsatisfiedclausesthataretrappedmoreoftenandmakingtheseclausesmorelikelytobesatisfiedinthefuture.Thesecondstrategystoresinformationonpointsvisitedbefore,whetherinsidetrapsornot,andavoidsvisitingpointsthatareclosetopointsvisitedbefore.Itcanbeimplementedbymodifyingthepenaltyfunctioninsuchawaythat,ifatrajectorygetsclosetopointsvisitedbefore,anextrapenaltywilltakeeffectandforcethetrajectorytoanewregion.Itspecializestothefirststrategybecausetrapsarespecialcasesofpointsvisitedbefore.Finally,weshowexperimentalresultsonevaluatingbenchmarksintheDIMACSandSATLIBarchivesandcompareourresultswithexistingresultsonGSAT,WalkSAT,LSDL,andGrasp.TheresultsdemonstratethatDPMwithtrapavoidanceisrobustaswellaseffectiveforsolvinghardSATproblems.