tr-2006-106

HowtosuccessivelyaddressProfessionalMarkets

throughtheOfficeworldMSR-TR-2006-106

YoussefHamadiandLucasBordeaux

MicrosoftResearchLtd.,

7JJThomsonAvenueCambridgeCB30FB,

UnitedKingdom,

{youssefh,lucasb}@microsoft.com

24thJuly2006

Abstract

ThisworkshowshowExcelcanbeleveragedtotackleconfigurationproblems.WedemonstratethisbypresentingthefulldevelopmentcycleofaPC-configuratorprototype.Wearticulateourdemonstrationbyexemplifyingseveralimportantpoints.First,thatExcelcanbeusedtoimportrawproductsandservicesdata.Second,thatthesedatacanbeusedbyaConstraintsconfigurationmodellingtocorrectlyinstantiateasetofconfigurationrules.Third,thatanyupdatetothedatalikeadditionofnewcomponentscanbeperformedwithoutalteringthemodelling.Fourth,thatdedicatedExcelGUIscanbeusedforinteractiveproductandser-viceconfiguration.Finally,weclaimthattheproposedextensionwouldbecomeanimblewaytosuccessfullyaddressprofessionalmarkets(B2B,B2C).Indeed,thepervasivenatureoftheOfficesuitewouldmakeanyOffice-basedBusinessSolutionwidelyadoptedbyalargebasisofOfficecustomers.

Keywords:Excel,Office,Configurationproblems,B2B/B2C

1Introduction

Productconfiguratorsarehelpingsalespersonsandpartnerstosuccessfullymatchcus-tomers’requirementstouniqueproductsandserviceofferings.Thesetoolsarecriti-calsincetheygreatlyreducethecomplexityandthereforeimproveproductivity.Wecandistinguishbetweenseveralconfigurationproblemclasses:ship-to-order(STO),assemble-to-order(ATO),engineer-to-order(ETO),andInternetPricingandConfigu-ration(IPC).

STOproductshavelittlevariabilityotherthanapredeterminedsetofattributes,suchascolorandsize.Someofficeequipment,householdappliancesandtelevisions

1

fallintothisclassification.ATOproductsareconfigurableofferingsmadeupofstan-dardcomponents.Theyareconfiguredbasedoncustomerneedsandintercomponentattributerelationships(suchascompatibility).Computersandtelecommunicationsequipmentfallintothisclassification.ETOproductshavethesamefeaturesasATOproducts,butinvolvesomelevelofengineeringanalysistobeconfigured.Finally,non-productbasedconfigurationlikeIPCenablessellingchannelstodeploycustomizedtradepromotionsandimplementcomplexpricinganddiscountingstrategies[Des06].

Inordertobesuccessful,product/serviceconfigurationmustrelyonamodelthatenablesuserstoefficientlyentertheirneeds,integrateswithotherentreprisesystems,andgeneratesoutputssuchasalineiteminaquotationorabillofmaterialformanu-facturingprocesses.Technically,thismodelisusedbyanautomatedtoollikeaCon-straintSolverwhosealgorithmsareusedtoperformproactiveconsistencycheckofthemodellingwithrespecttotheselectanddeselectactionsperformedbyend-users.Moreoverthesealgorithmscanalsoautomatically“finish”anorderbycompletingre-mainingchoiceatanytimeduringtheinteraction.Whencostorqualitydataareavail-able,optimizationalgorithmscanautomaticallyperformthechoiceswhichminimizesomeclearlydefinedcostfunctione.g.,componentswithcheapestoverallcostinATO,percentagechoicewhichminimizesdurationoffinancingplansinIPC,etc.

Inthispaper,weclaimthatMicrosoftExcelhasalltherequiredflexibilitytoim-plementefficientconfigurators.Tosupportthisclaimwearegoingtodemonstratevariouspoints.ThemostcriticalbeingtheprogrammaticintegrationofaConstraintSolverwithinExcel.Herethegoalistodemonstratethatconstraintmodellingcanef-fectivelybeperformedwithoutviolatingExcel’sprogrammaticmodel.WealsoneedtoshowthatrawbusinessdatawhichcharacterizeproductsandservicescaneasilybeintegratedandaddressedbyExcel’sConstraintsmodelling.Finally,wemustshowthatclassicalinteractiveconfigurationispossiblethroughExcelGUIs.

Moreover,wearguethataddingsuchConfigurationcapabilitytoanOfficeproductwouldhaveagreatimpactonMicrosoftstrategy.Indeed,itwouldallowthecompanytofightbigcompetitors(Oracle,SAP,Siebel,etc)withitsgreatestassets:alargebasisofpre-installedOfficesystems.

Thepaperisarticulatedasfollow:Section2.1overviewsthefunctionalitiesweproposetoaddtoExcel;thecoreofthepaperisthepresentationofanexampleofconfigurationproblemmodelledandsolvedusingtheenhancedsoftware(Section2);wethendiscusstheproposalandconcludeinSection3.

2SolvingConfigurationProblemsinExcel

2.1

AddingaConstraintProgrammingEngine

WebrieflydescribeanumberoffunctionalitieswhichweproposetoaddtoExcel.ThebasicideaistouseMSRC’sConstraintSolver1,Disolvertoenforceconfigurationrules

solversshouldnotbeconfusedwithlinearprogramming(LP)solverssuchastheonewhich

isreadilyavailableinExcel;thetoolssharesimilaritiesbutconstraintprogrammingdealswithmoregeneraltypesofconstraints,suchasBooleanconstraints,whichcannotbeexpressednaturallyinLPandareneededtomodelbusinessrules(seeSection2.2.2).

1Constraint

2

[Ham03].PresentingDisolverandtheConstraintProgrammingtechnologyingeneralgoesbeyondthescopeofthispaper;tounderstandtheproposal,allthereaderneedstoknowisthatthefollowingfunctionalitiesareprovidedbyDisolver,andthattheirintegrationinExcelisessentiallyamatterofwrappingthemasnewExcelfunctions:

•Basicfunctionsforthecreationofdecisionvariables.Adecisionvariablerep-resentsanunknownquantityrangingoverafinitenumberofvalues.InExcel,adecisionvariablewillbeattachedtoacell;theadd-onweneedissimplyanewfunctionwhichspecifiesthatthecontentofthecellisthevalueofacon-straintprogrammingdecisionvariablewithagivenrange.Forinstance,acellcontainingthedefinition=CPVar(\"X\C1:C10)willcorrespondtoavari-able,whoseinternalnameis“X”and,whosevaluecanbeanyofthevaluescontainedinthespecifiedrangeofExcel’scells.•Basicfunctionsforthecreationofconstraintsonthesevariables.Aconstraintisarelationimposedonsomeofthedecisionvariables.Itiscontainedbyacellandrelatestoanumberofvariablesorconstraintscells.Itstruthvalue(i.e.,whetheritissatisiedornot)givesthevalueofitscellandcanbereusedbyotherfunctions.ThedifferencewithaclassicalExcelfunctionhowever,isthattheconstraintcanbeimposed,i.e.wecanaskthesolvertoensurethatitalwaysevaluatestotrue.Naturally,Disolver’salgorithmswillthenneedtofindsatisfactoryvaluesforthevariablesrelatedbytheconstraint.Inaconfigurationapplication,theconstraintswillbeusedtospecifythebusinessrulesoftheapplication.

Aswecansee,wecanaddthebasicbuildingblocksofConstraintProgrammingwithoutviolatingExcel’sprogrammaticmodel.Indeed,decisionvariablesandcon-straintsoperateincellsandusecellsasinput.Moreover,theyreturnvaluesandcanthereforebemixedconsistentlywithclassicalExcel’sfunctionsandalgorithms.Thesefunctionalitiesareillustratedinmoredetailsinthenextpart.

2.2DevelopmentCycleofaTypicalApplication

OurgoalinthissectionistoshowthatExcel,extendedwiththepreviousfunctionali-ties,wouldbecomeapowerfultoolformodellingandsolvingconfigurationproblems.Fortheeaseofpresentation,weconsideraclassical“PCConfiguration”benchmarkwidelyusedintheresearchcommunity[Cli],andwhichfallsundertheATOclass.Asitsnamesuggests,thisproblemconcernstheconfigurationofPCswhichcanbebuiltusingseveraltypesofprocessors,motherboards,graphiccardsandothercomponents.Somecomponentsareincompatible,forinstanceamotherboardoftype“AbitBX6ATX”iscompatiblewitha“Slot1”CPUslotbutnotwithothertypesofCPUs,etc.Thegoalistofindaconfigurationwhichiscompatiblewiththedesiderataoftheuser.Theapplicationhelpsintwotransparentways:(1)whentheuserimposesachoiceforaparticularcomponent,orforbidssomevaluesforthiscomponent,thechoicesforothercomponentswhichbecomeincompatibleareautomaticallydiscarded;thisisthepropagationmode;(2)whentheuserhasspecifiedallherdesiderata,shecanclicka“solve”buttonandtheapplicationwillautomaticallyproposeherwithafully-specified

3

solutionsatisfyingherrequirements(forinstance,iftheuserdidnotspecifyanypref-erenceregardingthebuscomponent,theapplicationwillfill-inthecorrespondingcellwithavalueconsistentwiththeotherchoices);thisistheresolutionmode.2.2.1

DataIntegration

Anefficientconfiguratormustprovideaneasywaytointegratenewdatasuchasnewproductcomponentswhichshouldbeenteredwithoutalteringtheconfigurationmod-ellingandthepresentationlayerparts.

Excelcaneasilyintegraterawdataandpresenttheminacolumn-basedform.Thisisexemplifiedinfigure1whichpresentsrawdataforsomePC-configuratorapplica-tion.Eachcolumnistaggedwiththenameofthecomponentandpopulatedwiththeavailableparts.2.2.2

ConfigurationModelling

InConstraintProgramming,modellinginvolvesthedefinitionofconstraintsrestrictingthepossiblecombinationsofthevariablesofaproblem.ThereforeweneedtoshowthatwecaneasilyexpressCPvariablesinExcelandeasilyrestricttheirrangethroughconstraints.

DecisionvariablesAdiscretedecisionvariablerepresentsasetofalternativechoiceswhichwillbeeventuallyprunedthroughconstraintpropagationand/orend-usersde-cisions.Forinstanceavariablecanrepresentthemother-boardcomponentanditsdomaincanbemadeofpotentialchoices,{AopenAK-72133ATX,AsusK7MATX,Mi-crostar6167ATX,etc.}.Thisrangedirectlyaddressesthedataintegrationworksheetoffigure1.Forexample,

=CP_Var(\"MotherboardI\components’!H:H)

definesavariablecalled“MotherBoard”(thisisjustaninternalnameusefulfordataoutput)andpopulatesitsdomainwithcomponentsdatalocatedinH:H.HerewecanremarkthattheintegrationofnewmotherboardcomponentscanbemadewithoutalteringthemodellingsincetheadditionofnewdatainH:Hwillbeseamlesslyreportedintherelatedvariabledomain.

ThisvariableandallthedecisionvariablesofthePCconfiguratorbenchmarkaredefinedintheVariablessectionoftheworksheetpresentedinfigure2.

Sinceavariableisrepresentedasafunctionitreturnsitsvalue.Thisvalueessen-tiallyencodestheresultassignedtothevariable.Dependingonwhichmodeisbeingused(i.e.propagationorresolution),variablesmaybeallinstantiatedorsomeofthemmayhavearangeofpossiblevalues.Inthiscase,severalchoicesareobviouslypos-sible:wecaneitherdisplaytherangeofallowedvalues(e.g.{AopenAK-72133ATX,AsusK7MATX}),ordisplayasingleproposalofvalue(emphasizedwithaspecialcolour,sothattheuserseesthatothervaluesarepossibleforthisvariable),orsimplydisplayaspecialflagindicatingthatthevariableisnotinstantiatedyet.

4

BusinessrulesWeknowhowtodefinethedecisionvariableswhichwillencodevalidconfigurations.Wenowneedtodefineconstraintswhichwillrepresentthebusinessrulesexpressingthecorrectcombinationsofdecisionvariables.

AbusinessruleisdefinedasanewExcelfunctionwhichtakesasinputacollectionofdecisionvariablesandmaintainsaspecificinvariantontheme.g.,allthevariablesmusthavedifferentvalues.Aswehavepresented,CPvariablesarelocatedinEx-celcellsandcanthereforeeasilybecometheinputofrulesexpressedasnewExcelfunctionswhichwilladdconstraintstotheDisolvermodel.ThisispresentedintheConstraintspartoffigure2.

Thefirstruleisrelatedtothemotherboardcomponents.Itdefinesthelistofac-ceptedconfigurationsthroughalistofconjunctions(presentedinline32).Eachcon-junctionaccessesdecisionvariablesandspecifiesacorrectmotherboardrealisation.Forinstance,wefindincellB32,=(B18&&B23&&B12&&B27

====

\"AbitBX6ATX\"&&B10=Slot1&&B13=IDE4&&B15=\"233MHz\"&&B16=\"450MHz\"SDRAM168Pin&&B17=4&&B26=PCIPCI&&B28=PCI&&B29=AGP)

Thisrulevalidatesaconfigurationusingan“AbitBX6ATX”motherboardcom-binedtoa“Slot1”CPUslot,etc.The13possiblemotherboardconfigurationsofthePCbenchmarkcanbedefinedwithasmanyconjunctionconstraintsultimatelycombinedinadisjunctiveformula.ThisispresentedinB33,=Impose(B32||C32||...)

ThisconstraintimposesadisjunctionbetweenrulesB32,C32,etc.Ittakesasinputtheprevioussetofrules.Assaidbefore,aconstraintreturnsitstruthvalue2whichcanbereusedbysomeotherrule,orimposedinaconstraint.ValidProcessorcomponentsaresimilarlydefinedinthebottomoffigure2throughasimpledisjunctionofconjunctions.

Remarkthatwedonotgivealltherulesofthismodelwhichalsocontainsconjunc-tionofdisjunctionwhichspecifycorrectcombinationsofalltheremainingpartsofaproperPC3.2.2.3

InteractiveApplication

ExcelGUIscaneasilyuseourconfigurationmodellingtoprovideaninteractivefront-endtoend-users.Anexampleofsuchafront-endforourPCconfigurationproblemispresentedinfigure3.Itismadeofseveralcombo-boxeswhichreportthedomainsofthedecisionvariables.Eachselectordeselectactionisreportedtothemodelling

alsothatthisvalueisnotnecessarilyfullyspecifiedifweareinpropagationmode.Inthiscase,

oneoptionistoreturntheset{0,1},reflectingthefactthatbothvalues0(false)and1(true)arepossiblefortherule.

3ThefullDisolvermodellingforthisbenchmarkandotherclassicalconfigurationbenchmarkisavailableuponrequest.

2Note

5

wherebusinessrulesareenforcedthroughconstraintsandeventuallyleadtovaluesup-pressionsorenforcementinotherdecisionvariables.

Combo-boxescanbeaddressedinanyorderwiththeinsurance4ofmovinginaconsistentspaceofconfigurations.Whenachoiceleadingtoaninconsistencyisper-formed,itcanbeeasilyreportedthroughsomedialogboxwithsomeclearexplanationoftheconflict.

Atanytime,aSolvebuttoncanbepressedtofinishapartialconfiguration.Inopti-mizationsettingswecanimagineseveralSolvebuttonrelatedtodifferentoptimizationcriterion,e.g.,Solve/cheapest,etc.Additionally,aninteractioncanbesavedforlateraccessthroughappropriatebuttons.

Whileafinaluser,salespersonorcustomerwouldhaveafrequentaccesstothein-terfaceoftheapplication,themodellingpart(e.g.,figure2),wouldtypicallybewrittenbyanExcelprogrammerandwouldnotchangefrequently.Eventually,newcompo-nentstypecouldbeaddedordeletedandthiswillrequirearefreshofthedataworksheet(e.g.,figure1).Importantly,thiswillnotrequireachangeinthemodellingpart.Overall,solvingconfigurationproblemsinExcelispossible,easyandworthwhile.ItispossiblethankstotheintegrationofaConstraintssolveranditiseasybecauseconfigurationmodellingcanbeperformedinExcel’sprogrammaticmodel:withoutchangingthehabitsofanaverageExcelprogrammer.Finally,itisworthwhilesincetheprogrammingpartcanconsistentlycopewithfrequentlychangingbusinessdata.

3ConclusionandDiscussion

Inthispaper,weshowedhowExcelcanbeleveragedforconfigurationproblems.Be-sidethesimpleadditionofanewcapabilitytoaflagshipproduct,wethinkthattheproposedextensionwouldbeanimblewaytoaddressB2BandB2Cmarkets.In-deed,OfficeispervasiveandanyOffice-basedBusinessSolutionwouldbecomewidelyadoptedbyalargebasisofOfficecustomers.Furthermore,becauseExcelissopopular,webelievethatourproposalcouldindeedcontributetoawideradoptionofconfigura-tiontechnologies,sinceitisconceivablethatmoreuserswouldgetfamiliarwithitonceitisavailableintheOfficepackage,andwouldthengetinterestedinmorespecialisedoffersastheiruseofconfigurationtoolsincreases.

Wearecurrentlyimplementingtheproposedintegrationwhichwillbeavailableuponrequest.However,importantquestionsremain.

AfirstquestioniswhethertheaddedConstraintProgrammingfunctionalitiescanserveotherpurposesthanconfigurationapplications.AcentralfeatureofCPisthatitexpressesrelationaldependenciesbetweendata.Excel,ontheotherhand,isbasedonthemoretraditionalnotionoffunctionaldependency.ForinstancewecanspecifythatcellBenefits!C5isequaltothesumofallnumbersofcolumnF.Therefore,thepropagationisjustone-way:modifyingthevalueofonecellincolumnFwillpropa-gatetocellC5.Addingrelationaldependenciesallowstopropagatethedependenciesbackwardandtoautomaticallydeduce,forinstance,valuesorintervalsofvaluesfor

4Up

tocurrentconsistencylevel.

6

thecellsofcolumnFwhicharenotfilledyet,givenaprospectivevalueforC5.Wethinkthatthisfunctionalitymayverywellbeofinterestpersesinceitwouldallowtheusertointeractivelysimulatehowmodificationsinsomeofherdataimpactotherdata.

AsecondquestionisrelatedtothefactthatETOcaninvolvesomelevelofengi-neeringanalysistoconfigureproducts.ItwouldbeinterestingtoseeifsomeoftheseengineeringtaskscouldbeperformedfromanOfficeproductcloselylinkedwiththeconfiguratore.g.,Excel,Visio,etc.Iftheanswerispositivethatwouldbecomeanotherstrongpointforourproposal.

Altogether,itseemsthatExcel-basedconfiguratorswouldbeperfecttoaddresssmallandmediumproblemscurrentlysolvedbysmallcompaniesoperatinginnichemarkets.Again,themainadvantagesforcustomerswouldbecheapcostandsystemin-tegration.LargemarketswithfiercecompetitioncouldstillrelyondedicatedMicrosoftproductsdoingconfigurationincomplexB2B/B2Csettings.However,anyMicrosoftoffershouldbeunifiedandhere,theuseofthesameConstraintssolvingtechnologywhichinvolvestheacceptanceofthesameproblemsolvingformalismwouldgreatlyhelp.Indeed,itwouldaccompanyandeasecustomers’evolutionfromsmallExcelbasedconfiguratorsdefinedwithextendedspreadsheetconstructstoMicrosoftstand-aloneapplicationscodedinsomehighlevelprogramminglanguage.

References

[Cli]

Clib:configuration-benchmarks-library.

http://www.itu.dk/research/cla/externals/clib/.

[Des06]R.Desisto.Marketscopeforsalesconfiguration,2Q06.TechnicalReport

n/a,Gartner,2006.[Ham03]Y.Hamadi.Disolver:ADistributedConstraintSolver.TechnicalReport

MSR-TR-2003-91,MicrosoftResearch,Dec2003.

7

Figure1:Integrationofcomponentsdata

8

Figure2:DefinitionoftheconfigurationmodellingthroughaccesstotheConstraintssolvercomponents

9

Figure3:End-usersinteractiveapplication

10