The graph in the image represents the production sequencing on a machine with production capacity C in volume. Each node N represents a different product with a profit L per volume produced. Every time we pass through node N, a minimum volume of product must be produced. The objective is to maximize profit. Note, this is a generalization of the problem, what I'm interested in is a constraint that guarantees that an edge can be passed at most once. Also, does anyone know if there is a classic problem in the literature that covers the problem? The closest thing I came to was the vehicle and traveling salesman routing problem, but it's not quite the formulation I need, since nodes can be visited more than once. I know there is a way to turn the problem into a routing problem, but I wanted an efficient formulation specific to my problem.enter image description here

  • $\begingroup$ This sounds similar to a network flow problem. Have you read about those? $\endgroup$
    – Brannon
    Oct 5, 2023 at 13:36
  • $\begingroup$ It would help to see your attempt at formulating it (in particular what variables you are using). $\endgroup$
    – prubin
    Oct 5, 2023 at 15:14
  • $\begingroup$ It seem Eulerian trail (or Eulerian path) in graph theory, but you have to explain more. Each node has it own capacity, it product is part of the global product ? Exemple: does product of node 1 is the input of production for node 2 ? $\endgroup$
    – Issouf
    Oct 6, 2023 at 1:14
  • $\begingroup$ @Maria, do you mean by sequence is something like ($0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 0$)? Do you have predetermined sequences for all combinations of producing the products? Is it possible the start and the end node being different or should always being the same? $\endgroup$
    – A.Omidi
    Oct 7, 2023 at 20:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.