2002年日本オペレーションズ・リサーチ学会 秋季研究発表会 1−C−9
整数計画問題に対するtestsetの計算にづいて
ComputingtestsetsforintegerprogrammlngprOblems
東京理科大学＊伊藤雅史ITOMa・Safumi
東京理科大学 平林隆一 HIRABAYASHIRyuichi
0）＝（0）1101ds・ DefinitioIl・ThesetT⊂Z−1＼（0）iscalledat・eSt・ Set・forIP＾，C（b）ifit・SatisRes： （i）Ifαisf占asibleand no11−Optimaltllellt・here exists u ∈ T such that．α−uis ftasible all（1C・α＞c・（α一視），
（ii）Ifβis a・n Optil−1a・1solutiollt・11ellβ−tLi＄ infea5iblefora11tL∈T．
Now we explain the C−T a・lgorithm fbr
IP＾，C（b）・CollSiderthepolyl10mialri11gk［l，y］：＝ 叩1，…，fd，yl，…， Satisfyingt・11atalltermswit・htiarelargert・llall trhatcontainonlyyj・Further血ore，＞cisa■t・erl−1 0rdersatisfyillgC・α＞c・β⇒yCr＞cyP．Illtlle C−Talgorithm，WehavetocolllPuteaGr6bller basisGofanideal（F〉⊂k［t，y］w．7、．t・aterll1 0rderwitllPrOpertiesof＞（√＞y，）alld＞c・Anopti− malsolutioncallbeobt，ainedfrollltherelllai11der
ofl！1‥．i慧ddividedbyG．
Itiseasytoseet・hattheGr6bllerbasisGsat−
isfiestheconditiolisoftest，Set．S．ThecruCialfact isthatGisasubsetof（xu−rt’：AtE＝．4t，）． Thomas alld Weismalltelproved t・hat・the setbG：＝（∬t‘−∬l′ ∈G：ムーtl∈CN（j））
also s？tis危es tlle COnditiol10ftest set．s，Where
CN（A）：＝iAtL：tL∈Fqn）．ThisbGiscalled o b−Gr∂b一一erbasisfbrlP＾，C（b）［5］・Ourobject・ive istoconstruCtanalgorithmtocomputebG．
1I11trOduction
Gr∂bIlerbases，int・rOduced by Buchbergeril−
165【2】，a・rebasesofidealsontllepOlynomia・1
rlng al−d they haveplayedimporta・nt・rOlesill
commutativealgebraandalgebra・icgeomet・ry・In
，91，Colltia・ndTraversoproposedanalgorit・hm
（t・lle C−Taわorithm）tbrilltegerprOgrammi11gS
（IP）tlSillgGr6bnerbases・Gr6bnerba5eSand
theC−Talgorit・hmaresa・idtobeverypowerful
tooIstoanalyseIPfromtheviewpointofcom−
mutat．ivealgebra［5】．011tlleOtherhalld，teSt
setsfbrIPareintroducedbyGraverin1975・In
1995，TllOma5prObedthat・Gr6bllerbasesused
illC−Ta・1gorithmsatisfiestheconditionsoft・eSt
sets．However，Gr6bnerbasesinC−Talgorithm
colltains alotofu11neCeSSary element・Singell−
eral．In1997，Thomasal−dWeismanteldeAned
truncated Gr6bnerbases，inwhichunnecessary
elementsareexclude．Tlleyalsoproposedanal−
gorithmt10COmputethem，butitisbasedonthe
BtLChbe7Veralgorithmwhichisknownastheex−
tremelytime−COnSumlrlgPrOCedure・Inthispar
per，WeprOpOSealla・nOtheralgoritlm一tOCOm−
pute test・SetS，based oh the basis coT”erSion
ね亡んni91Jeβ．
2 Tbst setsforIP
Ba5icde負nit．ionsofGr6bllerbasesarein［1］・
West．udyIPoftheformIP＾，C（b）＝lnin（c・X：
力＝b，エ∈f≒㍗り，WhereA＝【叫〕∈Ndxn，
b∈F寸d，alldc∈Rn．Weassume（3≧0：Ax＝
3 OurAlgorithln
Itconsist．s orP朋∫gJalld f）〟A∫gg．
In genera・l，thellumber of variablesis de−
ー50−
basedontheBuchbergera190rithm・［1］byaddi11g t・he eccltLSion testnot・tOgenerat・e ullneCeSSa・ry elemellt・SfbrIPA，e（b）・Genera・11y，t・heexclusiol− t・eStisl10tPraCticalbeca・uSe theexclusiollteStl requirestosoIveIPsoftheformIP＾，b（P）・But inouralgorithm，thistestcallbedollequiteea・S→
ilybydividingtfl．．．t3dbyF．
sired to be smallfor Gr6bner ba5eS COmputa−
t・ions．Hence trhegoa・lofPHASElistoelimi−
natethevaria・blesil，．．．，id丘om〈F〉，thatare
ull11eCeSSaryinbG．Itca・nbedonebyuslnga11 elimination property ofGr6lmer bases of（F〉 W・r・t・＞（t＞y）・Wefbcusourattention tothe fact that Fis already a・Gr6lmer basis w．r．t．
an undesired order＞×．The change oforder− 1ngOfGr6bnerbasesfroIn＞×tO＞（t＞y）Canbe donebytheGr∂blM、Walk［3］，butitisnotfast
enoughaccordingtoourcomputationalresult・
Ourprocedure，Cal1edastheb−FGLM，COmputeSil∈k［l，y］，WhichisaSubsetofaGr6lmerba−
sisof〈F〉w・r・t・＞（t，y）・fkeepsanelimina−
tionpropertydfGr6bnerbases，andhasa・nad−dit，ionalpropertythatB：＝fnk［y］isabasis
oftheIinear space on k spanned by bG．The
procedureisbasedontheFGLMalgorithm［4］， whichis aGr6bnerbasesconversion algorithm
fbrO−dimensionalideals，andsa・idtobeveryfhst Whellhalldlingbinol11ialideals・IllOurCaSe，〈F〉 is a bi110mialideal，but ullfortunately，nOt O−
dil11ellSioIlal．Tlledifhcultyisthat FGLMdoes notterminatewhenidealsarel10tO−dimensio11al． WeovercomethisdifBcultybymakinguseoftlle nlultivariategradingonk［t，y］de負nedin【5】，and ensureitstLerminationbythe負nitenessofftasi− blesolutionsofIPJl．c（b）・ In PHASE2，BisconvertedintobGbyour
procedure called b−G7、6bner WaLk．The maill Strategyis similart・O the orlglnal．We de負ne the b＿Gr∂bne†、COnefor each term orderillthe SameWaytOthede飢IitionoftheGr6bnercone． Moreover，thedepwttJ柁IL，oissetto（1，0，…，0）． By tra・Clng thelinesegment丘om u・o tO C，We
can爺mdabounda・ryWlOfthecurrentb−Gr6bner
cone．Then we transform Binto a basis w．r．t．
thetermorderofthenextGr6bnerconebythe
loca・1collVerSionprocedure，andtraceagai11fiom t（・ltO C．R・epeat this operat・ion untiltheline SegmenttLlitOCisintlleSameb−Gr6bnercone．
Illthelocalconversion，We have to apply the
b−BtJChbelyeraLgorithmintroducedin［5］・Itis
4 Conclusion
Wecombined the theory ofb−Gr6bller bases
Withthebasesconversio11teChllique．Ouralgo− ritlmlWi11helpustoallalyzelargersizeofIPs andrelatedproblemsalgebraically．
参考文献
［1］W．W．AdamsalldP．Lousta・ulla．u．ATIIntTV− ducfわnfoG†、∂ふne†、β85ピβ，Vol．30rC用d…′ビ SttJdiesiIIMalhemalics．America．11Matlle− matica・lSociety，2ndeditioll，1996． 【2】B・Buchberger．Anaborithm・Jbrindin9a 払βiβル†、加代βiduビぐねβ＝、i叩げdニビ和一 dimen封0胴J匹Jynom・血＝流血．PhD thesis， Math・I11St．UniversityofIll11SbruCk，Austria・， 1965．in Germall． t3］S．Co11art，M．Kalkbreller，alldD．Mal1．Con− Vert・ingbaseswiththeGr6bnerwalk．JoILrllal 〆萌仰山厄C川甲血玩Il，Vol．24，pp．465− 469，1997． 【4】J・C．Faugむe，P．Gianni，D．Lazard，a・ndT・Mora．E篤cient computation of zero−
dimensionalgr6bllCrbasesbychallgeOfor−
dering・JotLmalqFSymbolic ComptLtatio17， Wl．16，pp．329−344，1993．
【5］R．R．Thollla5and R．．WeislllallteI．TruJl−
Cated gr6bner basesforinteger progral−l− 1nlng・A押J血抽A匂eふ和inβn如nf汀如タ，
Com・”lt…iぐ8fiondIld（わmptJfi叩，No．8，pl）．
24ト257，1997．
−51−
