programming exercise 2


Set \(d=18\).

Consider the \(d\times d\) matrix
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.

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 #


    • 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?).

Leave a Reply