Can this optimization problem be modeled in CVX?


(Dipak Narayanan) #1

W=16, M=4 and {\bf{L}}\in\mathbb{R}^{N\times P} is a known matrix.

\alpha and \beta are integer variables of length N.

[{\bf{L}}]_{i,:} defines the $i$th row of matrix {\bf{L}}

\begin{equation}
\begin{array}{*{35}{l}}
\min ||W{\bf{d}}-{\bf{s}}||2\
\text{}\text{subject to} \hspace{3mm}{\bf{s}}=\sum
{i=1}^{N}[{\bf{L}}]{i,:}\gamma_i.\
\text{}\hspace{16mm}\sum
{i=1}^{N}\alpha_i=M.\
\text{}\hspace{16mm}\gamma_i=\alpha_i\beta_i\
\text{}\hspace{16mm}\sum\gamma_i=W\
\text{}\hspace{16mm}1\le\beta_i\le 13\
\text{}\hspace{16mm}\text{if }\alpha_i>1, \text{ then }\beta_i\ge 2\alpha_i
\end{array}
\end{equation}


(Mark L. Stone) #2

I can’t even quite figure out what your problem specification is. it appears that you have a product of integer variables which will have to be dealt with. if worse comes to worse, presuming there are finite lower and upper bound on these variables, you might be able to “ilnearize” this using binary encoding, as shown at https://www.quora.com/How-do-I-convert-a-constraint-with-a-product-of-two-integer-variables-to-a-linear-constraint-1 . Because i’m not sure exactly what your problem specification is, I don;t know whether there are any other matters which need to be dealt with.


(Dipak Narayanan) #3

Thank you very much. This problem is very similar to Can this be solved in CVX?, with some additional requirements. I have demand vector \bf d. The matrix \bf L has N(=64) rows and P(=72) columns. Each row in \bf L has some supply. My target is to find M rows of \bf L such that the summation of these M vectors satisfies the demand. The vector \alpha_i is an integer variable gives the the index as well as the number of times a particular row in \bf L is chosen. If the row 2 is one of the M rows and is chosen just once then \alpha_2=1. If it was chosen twice then \alpha_2=2.

Now, the supply provided by the each row in \bf L is defined for unit time. The time unit can be second, millisecond or even minute. In this problem , we want to minimize the norm of the difference vector \bf d-s over W(=16) units of time. There are total M opportunities to select the rows. The scheduler selects the rows (M times) within the given cycle of W units of time.

The supply from any selected row (on one of the M different occasions) should last for at least one unit of time. Therefore, the supply from any selected row can last for maximum 13 units of time.

So, in this problem, I need to find the index of the selected rows (\alpha_i)'s and the duration of each selected row so that the norm is minimized.


(Mark L. Stone) #4

Is there a constraint \gamma_i == \alpha_i \beta_i for each i , in which both \alpha_i and \beta_i are optimization (i.e., decision) variables?

I suppose this makes sense to you, but to me your problem specification is just a bunch of mumbo jumbo which I don’t have the energy to try to figure out.


(Dipak Narayanan) #5

I understand that the last reply was a bit unstructured and difficult to follow. Just to put it in simple words, I have M opportunities to select rows of \bf L. I can select the same rows twice. The minimum and maximum duration of any selected row is 1 and 13, respectively.

\min ||W{\bf{d}}-\gamma{\bf{s}}||_2

\gamma is a vector of decision variable of length N.

\sum_{i=1}^{N}\gamma_i=16 and 1\le \gamma_{\text{index of selected rows}} \le 13 (integers only)

There are only M non-zero elements in \bf \gamma vector (here we somehow select different rows in different instants, no row is selected twice.)


(Mark L. Stone) #6

I’ll let you look at " MIP formulations and linearizations Quick reference" by FICO https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf to figure it out.

A great resource for conic optimization modeling,which has some some integer material, is the “MOSEK Modeling Cookbook” https://docs.mosek.com/modeling-cookbook/index.html , which will greatly help you use CVX (even if you don’t use Mosek, but please don’t tell @Erling I said that).

You’ll probably benefit from putting in the effort to work through “Model Building in Mathematical Programming”, 5th Edition by H. Paul Williams https://www.wiley.com/en-us/Model+Building+in+Mathematical+Programming%2C+5th+Edition-p-9781118443330 . This ought to really help you do effective integer modeling and formulation.


(Erling D.Andersen) #7

One our competitors told me that they used the cookbook a lot. That is fine for us.