Mathematics - GRAPH THEORY CPLEX problem

Problem 

Part 1: Scheduling   Consider the problem of scheduling a set of tasks, having arbitrary processingT n

times and availability dates on a single machine. Tasks must not overlap and cannotp i r i begin their execution before their dates of availability. A solution is characterized by a task permutation whose objective is to minimize the average

processing end time , where represents the processing end date of the task inin 1 ∑

n

i=1 C i C

position . i

1. Write the model of this problem in a .mod file and test this model with the given instance in Table 1.

i T 1T 2T 3T 4T 5T 6T 7T

i p 2 5 3 1 6 3 4

i r 1 0 2 4 3 1 0

Table 1 - An instance with 7 tasks

Considering the same problem where the objective is to minimize the total processing time of tasks; by in other words, minimize the maximum number of end dates for treatment of tasks

.max maxC = 1 ≤ i ≤ n Ci} {

2. Write the model of this problem in a .mod file and test this model with the instance given in Table 1.

Part 2 : Graph Theory  Covid-19 refers to "Coronavirus Disease 2019", the disease caused by a virus of the

Coronaviridae family, SARS-CoV-2. This respiratory disease can be fatal in patients who are frail due to age or other chronic diseases. It is ​transmitted through close contact​ with infected individuals.

Suppose that a group of people, stopped on the street, potentially had contact with infected individuals, however, at least one of them is known to be infected with the virus. After the evacuation of these individuals in the hospital, the doctors were able to list, for each individual, the people in that group with whom he had "close contact" (i.e., establishing a binary relationship between these individuals).

Doctors want to know the minimum number of people infected so that any individual in this group will be infected.

In order to model this problem, we are going to define a simple non-oriented graph of vertex , and , where each vertex (V , )G = E n V {1, .., } ( = . n (u, ) | u, })E ⊂ { v v ∈ V

represents a potentially infected person, and if the edge exists in , this means that peopleu, )( v u and v had "close contact. Thus, determining the minimum number of infected persons for any individual in this group to be infected means finding the minimum cardinality of a set ,S ⊂ V where each vertex of has at least one neighbor in , or even find a minimum subset of V S S V , such as (i.e., . This problem can be modeled as an integer (bivalent(S) S VN ⋃ = [S] V )N = variable) linear program. Illustrative example: Let a simple non-oriented graph, with and (V , ) G = E {1, , .., } V = 2 . 7

(K​1,6​ graph or star graph). {(1, ) | v 2, , .., }} E = v ∈ { 3 . 7

Figure 1 - An infected person can infect the group in the case of a

K​1.6​ graph.

If the graph modeling established by the doctors leads to the graph K​1.6​ ; it can be deduced that the number of infected persons is estimated between 2 and 7 positive cases. Similarly, we can intuitively see that they are all infected in the case of a complete graph. Moreover, in the case of a complete multiparty graphK​3.3.3​ , it can be seen that the number of infected persons is 7, 8, or 9.

Figure 2 - One infected person can infect the group in the case of a K​8​ graph, and a minimum of two people in the case of a K​3.3.3 ​graph.

1. Model this problem using graph theory and write the associated linear program. 2. Implement the LP in a .mod file using tables (i.e., adjacency matrix, incidence matrix),

then by tuples and sets. 3. Test these models with the following graphs: Peterson graph, full K​6​ graph, bipartite

graph, and a 4-level binary tree (written on .dat data files).

Figure 3 - A 4-level binary tree.

As already mentioned above, in the case of a complete graph K​n​ or a graph K​1,n​, an

infected individual (i.e., vertex) can infect the whole group (i.e., or all vertices of the graph).V Nevertheless, this number can be different for other classes of graphs. In addition, the doctors also want to know the maximum number of individuals ω, such that, all of these ω individuals will be infected, if at least one of them is infected. In other words, they are looking for a subset

of maximum cardinality , such as , the edge exists in theC ⊂ V |C|ω = u.v ∀ ∈ C u, )( v sub-graph of generated by (i.e., .G C u, , (u, ) )∀ v ∈ C ∃ v ∈ E ⋂C × C

4. Model this problem using graph theory and write the associated linear program. 5. Implement the PL in a .mod file using tables (i.e., adjacency matrix, incidence matrix),

then by tuples and sets. 6. Test these models with a graph of your choice. 7. Write a description of the results produced for these problems, and the conclusions that

can be drawn from them.