programming exercise 2

$$\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|.$

20 Responses to programming exercise 2

1. Ann April 11, 2016 at 2:06 pm #

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!

• yuliy April 11, 2016 at 3:21 pm #

Of course use the existing solvers.

2. Chen April 11, 2016 at 6:08 pm #

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

• yuliy April 12, 2016 at 8:14 am #

You initialize them by parsing the exercise text.

3. Chen April 11, 2016 at 6:12 pm #

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

• yuliy April 12, 2016 at 8:13 am #

No.

• Chen April 13, 2016 at 3:34 pm #

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

• yuliy April 17, 2016 at 11:46 pm #

Minimize the functional defined as max. Happens.

4. Chen April 11, 2016 at 9:28 pm #

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

• yuliy April 12, 2016 at 8:12 am #

Use any standard software.

5. Jie April 15, 2016 at 4:30 pm #

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

• yuliy April 17, 2016 at 11:47 pm #

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

6. Zhongyuan Fang April 16, 2016 at 11:56 pm #

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?

• yuliy April 17, 2016 at 11:49 pm #

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.

7. Ravi April 17, 2016 at 9:48 am #

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.

• yuliy April 17, 2016 at 11:50 pm #

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

8. Ted April 20, 2016 at 9:19 am #

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

• yuliy April 21, 2016 at 2:17 pm #

You’re right, thank you! corrected.

9. Ann April 21, 2016 at 12:28 pm #

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

• yuliy April 21, 2016 at 2:15 pm #

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