1
$\begingroup$

I'm trying to solve this problem:

An investment agency holds the rights to six investment projects: I1, I2, ..., I6. Projects I1, I2 and I3 are research and technological development projects and the remaining three, I4, I5 and I6, are sustainable agriculture projects. The agency intends to form portfolios consisting of a research and technological development project and a sustainable agriculture project. Due to the risk associated with the projects, only the following pairs of projects are feasible: (I1, I4), (I1, I5), (I2, I4), (I2, I5), (I2, I6), (I3, I4) (I3, I5) e (I3, I6). The risk associated to each project, measured on a scale of 0 -10 (0 - no risk; 10 - maximum risk), and the number of portfolios in which each project may be included are shown in the table below:

enter image description here

a) Represent the problem in a network and identify the network model that allows the agency to determine how many portfolios of two projects it will be possible to define. Justify

b) Suppose now that the agency wants to determine the three portfolios of two projects that minimise total risk. Indicate all the necessary changes to be made to the network shown in a) and state the network model that allows the optimal solution to be determined. Justify.

Point a) I considered that it was a problem of maximum flow and I solved it this way (but I don't know if it's right). M is considered to be a large number. Above the arcs are their capacities (in this case, it represents the number of portfolios).

enter image description here

I don't know how to solve part b) and turn the network in part a) into a minimum cost flow problem. I don't know where to put it on the network that I can only have 3 portfolios.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Since this looks to be a homework, perhaps a few hints rather than the answer?

a) Check your network. How many edges should go from (i1,i2,i3) to (i4,i5,i6)? How many do you have?

b) You know this is a minimum cost flow, so you know you can have a general network structure and costs on the edges. So you have figured out that you somehow need to limit the flow in the network to at most three. Can you figure out how to make sure no more than 3 leaves s? In addition to costs on arcs, what in min-cost flow, what additional number is put on nodes? Depending on how this is taught, the solution will either be through the supply/demand on nodes or, if your min-cost flows always have conservation of flow at nodes, through an edge with the appropriate capacity.

Perhaps that will help?

Improve this answer
$\endgroup$
2
  • $\begingroup$ In point a) I corrected the scheme I made in the post. I added the arcs (I2,I6) and (I3,I4), because in total I need to have 8 arcs. Now would that be right? My problem is mainly in point b). I know that in the minimum cost flow problem, on top of each arc, the unit weight (in this case, the risk) and the capacity (in this case, the number of portfolios) are represented. But I don't know how to guarantee that only 3 portfolios arrive. In the scheme that I have I don't know how to do it. $\endgroup$
    – Carmen González
    Dec 31, 2022 at 11:46
  • $\begingroup$ This depends on exactly how your course defines min-cost flow (there are a few alternatives). If you go with the wikipedia definition at en.wikipedia.org/wiki/Minimum-cost_flow_problem then you have figured out the c's (capacity) and a's (cost) but you haven't defined d (the required flow). Other definitions have a supply/demand at every node. So re-lookup the definition in your course, and see which parameters you have not yet set. $\endgroup$
    – Michael Trick
    Dec 31, 2022 at 12:31
1
$\begingroup$

To convert to min-cost, you need to tweak this way:

  1. keep sink and nodes

  2. put 1 as weight on the graph, so a flow(r, a) of f(r,a) is anyway binary, r is research project and a is agriculture. Ensure to put flow(r,a) = flow(a,r) which implies $f_{i,j} = f_{j,i} \ \ \forall (i,j)$ pairs

  3. on nodes, demand as part of flow conservation is the number of portfolio the node appears.
    Like flow conservation will be
    $\sum_{j \in\ S_i} f_{i,j} \le N_i \ \ \forall i \in\ $projects,
    $f_{i,j}$ is the binary flow, $N_i$ is number of pairs $i$ can appear, $S_i $ is set of j nodes connected/adjacent to each i.

  4. Put demand at sink, s = 3 with an edge from all projects
    Then $\sum_{i} f_{i,s} = 3$

  5. $f_{i,s} \le \sum_{j \in\ S_i} f_{i,j} \ \ \forall i$: ensures before it makes an edge from a node to sink 1, that node must be in a portfolio pair selected.

Objective is then $\sum_i (r_i \sum_{j \in\ {S_i} }f_{i,j})$. Ensure to exclude sink node here.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.