Required Tasks

$(1)$ For Instance $1,$ consider Scenario $1$ where $\backslash ($ m$=2\backslash ).$ The goal is to find $8$ pairs of workers that maximize the total synergy. Formulate the problem as an integer programming model. Define the decision variables and constraints clearly. Solve the model using AMPL with dataset.dat file. What is the optimal partition $(8$ pairs of workers$),$ and what is the corresponding objective function value?

$(2)$ For Instance $1,$ consider Scenario $2$ where $\backslash ($ m$=4\backslash ).$ The goal is to form $4$ teams of workers, each consisting of $4$ workers, to maximize the total synergy among team members. Formulate the problem as an integer programming model. Define the decislon variables and constraints clearly. Solve the model using AMPL with dataset. dat file. What is the optimal partition $(4$ teams, each consisting of $4$ workers$),$ and what is the corresponding objective function value?

$(3)$ For Instance $2,$ you will solve the same optimization problems as in $(1)$ and $(2),$ but using the

dataset hard.dat file.

$-$ Scenario $1$: $\backslash ($ m$=2\backslash ).$ The goal is to find $20$ pairs of workers that maximize the total synergy.

You

should be able to get an optimal solution in a reasonable time.

$-$ Scenario $2$: $\backslash ($ m$=4\backslash ).$ The goal is to form $10$ teams of workers, each consisting of $4$ workers, to maximize the total synergy among team members.If the code runs for more than $30$ minutes, interrupt it and report the best solution you found. Summarize your findings.

$(4)$ Solving for Scenario $\backslash (2($m$=4)\backslash )$ in $(3)$ may take significantly more time than for $\backslash ($ m$=2\backslash ).$ One possible approach to address this problem is to use the optimal pairs derived from Scenario $1\backslash (($m$=2)\backslash )$ and pair those pairs in a second step. This heuristic, called Double$-$Pairing Algorithm, works as follows:

$($a$)$ First, solve Scenario $1$ optimally, which will yield $20$ pairs $($first pairing$).$

$($b$)$ Next, we will optimally pair these pairs. Each pair consists of two workers, and when two pairs are combined, we have four workers. For instance, if workers $1$ and $2$ form pair $\backslash ($ A $\backslash ),$ and workers $3$ and $4$ form pair $\backslash ($ B $\backslash ),$ merging pairs $\backslash ($ A $\backslash )$ and $\backslash ($ B $\backslash )$ assigns workers $1,2,3,$ and $4$ to the same team. The synergy between two pairs $($e$.$g$.,$ between pair $\backslash ($ A $\backslash )$ and pair $\backslash ($ B $\backslash ))$ is defined as the sum of all relevant synergy values:

$\backslash [$

c A$,$ B$=$c $1,2+$c $1,3+$c $1,4+$c $2,3+$c $2,4+$c $3,4.$

$\backslash ]$

This creates an instance with $20$ "workers" $($where each "worker" corresponds to a pair$)$ and updated synergy values $($second pairing$).$

$($c$)$ Finally, solve the problem in Scenario $1$ for the $20$ pairs. This will result in $10$ pairs of pairs.

Based on these pairs of pairs, reconstruct the teams of $4$ workers. Implement Double$-$Pairing Algorithm in AMPL, which may require more than two $\text{'}.$mod'files and new $\text{'}.$dat' file. Report the objective function value from the output of the algorithm.

Discuss what this solution suggests about the optimal value for the original problem with $\backslash ($ n$=40\backslash )$ and $\backslash ($ m$=4\backslash )$