I am working on a problem where I need to extract a connected tree of nodes based on certain attributes while optimizing for the minimum number of nodes. Some attributes of the nodes are known in advance, such as resource capacity. However, I do not know in advance how many nodes will be selected in the final tree, especially the intermediate nodes that ensure connectivity and may act as task-forwarding nodes.
The goal is to formulate a mathematical optimization model with a set of constraints to select an ordered tree with the minimum number of nodes, where each node hosts specific tasks. Selecting individual nodes is straightforward, but I am struggling to write the constraints to ensure that:
- All selected nodes are connected.
- The hosted tasks follow a desired ordered sequence.
For example, if nodes host tasks A, B, C, and D, task A should be in a node that comes before a node hosting task B, and so on. Multiple tasks can be placed in the same node if they do not exceed the resource capacity of the node and do not violate the ordered sequence of tasks. A node with task D may act as a root node in the tree.
Most of the existing literature I found online assumes either the total number of nodes in the final tree or the total number of edges in the tree is known beforehand. In my case, it is possible that only a single node may satisfy the required attributes and host all the required tasks, or a set of constraints may be needed to satisfy the required attributes.
Any hints or suggestions regarding how to formulate these constraints are highly appreciated.