linear equations with binary variables - Stack Overflow

Are you sure your problem is not a binary integer programming? If you just want to solve this in-equation with such small amount of ... OnlydayslefttoRSVP!JoinusSept28atourinauguralconference,everyoneiswelcome. Home Public Questions Tags Users Companies Collectives ExploreCollectives Teams StackOverflowforTeams –Startcollaboratingandsharingorganizationalknowledge. CreateafreeTeam WhyTeams? Teams CreatefreeTeam Collectives™onStackOverflow Findcentralized,trustedcontentandcollaboratearoundthetechnologiesyouusemost. LearnmoreaboutCollectives Teams Q&Aforwork Connectandshareknowledgewithinasinglelocationthatisstructuredandeasytosearch. LearnmoreaboutTeams linearequationswithbinaryvariables AskQuestion Asked 8years,9monthsago Modified 8years,9monthsago Viewed 3ktimes 0 IhavetheseequationsandIwanttofindonesolutionforthem 0<=x1+x2+x3+x4+x5+x6<=3 0<=x7+x8<=2 2<=x1+x2+x3+x4<=4 2<=x3+x4+x5<=3 2<=x6+x7+x8<=3 thevaluesofxiis0or1(xiisbinaryvariable) isthereanyalgorithmforsolvingthiskindofequationandsimilarones matlablinear-algebralinear-programming Share Improvethisquestion Follow askedDec7,2013at22:31 user1514730user1514730 6111silverbadge66bronzebadges 1 1 Yourquestionisverysimilartoyourfirstquestion:stackoverflow.com/questions/20443517/… – Daniel Dec8,2013at2:11 Addacomment  |  2Answers 2 Sortedby: Resettodefault Highestscore(default) Trending(recentvotescountmore) Datemodified(newestfirst) Datecreated(oldestfirst) 4 Areyousureyourproblemisnotabinaryintegerprogramming? Ifyoujustwanttosolvethisin-equationwithsuchsmallamountofvariables,brute-forcesearchmayjustwork....Construct2^88*1vectors,andverifyifeveryvectorsatisfyyourin-equation(youcanwriteyourequationinmatrixformforsure). IfyoujustwantONEsolution....youcanevendoitbyhand:10101011 Butthegeneralsolutionisnoteasy.Checkthispost.Tosolvethebinaryintegerlinearequationinpolynomialtime,thereisonepaperthatyoumaytakesometimedigging. EDIT:updatefrom@BenVoigt branch-and-boundistypicallyeffectiveforefficientlysolving(large)integer(incl.binary)andmixed-integerproblems.Ofcoursethisproblemistoosmalltobeworththeoverhead--exhaustivesearchisquiteadequate. Share Improvethisanswer Follow editedApr13,2017at12:57 CommunityBot 111silverbadge answeredDec7,2013at23:02 lennon310lennon310 12.2k1111goldbadges4141silverbadges6060bronzebadges 6 thanksforyourhelp..Iamsearchingforpolynomialalgorithmforsolvingthisproblem. – user1514730 Dec7,2013at23:08 updateonepublicationforyou,thepseudo-codeisincludedinthepaper,butittakestimetounderstandtheprinciple. – lennon310 Dec7,2013at23:24 thereisspecialforminmyproblem,firstthematrixAistotallyunimodularandalsothevariableineachequationareneighbours,maybethismaketheproblemeasertosolve. – user1514730 Dec7,2013at23:47 Yoursolutiondoesnotsatisfy2<=x6+x7+x8 – Daniel Dec8,2013at1:48 1 branch-and-boundistypicallyeffectiveforefficientlysolving(large)integer(incl.binary)andmixed-integerproblems.Ofcoursethisproblemistoosmalltobeworththeoverhead--exhaustivesearchisquiteadequate.(Thoughlennon,youmaywanttousethecorrecttherm,eitherexhaustiveorbruteforceratherthanbrutal) – BenVoigt Dec8,2013at1:55  |  Show1morecomment 1 Regardlessofthealgorithmyoumayuse,Iwoulddosomepreprocessingtoreducethecomplexity.Thesumofbinaryvariablesisalways>=0: x1+x2+x3+x4+x5+x6<=3 x7+x8<=2 2<=x1+x2+x3+x4<=4 2<=x3+x4+x5<=3 2<=x6+x7+x8<=3 Thesumofbinaryvariablesisalways<=numofvariables: x1+x2+x3+x4+x5+x6<=3 2<=x1+x2+x3+x4 2<=x3+x4+x5 2<=x6+x7+x8 Share Improvethisanswer Follow editedDec8,2013at2:56 answeredDec8,2013at1:46 DanielDaniel 36.4k33goldbadges3434silverbadges6767bronzebadges Addacomment  |  YourAnswer ThanksforcontributingananswertoStackOverflow!Pleasebesuretoanswerthequestion.Providedetailsandshareyourresearch!Butavoid…Askingforhelp,clarification,orrespondingtootheranswers.Makingstatementsbasedonopinion;backthemupwithreferencesorpersonalexperience.Tolearnmore,seeourtipsonwritinggreatanswers. Draftsaved Draftdiscarded Signuporlogin SignupusingGoogle SignupusingFacebook SignupusingEmailandPassword Submit Postasaguest Name Email Required,butnevershown PostYourAnswer Discard Byclicking“PostYourAnswer”,youagreetoourtermsofservice,privacypolicyandcookiepolicy Nottheansweryou'relookingfor?Browseotherquestionstaggedmatlablinear-algebralinear-programmingoraskyourownquestion. TheOverflowBlog Fiveninesuptimewithoutdeveloperburnout(Ep.488) WehateScrumandAgile…whenit’sdonewrong(Ep.489) FeaturedonMeta RecentColorContrastChangesandAccessibilityUpdates Revieweroverboard!Orarequesttoimprovetheonboardingguidancefornew... ShouldIexplainotherpeople'scode-onlyanswers? Linked 1 Totallyunimodularmatrixwithbinaryvariable Related 389 HowcanIindexaMATLABarrayreturnedbyafunctionwithoutfirstassigningittoalocalvariable? 0 3NlinearEquations 1 Findingequalvariablesinnonsolvablemulti-variableslinearequations 0 SolvinglinearequationswithoneunknownwithPython 0 SolvetwoequationsofLinearInequalityinvolvingthreedifferentvariablesthroughcode 0 Constrainingthesolutionsforlinearequations 0 MinimizingasystemoflinearequationswithlimitedvariablesinOctave 0 Needtowriteasetoflinearequationsforfollowingcondition: HotNetworkQuestions IsthereasomewhatrealisticFOSSflightsimulatorforLinux? Unusualwordstodenoteaspecificlengthoftime?Likefortnightbutfordifferentamountsoftime Advantagesofalawlicenseotherthantheabilitytopracticelaw Whatisthestatusofsongsthatglorifyillegalactivityindifferentcountries? PROMPT_COMMANDoutputinshellscriptusingpipingLINUX Whyissendingtroopsdifferentfromsendingmilitaryequipment? CanIgetalatepaymentonmycreditcardifapris0%forthefirst21months? Whydolawyerswritecontractswithlanguagethatismoredifficulttounderstandthanotherworks? inRhowdoyoudetermineifthereisasignificantrelationshipbetweentwovariableswithseveralfactorsaffectingit? Differencebetween"unreal"and"notreal" TravelonlastdayofSchengenvisa Howtoplayasadual-wieldingmonk? Whenacorkispulledoutofawinebottle,whydoestheinnerendoftenexpandmorethantheouterend? Howisaphrasepatternsubdividedandmeasured? Emailaddressesgivinginternetconnection Howtopreventhumansfrombeingkilledbyaliendiseases? PrinteveryFool'sMate Whatdoyoucallitwhenyouaresayingsomethingpalpablyuntrueonpurpose? Whatexactlydidthe"UNFORMAT"MS-DOScommanddo? AsaPhDstudentintheoreticalphysics,whatfractionofmytime(ifany)shouldIspendonbackgroundmaterialratherthanmyresearchproblem? PricingabonddenominatedinUSDbutissuedinEurope InwhichtournamentdidKarpovplayhisfirstmovewithwhitepiecesandofferadraw? HowhardisittofindajobintheacademiawithaMuslimnameintheUK? WhichrunwayshouldIuse,andhowcanIrecogniseitinfurtherflights? morehotquestions Questionfeed SubscribetoRSS Questionfeed TosubscribetothisRSSfeed,copyandpastethisURLintoyourRSSreader. lang-matlab Yourprivacy Byclicking“Acceptallcookies”,youagreeStackExchangecanstorecookiesonyourdeviceanddiscloseinformationinaccordancewithourCookiePolicy. Acceptallcookies Customizesettings