How to obtain the optimum from a linear programming problem, when the calculations have to be carried out in a decentralized way

In: Statistica Neerlandica, Volume 23, Issue 2, p. 115-149

Abstract

Samenvatting Er zijn verscheidene betrouwbare, snelle elektronische rekenmachines met een groot geheugen verkrijgbaar. Ondanks het feit, dat deze machines in staat zijn grote lineaire programmeringsproblemen op te lossen, blijven er een aantal over, die niet in zijn geheel opgelost kunnen worden of die om andere redenen niet in zijn geheel opgelost zullen worden. In zo'n geval wordt het totale probleem vaak gesplitst in deelproblemen. Men doet dit door aan een aantal variabelen waarden toe te kennen, waarvan men hoopt, dat ze ongeveer zo groot zullen zijn als die, die men verkregen zou hebben na oplossing van het totale lineaire programmeringsproblm. Aangezien men in de praktijk vaak genoegen neemt met pseudo‐optimale antwoorden, geeft zo'n combinatie van oplossingen van deelproblemen in het algemeen bruikbare resultaten, mits de gegeven schattingen voor de variablen, die maakten dat het totale probleem gesplitst kon worden, niet te ver van de goede waarden zullen afwijken. Aangezien men dit zonder het oplossen van het totale probleem nooit te weten zal komen, blijft het raadzaam te proberen deze schattingen op een dusdanige wijze te verbeteren, dat ze de waarden behorende bij de optimale oplossing benaderen.In 1961 werd hiervoor een werkwijze ontwikkeld bij de Bataafse Internationale Petroleum Maat‐schappij N.V. die op 7 maart 1962 intern gerapporteerd werd in een rapport, dat ongeveer gelijkluidt aan de titel van dit artikel.Past men de hierin beschreven werkwijze toe, dan verbetert men iteratief de schattingen en wel op een dusdanige wijze, dat de waarde van de doelfunctie van het totale probleem van stap tot stap beter wordt. Evenals in het rechtstreeks toepassen van lineaire programmering is het theoretisch mogelijk, dat twee na elkaar verkregen combinaties van resultaten, een zelfde waarde van de doelfunctie opleveren. De kans hierop wordt echter in de, in dit artikel beschreven methode, veel kleiner. Hieruit blijkt, dat de resultaten, verkregen na het verrichten van enkele stappen, een beter resultaat geven, dan de eerste schatting. Is men dus gedwongen om welke reden dan ook, het rekenwerk te stoppen, dan heeft men een beter resultaat verkregen dan dat, behorende bij de eerste schatting.Vaak zal het ook niet nuttig zijn verder te gaan met het rekenwerk, aangezien ervaring heeft geleerd, dat de grootste verbeteringen in het begin te verwachten zijn. Theoretisch kan men door het volgen van de methode het optimum bereiken. De methode werd echter niet met dit doel voor ogen antwikkeld en kan in dat geval te langzaam zijn en daardoor te kostbaar werken.Alhoewel de methode het eenvoudigst toe te passen is, indien men de deelproblemen op één plaats ter beschikking heeft, werd ze ontwikkeld teneinde gedecentralizeerd werken toe te laten. In zo'n geval zal er enige informatie van een centraal punt naar de plaatsen. waar de deelproblemen behandeld worden verzonden moeten worden en terug; deze hoeveelheid informatie is echter gering.Summary Nowadays most electronic computers have large memories and are able to carry out calculations very rapidly. Nevertheless, it may be impractical or impossible for some computers to solve very big linear programming problems without some modifications to the problem. Fortunately, the optimal answer is not always needed, but any possible improvement of an estimated answer may be of great value. In this article it is shown, how this can be reached by splitting the integrated problem of a bigger company into several natural. and much smaller, problems, linked by certain variables. Furthermore a method is described for finding an improved answer to that inte grated problem. It is reached by first estimating the linking variables and then improving this estimate in a number of systematic steps. It is developed for cases where the calculation work is carried out on a decentralized basis, but works even easier in cases where all calculation work is carried out on the same place. In the first case there has to be a flow of information between places, where calculations on smaller problems are carried out and the place where the calculations are carried out on the sizes of the linking variables only. Theoretically the optimum may be reached in a finite number of steps, but when calculations have to stop before reaching the overall optimum, an improvement will have been achieved, since each solution obtained is at least as good as, but generally better than the preceeding one.The method is developed in 1961.For non‐mathematicians it may be difficult to understand an article written in matrix‐notation. Therefore, the proofs and derivations in this article are given without matrix‐notation. Consequently the method will be more easily understood by those, who are likely to use it, the more so, since proofs and derivations are given for a limited number of variables and blocks only.