March 24, 2013

Project Scheduling and Copresheaves

Posted by Simon Willerton

Obsessed as I am with finding examples of enriched categories, I was struck by the unfamiliar notion of ‘activity network’ when checking a colleague’s course on graph theory. What struck me was how scheduling actives seemed to be like finding a certain kind of copresheaf. Activity networks are also known as PERT charts to people in project management: an activity network or PERT chart records all the dependencies between the activities need to be completed during a project, and also records the times the activities will take to complete. Once you have this information you can try to schedule each of the activities in so that the project is completed as quickly as possible, and you can identify which activities are critical in the sense that any delay in that activity will cause a delay to the whole project.

I noticed that there was some enriched category theory going on with these PERT charts. Patrons of the Café are probably familiar with the idea that metric spaces can be thought of as categories enriched over $([0,\infty],\ge,+)$ the category of extended non-negative numbers. The triangle inequality for metric spaces then corresponds to the composition for enriched categories. The category that is enriched over for PERT charts is $(\{-\infty\}\cup[0,\infty],\le,+)$ so the main difference is that the morphisms go the other way, this means that you get a reversed triangle inequality! However, that makes sense in the scheduling context. I will explain how this gives categorical interpretations of terms like earliest start time, latest start time, float and critical path.

I have stressed the project management aspects here, but these ideas are also important, it seems, in scheduling processor jobs in parallel computing.

PERT graphs and project management

In project management, a project, for example renovating a house, will consist of various activities which need scheduling subject to various interdependencies between them. For instance, in the house example, you can’t get a decorator to paper the walls until you’ve had a plasterer plaster them and it takes, say, ten day to plaster the walls. There are standard methods to approach the scheduling of jobs. According to Wikipedia, the method of Program Evaluation and Review Technique (PERT) – closely associated to the critical path method –was introduced by the US Navy in the mid-twentieth century during the Polaris missile development and had precursors in the management of the Manhattan Project.

The PERT method begins with you writing down every activity you need to complete, how long each activity will take and which activities need which others to be finished. So, ignorant of anything to do with house renovation, let’s make up an example.

Label Activity Duration Requires
aFix electrics7 days
bPlaster walls10 daysa
cLay carpets3 daysa
dPaper walls12 daysb
eRe-tile roof15 days

Note that we’ve only put in the explicit dependencies, so that although papering the walls (activity d) also requires the fixing of electrics (activity a) to be finished we don’t put that in.

We add specific start and finish activities, which we will label S and F. Activity F has no duration and is explicitly dependent on everything which didn’t have anything dependent on it – you can’t finish before everything is completed. Activity S has no duration, is not dependent on anything and any activity which is not already dependent on something is made dependent on S – nothing can begin before the start.

Label Activity Duration Requires
SStart0 days-
aFix electrics7 daysS
bPlaster walls10 daysa
cLay carpets3 daysa
dPaper walls12 daysb
eRe-tile roof15 daysS
FFinish0 daysd, c, e

We can now draw a graph of this data. We draw a node for each activity and and arrow for each explicit dependency. Each arrow is labelled by the amount of time after the first activity has started that the second activity can start – here we are measuring time in days. This is the basis of what is called a PERT chart.

Those of you who have filled in grant applications may have been asked to provide a PERT chart. Now you know, more-or-less, what one is. Often they are also labelled with things such as ‘earliest start time’, ‘latest start time’ and ‘float’, but we’ll come to those below.

Scheduling and copresheaves?

The goal of drawing up a PERT chart is to schedule the work, for instance book the contractors, so that the project finishes as quickly as possible. This means we wish to assign a start time $T(x)$ to each activity $x$ so that whenever we have activity $y$ with an explicit dependency on $x$ we have the scheduling constraint.

(1)$C(x,y)+T(x)\le T(y)$

where $C(x,y)$ is the label on the arrow in the above PERT chart, so $C(x,y)$ is how long after $x$ starts that $y$ can start.

Actually we can give ourselves such scheduling constraints (1) on the start times $T(x)$ and $T(y)$ for every pair $x$ and $y$, not just those with those with arrows between them, by setting $C(x,y)=-\infty$ if there is no arrow from $x$ to $y$ in the graph, ie if there is no explicit dependency of $y$ on $x$. If we take $A$ to be our set of activities (including the start and finish activities) and $V$ to be the set $\{-\infty\}\cup [0,\infty)$, then we have encoded the dependencies and times as a $V$-graph $C$, on the set $A$, this just means that we have a function

$C\colon A\times A\to V.$

I’ve obviously been thinking too much about enriched categories of late as the scheduling constraint (1) looks to me like a copresheaf condition. Remember that a copresheaf on an ordinary category $\mathcal{A}$ is functor $T\colon \mathcal{A}\to Set$, so that means, of course, that to each object $x$ in $\mathcal{A}$ we associate a set $T(x)$ and to each pair of elements $x$ and $y$ we have a function between sets $T\colon Hom_{\mathcal{A}}(x,y)\to Hom_{Set}(T(x),T(y))$, or to put it another way, we have a morphism in the category of sets

(2)$Hom_{\mathcal{A}}(x,y)\times T(x)\to T(y),$

where $(f,\alpha)\mapsto T(f)(\alpha)$. Compare this with the scheduling constraint (1).

Closed monoidal structure

To make this similarity into something more formal we can make $\{-\infty\}\cup[0,\infty)$ into a category by using $\le$ as a poset structure, so there is a unique morphism $a\to b$ if and only if $a\le b$ and using $+$ as a monoidal structure. Note that this is the opposite to the category structure used on $[0,\infty]$ to define metric spaces as enriched categories – there we use $\ge$. This means we can write the scheduling constraint (1) as the morphism

$C(x,y)\otimes T(x)\to T(y)$

which now looks more like the set copresheaf situation (2).

If we are enriching over a monoidal category $(\mathcal{V},\otimes)$ and want to talk about $\mathcal{V}$-functors into $\mathcal{V}$ then we will need to give $\mathcal{V}$ a $\mathcal{V}$-category structure, thiat is to say we will need that $\mathcal{V}$ is a closed monoidal category. This means we need a functor $[[{-},{-}]]\colon \mathcal{V}\times \mathcal{V}\to \mathcal{V}$ such for each $v\in \mathcal{V}$ the functor $v\otimes{-}$ is left adjoint to $[[v,{-}]]$. I’m using double brackets here not to confuse the internal hom $[[a,b]]$ with the closed interval $[a,b]$.

In our case this means we need

$a+b\le c \qquad\text{if and only if} \qquad a\le [[b,c]].$

In order to do this we will have to add a plus infinity, so we will define the category $\mathcal{R}$ to be $\{-\infty\}\cup[0,\infty]$ with $\le$ giving the morphisms and $+$ being the monoidal structure. It is easy to say what the closed structure is on finite numbers, so for $a,b\in (-\infty,\infty)$ we define

$[[a,b]]=\begin{cases} b-a& a\le b,\\ -\infty& a\gt b\end{cases}$

I will often write $b-a$ instead of $[[a,b]]$ with the understanding that it means $-\infty$ if you get a negative answer.

Exercise: How do the monoidal and closed structures extend to include infinite numbers? Fill in the following tables, where $a$ and $b$ are finite. (I can give a hint if people need help getting started.) $\begin{matrix} +& \color{red}{-\infty} &\color{red}{b}& \color{red}{+\infty} \\ \color{red} -\infty& -\infty&-\infty&?\\ \color{red} a &-\infty& a+b & +\infty\\ \color{red}+\infty&?&+\infty&+\infty \end{matrix} \qquad\qquad\qquad\qquad \begin{matrix} [[,]]& \color{red}{-\infty} &\color{red}{b}& \color{red}{+\infty} \\ \color{red} -\infty& ?&?&?\\ \color{red} a &?& b-a & ?\\ \color{red}+\infty&?&?&? \end{matrix}$

If I’d put negative numbers in as well (which I don’t think are necessary here) then I would have used ordinary subtraction between finite numbers. This is what Lawvere does when he puts this closed monoidal structure on $[-\infty,\infty]$, the whole of the extended real numbers, in his entropy paper:

State Categories, Closed Categories, and the Existence Semi-Continuous Entropy Functions, (10 MB file!) IMA reprint 86 (1984).

He calls categories enriched over $([0,\infty],\le,+)$ ‘entropic categories’. I haven’t fully digested what use he makes of them in this paper.

Enriching over $\mathcal{R}$

We can now consider categories enriched over the closed monoidal category $\mathcal{R}=(\{-\infty\}\cup[0,\infty],\le,+)$. Let’s just remind ourselves what such a thing is. It consists of a set $A$ and a function $D\colon A\times A\to \{-\infty\}\cup[0,\infty]$ such that

• for all $x\in A$ we have $0\le D(x,x)$,
• for all $x,y,z\in A$ we have $D(x,y) +D(y,z)\le D(x,z)$.

This last condition looks bizarre as it is the triangle inequality the wrong way round! However, we will make sense of it in if we look at our scheduling example. Our PERT chart, illustrating the explicit dependencies between events, can be thought of as an $\mathcal{R}$-graph on the set $A$, this just means it corresponds a function

$C\colon A\times A \to \{-\infty\}\cup[0,\infty]$

We can form the free $\mathcal{R}$-category on $A$ by defining

$D(x,y)\coloneqq max\{C(x,a_1)+C(a_1,a_2)+\dots +C(a_{n-1},a_n)+C(a_{n},y)\},$

where the maximum is taken over all the tuples $a_1,\dots, a_n\in A$ and over all $n\ge 0$. (Here max is the coproduct in $\mathcal{R}$.) This $\mathcal{R}$-category is now recording the implicit dependencies. So for instance in the example above we didn’t record any explicit dependency between fixing the electrics (activity a) and finishing the project (activity $F$), so $C(a,F)=-\infty$ but it is a consequence of the other dependencies that you need to fix the electrics at least twenty nine days before finishing the project, ie $D(a,F)=29$.

I hope that if we interpret $D(x,y)$ as the time lag between starting activity $x$ and starting activity $y$, you can now make sense of the reversed triangle inequality

$D(x,y) +D(y,z)\le D(x,z).$

The minimum time lag after starting $x$ to starting $z$ is at least as big as the minimum time lag from $x$ starting to $y$ starting plus the minimum time lag from $y$ starting to $z$ starting So we can think of the hom-objects in an $\mathcal{R}$-category as being like minimum possible time lags rather than minimum possible distances.

Scheduling and copresheaves

We can now return to the scheduling question. We want to schedule the activities in our project subject to the dependencies between them. Here by scheduling an activity $x$ we will mean setting a time $T(x)\in [0,\infty)$ relative to the start of the project, so that $T(S)=0$, subject to the explicit constraints, so for all activities $x,y\in A$

$C(x,y)\le T(y)-T(x).$

This means that $T$ is precisely an $\mathcal{R}$-graph function from out PERT chart to the underlying $\mathcal{R}$-graph of $\mathcal{R}$. This is corresponds exactly to an $\mathcal{R}$-functor from the free $\mathcal{R}$-category $(A,D)$ to $\mathcal{R}$. This is just expressing the free-forgetful functor between $\mathcal{R}$-graphs and $\mathcal{R}$-categories:

$\mathcal{R}\text{-Grph}(A, U(\mathcal{R}))\cong \mathcal{R}\text{-Cat}(F(A),\mathcal{R}).$

In other words, scheduling the jobs means finding a copresheaf on the $\mathcal{R}$-category $(A,D)$ of implicit dependencies.

We can give some categorical interpretations of standard ideas in critical path analysis now.

What we really want to do is to finish the project as quickly as possible. The shortest amount of time the project will take to finish is the minimum time lag between the start and the finish, this is just $D(S,F)$. Given that length of time, we want to know how much freedom we have in scheduling individual activities and whether delaying a specific activity will cause the whole project to be delayed – will it matter if the plasterer doesn’t turn up on time or the walls take longer to dry out than expected. There are three basic things then to know about each activity: the earliest start time, the latest start time, and the float.

• The earliest start time of an activity is hopefully self-explanatory. It is the minimum time lag between the start of the project and the start of the activity. In categorical terms it is just $D(S,x)$ – the evaluation of the representable copresheaf. As functions we have that the earliest start time is a copresheaf $\text{earliest start time} =D(S,{-}).$

• The latest start time of an activity is the latest that an activity can start without delaying the whole project. The minimum time lag between the activity $x$ and the finish is $D(x,F)$, and if the project is not delayed then the finish time is $D(S,F)$, thus the latest start time is $D(S,F)- D(x,F)$ or in internal hom terms $[[D(x,F),D(S,F)]]$. So the latest start time is the copresheaf $\text{latest start time}=[[D({-},F),D(S,F)]].$

• The float of an activity is the difference between its earliest start time and its latest start time, and so reflects how much leeway you have in scheduling the activity. If the float is zero then the activity is said to be critical. In our notation the float of activity $x$ is $(D(S,F)- D(x,F))-D(S,x)=D(S,F)-( D(x,F)+D(S,x) )$ or in the internal hom notation $[[D(S,x) + D(x,F) ,D(S,F)]]$ To put it another way, the float is measuring how much the reverse triangle equality is violated for $x$ between $S$ and $F$.

A viable schedule $T$ will be one which finishes the project as soon as possible and satisfies the constraints so will be a copresheaf which satisfies

$D(S,{-})\le T({-}) \le[[D({-},F),D(S,F)]].$

I don’t know if that is a condition which crops up elsewhere in category theory.

A further important notion is that of critical path, these are the paths in the PERT graph from the start to the finish which consist of activities with float zero, so a delay of any activity on the path will lead to a delay in the project. The path $S a b d F$ is critical in our example above. Everywhere on a critical path the triangle inequality from $S$ to $F$ is actually an equality, so critical paths are the analogues of geodesics in metric spaces.

Further questions

All of this came out of me looking at a colleague’s course and thinking randomly “Hmm. That looks categorical.” Here are some random further questions.

1. Do other categorical notions have useful interpretations in this context? Is the notion of $\mathcal{R}$-functor between projects meaningful? How about the notion of $\mathcal{R}$-profunctor?

2. Is it useful to think of these things are ‘generalized metric spaces with negative distances’?

3. Do these ideas extend to other networks such as Petri nets or networks of resistors?

4. Does it help to think in terms of entropy as in Lawvere’s paper?

Posted at March 24, 2013 5:47 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2602

18 Comments & 0 Trackbacks

Re: Project Scheduling and Copresheaves

[Note: Tim emailed me this straight after a skim reading of the post and before drinking his morning coffee, so I take responsibility for posting this here. Simon.]

I liked the post. I used to teach critical path analysis, and then go on to discrete dynamical systems and (times) Petri nets. These both have strong categorical flavour.

Have you looked at the paper:

Casley, R.T., Crew, R.F., Meseguer, J., and Pratt, V.R., Temporal Structures, Proc. Category Theory and Computer Science 1989, ed. D. Pitt et al, LNCS 389, 21-51, Springer-Verlag, 1989. Revised journal version in Mathematical Structures in Computer Science, Volume 1:2, 179-213, July 1991. (The Journal version is good preprint pdf.)

(I think that is the right one of Pratt’s work. He has written a lot that is discursive so it is difficult to find which bit it is in.)

There are links between discrete dynamical systems approaches to scheduling and tropical algebra. I used to get students doing projects on using the Max+ / tropical algebra and linear algebra to attack fairly real life scheduling problems. That was good fun both for the students and for me! I learnt a lot!

The Petri nets aspect was explored by Meseguer, as a Petri net looks like a presentation of an symmetric monoidal category. Your post suggests that there may be an enriched version of his result for times Petri nets. (I had meant to explore that with students but the occasion never came, and the Bangor department was closed which made things impossible.) Meseguer’s papers include

José Meseguer, Ugo Montanari: Petri Nets Are Monoids: A New Algebraic Foundation for Net Theory. LICS 1988: 155-164

and another one on Petri nets and Linear Logic from about the same time. See Meseguer’s papers at dblp.

Posted by: Tim Porter on March 25, 2013 9:19 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Tim, thanks for these. I’ll have a look.

Last week I got hold of a copy of

Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications (Princeton Series in Applied Mathematics) Bernd Heidergott, Geert Jan Olsder, Jacob van der Woude.

They seem to take train scheduling as a key motivating example. I’m looking forward to chugging through it.

Posted by: Simon Willerton on March 26, 2013 5:40 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

As I said before, I found it a fun area to teach. Somehow it seems that you can persuade the students that the calculations and theory are (i) useful (ii) not too difficult as they mirror ordinary linear algebra, and (iii) the methods reveal a lot about the algebra that they use almost automatically since here if you try to go on automatic pilot’ you start subtracting yet that is clearly a silly thing to do.

I would be great to see this introduced into a lot of undergraduate courses. (I usually used Stephan Gaubert’s notes as a basis. I put a link on the n-Lab…. I am also convinced that eventually the homotopical algebra of related things will become very important.)

Posted by: Tim Porter on March 29, 2013 7:05 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Here’s a link to the notes of Gaubert on discrete event systems: Introduction aux Systèmes Dynamiques à Événements Discrets.

I’ve realized that the PERT graphs above fall into the timed Petri net net. In fact they fall into the smaller net of timed event graphs.

Tim, you said to me (in an email) that you have been “trying to push the idea of modelling complex systems of various types by enriched categories for some time”. Is there somewhere where I can read about this, or have you just been doing it verbally?

Posted by: Simon Willerton on April 8, 2013 11:55 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Mostly verbally!! I did prepare some draft EPSRC proposals but then it became clear that I needed a publication trail in such areas. I had talked about enriching shape theory in something like that way, way back in the 1980s, and also had published some stuff on using Chu spaces in their more general form (i.e. with a richer set of truth values’) for handling observations. This was then further pushed forward with the project work the students had done on Petri nets etc., but then time ran out as it was clear that Bangor was going to be shut down, and our work load was going up. I talked to the then computer scientists in Bangor at the time, but then they left!

I never felt that the work would get published so left it aside. The ideas were not ripe at that time and there was not the interest in them that there might be now.

Posted by: Tim Porter on April 9, 2013 6:33 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Of course, as soon as I saw my e-mail I saw a typo, (is that a version of Sod’s law?). It should be `(timed) Petri nets’, not (times)!

Posted by: Tim Porter on March 25, 2013 10:34 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Why the exotic-sounding word ‘copresheaf’ instead of the familiar one ‘functor’?

Posted by: Mike Shulman on March 25, 2013 12:43 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Good question. I guess one answer is that I have been thinking too much about presheaves and copresheaves recently, so forgot that copresheaf might sound exotic to some (or perhaps, to most).

My emphasis on the word ‘copresheaf’ rather than ‘functor’ is due to thinking of copresheaves as being akin to functionals (ie scalar-valued functions) and functors as being akin to more general functions – I’m reckoning that functionals are the most basic kind of function. I consider the enriching category $\mathcal{V}$ to be the ‘scalars’, so a copresheaf on $\mathcal{C}$ is just a scalar-valued functor $\mathcal{C}\to {V}$.

In retrospect ‘functor’ might have been a less scary word to use than ‘copresheaf’, but would miss the specificity.

Posted by: Simon Willerton on March 25, 2013 4:19 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

So can

$D(x,y)\coloneqq max\{C(x,a_1)+C(a_1,a_2)+\dots +C(a_{n-1},a_n)+C(a_{n},y)\}$

be thought of as a path integral? As in matrix mechanics for any rig, it seems there is ‘multiplication’ (here addition) along a path and summation (here max) across paths.

Posted by: David Corfield on March 26, 2013 9:43 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Yes. You can think of it like that. It is indeed a ‘sum’ over all ‘paths’ of a certain ‘product’.

You should compare it with the metric graph case if you haven’t already. Suppose you have a graph with edges marked with a given length, so if $u$ and $v$ are vertices at either end of an edge then there is a length $L(u,v)\in [0,\infty)$. We can then get a metric on the vertex set $Vert$ by the ‘shortest path metric’. This is a free $[0,\infty]$-category by the analogous construction to that which I did for PERT graphs: I will spell that out.

We can extend the edge lengths to a function $L\colon Vert \times Vert \to [0,\infty]$, ie a $[0,\infty]$-grap, by $L(u,v)\coloneqq \infty$ if $u$ and $v$ do not have an edge between them.

We think of $[0,\infty]$ as a monoidal catgory where we have a morphism $a\to b$ if and only if $a\ge b$ and the monoidal product is addition $+$. The coproduct for this is min. So the free $[0,\infty]$-category $(Vert,\;d\colon Vert\times Vert \to [0,\infty])$ on the $[0,\infty]$-graph $(Vert,\; L\colon Vert\times Vert \to [0,\infty])$ is the shortest path metric:

$d(u,v)\coloneqq min\{L(u,a_1)+L(a_1,a_2)+\dots +L(a_{n-1},a_n)+L(a_{n},v)\}.$

This is again a ‘path integral’ in the sense you describe it.

Posted by: Simon Willerton on March 26, 2013 3:50 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Your

$C(x,y)+T(x)≤T(y)$

is very much like your bakery example of optimal transport

$\phi(Hovis)\gt \phi(Warburtons)+d(Warburtons,Hovis).$

Posted by: David Corfield on March 26, 2013 10:34 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Indeed, it is very much like the bakery example. The condition I want satisfied there is the negation of the inequality you give, so I want

$d(Warburtons, Hovis)+ \phi(Warburtons) \ge \phi(Hovis).$

Thus $\phi$ is a copresheaf on the metric space of bakeries. I seemed to have claimed back then that it was a presheaf, but I think I got the variance wrong. I’ll talk you through this a bit further below.

Why do I get the opposite inequality here to the scheduling case where I claimed that a copresheaf is something which satisfies

$C(x,y)+ T(x)\le T(y)?$

That’s because PERT graphs are related to categories enriched over a poset of extended non-negative real numbers with $\le$ and metric spaces are categories enriched over a poset of extended non-negative reals with $\ge$.

Let’s remind ourselves what a copresheaf is. Suppose $\mathcal{V}$ is a closed monoidal category. For $\mathcal{C}$ a $\mathcal{V}$-enriched category a presheaf on $\mathcal{C}$ is a $\mathcal{V}$-functor $T\colon \mathcal{C}\to \mathcal{V}$. This means that it consists of a function on objects $T\colon ob(\mathcal{C})\to ob(\mathcal{V})$, and for each pair of objects $x,y \in ob({C})$ there is a morphism in $\mathcal{V}$

$Hom_{\mathcal{C}}(x,y) \to Hom_{\mathcal{V}}(T(x),T(y)).$

Here $Hom_{\mathcal{V}}$ means the internal hom in $\mathcal{V}$. Because $\mathcal{V}$ is closed we have the hom-tensor adjunction in $\mathcal{V}$ so the morphism above is equivalent to a morphism in $\mathcal{V}$

$Hom_{\mathcal{C}}(x,y)\otimes T(x) \to T(y).$

If we are taking $\mathcal{V}$ a poset of real numbers with addition as the monoidal structure, then the $\otimes$ becomes a $+$ and the existence of a morphism in $\mathcal{V}$ of the form $a\to b$ just means $a \ge b$ or $a\le b$ depending on which partial order on the reals we have taken.

In the $\le$ case the copresheaf condition is

$Hom_{\mathcal{C}}(x,y) + T(x) \le T(y),$

which is what we see for PERT graphs.

On the other hand, in the $\ge$ case (ie the case relevant for metric spaces) the copresheaf condition is

$Hom_{\mathcal{C}}(x,y) + T(x) \ge T(y),$

which is what we saw for the bakeries.

Posted by: Simon Willerton on April 1, 2013 6:41 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

What I always dreamed of was a nice piece of shiny machinery (matrix mechanics) with a dial for you to choose your rig, and off it would go pumping out results on classical, quantum, statistical mechanics, homotopy theory, and now maybe optimal transport and project scheduling.

There was also the hope that rig morphisms would allow us to relate these areas, e.g., if a classical particle can get from A to B in a space, it means A and B are path connected.

Posted by: David Corfield on April 2, 2013 1:57 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

An interesting question in this regard is to whether or not a given rig $R$ can be categorified in the sense of finding a monoidal category whose set of (isomorphism class) of objects in the underlying set of $R$, whose monoidal product on objects becomes the product in the rig and whose categorical coproduct becomes the addition in the rig.

By the above we can do that for $(\mathbb{R},max,+)$ and $(\mathbb{R},min,+)$. We can also do that for $(\mathbb{N},+,\times)$ by taking the category of finite sets with the monoidal product being the cartesian product. But can we categorify $([0,\infty],+,\times)$?? That would allow us to do proper(ish) path integrals in this enriched setting.

Posted by: Simon Willerton on April 2, 2013 2:48 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

We had plenty of discussion over the years of using tame groupoids with obvious sum and product as a categorification of the non-negative reals. Of course, any given real will have many different representations as a groupoid cardinality.

We even wondered about a ‘distance’ between groupoids.

Posted by: David Corfield on April 2, 2013 3:10 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

David wrote:

What I always dreamed of was a nice piece of shiny machinery (matrix mechanics) with a dial for you to choose your rig, and off it would go pumping out results on classical, quantum, statistical mechanics, homotopy theory, and now maybe optimal transport and project scheduling.

We basically came up with it; the links you assembled explain it. But I guess we’d have to write things up a bit more formally, preferably all in one place, for people to see that this machinery really exists.

When I saw Simon in Sheffield last week, he showed me the book Max Plus at Work, a rather down-to-earth introduction to the max-plus rig and its applications to train scheduling. It has a nice section on ‘timed Petri nets’ which, I realized, are just like the ‘stochastic Petri nets’ I love except that they use the max-plus rig instead of the rig of nonnegative reals with their ordinary addition and multiplication. So, chemical reaction theory is a deformation of train scheduling!

I wanted to write a paper explaining this then and there, and Simon sounded interested, so maybe we’ll do it. But he seems a bit more interested in enriching categories over different monoidal categories, while I seem a bit more interested in linear algebra over different rigs (or rig categories). So we may not be seeing eye-to-eye yet. They should be closely related, of course.

Posted by: John Baez on April 5, 2013 2:02 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

…chemical reaction theory is a deformation of train scheduling!

Excellent!

I wanted to write a paper explaining this then and there…

It would be great to revisit the ideas we all had in this area. No doubt they’re quite scattered. I just came across Urs talking about path length and path integral.

Posted by: David Corfield on April 5, 2013 8:34 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

John, I do like your overstated, as opposed to British understated, comments.

I wanted to write a paper […] then and there.

Ah, I didn’t realize.

There’s a link to the Max Plus at Work book above – the link points to the publisher rather than to Amazon as I’m trying to avoid Amazon at the moment due to their anti-social tax avoidance methods. (Note: there is a certain amount of British understatement in that last sentence.)

Posted by: Simon Willerton on April 9, 2013 11:40 AM | Permalink | Reply to this

Post a New Comment