\(\def\Real{\mathbb{R}}

\def\Comp{\mathbb{C}}

\def\Rat{\mathbb{Q}}

\def\Field{\mathbb{F}}

\def\Fun{\mathbf{Fun}}

\def\e{\mathbf{e}}

\def\f{\mathbf{f}}

\def\bv{\mathbf{v}}

\)

Set \(d=18\).

Consider the \(d\times d\) matrix

\[

C=\left(c_{ij}\right)_{i,j}

\]

where

\[

c_{ij}=a_{ij}+n_i-n_j.

\]

The base matrix of coefficients \(a_{ij}, 1\leq i,j\leq d\) is given here; the modifier \(n_j\) is the \(j\)-th digit of your UID squared.

In the following assignment, use simplex method.

#### 3 credits students

Find the least cost bipartite matching where the cost are given by the coefficients \(c_{ij}\), – that is find the permutation \(\sigma=(\sigma_1,\ldots,\sigma_d)\) such that

\[

\sum_{i=1}^d c_{i \sigma(i)}\to\min.

\]

Hint:Use the Birkhoff-von Neumann theorem that the permutation matrices

\[

P_\sigma=\left(p_{ij}\right), p_{ij}=\delta_{\sigma(i)j}

\]

are the vertices of the polyhedron of doubly stochastic matrices

\[

\left\{(p_{ij})_{1\leq i,j\leq d}:\sum_i p_{ij}=1, 1\leq j\leq d; \sum_j p_{ij}=1, 1\leq i\leq d; p_{ij}\geq 0, 1\leq i,j\leq d\right\}

\]

#### 4 credits students

Find the scalar ranking \(r_i, 0\leq i\leq d\) best approximating the tournament \(c_{ij}\) in \(l_\infty\) norm, i.e. minimize

\[

\max_{i,j} \left|c_{ij}-(r_i-r_j)\right|.

\]

Submit your results (code, answers) by midnight of April 25.

Hi Professor, we are required to use simplex to solve these problems. Should we implement the simplex method ourselves, or we can use some existing simplex modules? Thanks!

Of course use the existing solvers.

Hi, Professor, what is the value of d and c in the credit 4 problem? Do we initialize them by ourselves?

You initialize them by parsing the exercise text.

In the second problem, should that be min instead of max?

No.

but in the question, you said ” i.e. minimize”, which is confusing

Minimize the functional defined as max. Happens.

Can we use the MATLAB build-in function linprog() to solve the linear programming?

Use any standard software.

Hello Professor, I didn’t quite get the definition of scalar ranking. Could you give an example of it? Thanks!

Example: A -> 5.23; B-> 7.92; C-> -.43 is a numerical ranking: B best, A middle, C worst.

Hi, professor. In the 3 credit question the coefficients are costs, but some of them are negative, is that practical, or should we use the absolute value?

You can shift all the costs by an equal amount, if you prefer: this will make them all positive (if you add some large enough constant to the costs) not affecting the optimal matching.

In short – no, do not replace by absolute values.

In the question we are asked to use nj as the jth digit if our UID squared. But the problem is our UID is only a 9 digit number but the value of j goes till 18 since our d is 18. So, you want to take our UID twice consecutively so that we can get 18 digits in total.

j-th digit of {UID squared}. Square the UID, not the digit.

Shouldn’t i, j be from 1 to d, instead of from 0 to d? Thanks.

You’re right, thank you! corrected.

Hi Professor, for the 4-credit problem, is it required that scalar ranking ri should be non-negative?

No, not necessarily (adding to all scalar ranks the same number won’t change the value of the objective function, right?).