Onion Information

Page Clicks: 0

First Seen: 05/06/2024

Last Indexed: 10/25/2024

Domain Index Total: 80

In the previous posts Feasibility is optimal and On self-concordant convergence I have made the case that seeking centrality may be better than trying to optimize on some objective function. The reason for this is two-fold: there is uncertainty in the data that make up the constraints seeking centrality gives each workplace more leeway In this post I will go into the second point, describing how we might quantify the amount of leeway/autonomy that can be provided to each workplace "no questions asked" by the system as a whole. Defining workplace autonomy What I mean by autonomy in this post is the extent to which each workplace can govern itself without threatening the feasibility of the system as a whole. The less constrained each workplace is the more "free" the workers in that workplace are likely to be. The more orthogonal its actions can be to the rest of the economy, the freeër it is. But at the same time, no workplace is an island. Excessive production of some products may induce demand or side-effects in other parts in the system that exceed the system's capabilities, thus violating feasibility. Greenhouse gas emissions are the obvious example, but other issues like eutrophication are also a concern, as happens currently with the southern parts of the Baltic sea ( Övergödning och läckage av växtnäring, Eutrophication and leakage of plant fertilizer , Jordbruksverket, fetched 2023-05-15). Likewise insufficient production will cause shortages in downstream workplaces, also violating feasibility. A maker of electric motors may speculatively try to make products in excess of the supply of rare-earth elements for magnets, which obviously will cause shortages in other parts of the economy, and thus such production should be discouraged. But if they don't exceed said supply, then it may be worthwhile to produce more than is currently demanded because tooling costs amortize. This would lower the cost of the products overall, and allow the workers there to take time off. Therefore for work scheduling purposes it would be useful to know within what bounds production can be guaranteed to proceed smoothly, assuming sufficiently accurate data in the relevant parts of the system. The more orthogonal a workplace is to the rest of the economy, the easier the scheduling of its work becomes. Being able to answer these questions by machine quickly means less bureaucracy, also an obvious boon to workplace autonomy. Finally, when workers in a workplace know that they can reduce production by a certain amount for a certain length of time, this allows exploring other production methods. For example another type of plant can be planted or another gizmo invented using the resources so freed up. We can imagine many remuneration schemes encouraging such exploration. There is always a tradeoff between exploration and exploitation, a problem known as the multi-armed bandit . The geometry of workplace autonomy I have mentioned orthogonality above. In this section I will show what this means. Let us for simplicity in visualization imagine two workplaces, A and B. A makes product a and B makes product b. It is estimated by both workplaces independently that for some time period A can produce between 0-100 units of a and B can produce 0-50 units of b. Each unit of a and b produces one unit of emissions, and the total amount of emissions are to be kept below 110. The estimated demand for a is 40 and the estimated demand for b is 10. Let us assume that the center of the system is at a = 60 , b = 20 . The situation looks like the following figure: The diagonal line corresponds to the emissions constraint. It may be tempting for each workplace to look at this and derive updated bounds on their own production without taking the other into consideration, namely 40 ≤ a ≤ 90 and 10 ≤ b ≤ 50 : However as sharp-eyed readers may realize, if both workplaces act entirely autonomously using only these bounds as reference then feasibility cannot be guaranteed. The Cartesian product of the two bounds is a rectangle, part of which lies outside of the feasible region: The orthogonality I have mentioned is here apparent. The rectangle's sides are orthogonal (at 90°) to one another. There are many choices for feasible rectangles in this system, and the most straightforward one seems to be to scale the limits on both a and b down so that the upper-right corner of the rectangle lies on the emissions constraint, like so: The updated bounds are 40 ≤ a ≤ 75 and 10 ≤ b ≤ 35 . Many other feasible bounds are possible. This approach generalizes to any number of workplaces and production methods, meaning we can always fit some n-dimensional rectangle ( orthotope or box ) inside the system. All that is necessary is that all corners of the box lie within the feasible region. Other geometries are also possible. Production within one workplace having two production methods available could be limited not just to a rectangle but any convex polygon, for example a hexagon. The Cartesian product of such a polygon with another workplace having just one production method results in a prism . Note that the sides of the prism are orthogonal to its ends. This orthogonality is again key to why autonomy can be guaranteed. That the edges of the hexagons are not orthogonal to one another is here a strength, since this allows more autonomy within the associated workplace. We can quantify the degree of autonomy by the area of the hexagon. For the other workplace it is the length of the sides between the two hexagons. For the system as a whole the total autonomy is the volume of the prism, which is just the product of the hexagon's area and the side length. If the number of production methods n is larger than three then the result is a prismatic polytope , which are difficult to illustrate for obvious reasons. Such polytopes have properties that make them easier to deal with computationally than polytopes in general. Note that two or more workplaces coordinating their actions more tightly can get a combined larger volume to work within, at the cost of reduced autonomy and at the cost of more infernal meetings. The figure below illustrates a situation where the heaxgonal workplace has more room to work within when the linear workplace is closer to the "lower" state. The resulting shape is a frustrum. It should hopefully be clear that the two workplaces are now dependent on more communication than before. Note that the amount of necessary communication can be attenuated by an automatic plan solver. But the roundtrip time inherent in that may be irritating to workplace coordination, for example when assigning shifts. Hence a preference to autonomy. A small demo Apologies to those who are even more averse to JavaScript than I am, but I know of no way to do the following using just HTML+CSS. The system below is the same as the one before. Try dragging the slider and see what happens. The dot doesn't move, sorry. Patch welcome! 40 100 10 50 A more complicated example would use multiple workplaces with multiple production methods and a simulated delay, showing how two or more workplaces stepping outside the box can result in infeasibility that isn't immediately visible. Perhaps something for the future.. A fast box fitting algorithm Consider the closed polytope A ′ x ≥ b ′ with A ′ ∈ R m × n and a non-zero internal volume, and some internal point ξ around which we'd like to find a large n-dimensional box B . Without loss of generality we can change the coordinate system to make the origin ( 0 , 0 , … , 0 ) correspond to ξ . The updated system is A x ≥ b where all entries in b by necessity are negative. If we want we can again without loss of generality scale each row in A so that all entries in b are -1. The implementation does this, but for clarity the description does not. Next introduce the positive vectors l and u , the lower and upper bounds that make up B , like so: B = { x | ∀ i ∈ [ 1 , n ] : l i ≤ x i ≤ + u i } The 2 n corners h of B have the coordinates h = ( - l 1 or + u 1 , - l 2 or + u 2 , … , - l n or + u n ) and because l i > 0 and u i > 0 the origin is always contained in the box. It is easy to see that the (hyper)volume of the box is V = ∏ l i + u i We would ideally like to compute the largest feasible box that contains the origin, or if we can't guarantee optimality then we at least want a box that is not unreasonably small. The algorithm proposed here is one that produces a reasonable, but not necessarily optimal, B . We start by observing that for all rows a i T there is a set of corners that minimize the scalar product with a i T . In other words the corners that violates the constraint a i T h ≥ b the most, or if they don't violate it then they are the least slack. These corners have signs opposite of a i T . Dimensions corresponding to zeros in a i T are irrelevant. We can therefore describe the entire set of corners by h ( i ) with signs opposite of a i T , including zeros (which are set to zero in h ( i ) ), like so: h j ( i ) = { - l j if a i , j > 0 + u j if a i , j b ) and so we can always squeeze l and u into the gap. In fact this algorithm is motivated partly by improving the lower bound on the volume of B . We can always compute a box that will fit by first fitting an orthoplex , or more specifically a type of asymmetric lozenge , by tracing in the positive and negative cardinal directions, resulting in initial values for l and u . To make the above less abstract let's look at some figures. Let's start with a polygon with the origin in its interior: By tracing in the cardinal directions we can fit a lozenge within it, which is guaranteed to always work because the polygon is convex: Finding the rectangle that is the dual to this lozenge (blue) is easy, as is finding the rectangle to which the lozenge itself is the dual (red): In general the lozenge has the following hypervolume: V lozenge = 1 n ! ∏ l i + u i The smaller box provides a lower bound on the volume of the large box we seek: V lower = ∏ l i + u i n = 1 n ∏ l i + u i The larger box naturally provides the upper bound: V upper = ∏ l i + u i Obviously V upper / V lower = n is a rather large range, so the chances of us finding a box that is not so horrible are probably good. Keeping in mind that n ≈ 10 , the V lower bound is equivalent to say a cobbler having leeway to make anywhere between 9.999999999 and 10.000000001 shoes in a given period. Not hooray. So the point is to widen these bounds to something more reasonable, perhaps 5 to 15 shoes. We are now ready to list the algorithm: Compute initial l and u by tracing lines in the positive and negative cardinal directions from the origin, assigning each entry based on the closest constraint encountered For i = 1 … m : For j = 1 … n let h j ( i ) = { - l j if a i , j > 0 + u j if a i , j 0 then update l j : = k ( i ) l j For j = 1 … n if a i T 2 8 cor...