# Can an Operations Research model optimize on a vector's indexes?

Theoretical model Suppose that I have an input vector $$E_{t}\in\mathbb R^n$$ for $$n\in \mathbb N$$

Suppose that I want to optimize $$\displaystyle\max_{t,x} E_tx$$. That is, my decision variables are the vectors $$x$$ and $$t$$ of same dimension $$n$$. We optimize on the indexes of the input vector $$E$$.

Subject to some linear constraints $$Ax\le b_1$$ and $$Bt \le b_2$$, $$\quad (A,B)\in\mathcal M_{n,n}(\mathbb R)^2$$, $$(b_1,b_2)\in (\mathbb R^n)^2$$.

and some domain constraints: $$x\in \{0,1\}^n$$ and $$t\in\{1,\dots,n\}^n$$.

Is such model exist in any Operations Research formulation? MILP, ILP, MQLP etc.? The fact that the input vector is indexed by a decision variable is something I have not met yet.

Numerical example of such model would be:

$$n = 3$$

$$E = (5,-1,3),\quad \forall i \in \{1,2,3\}$$. Note that $$E_i$$ could be anything in $$\mathbb R$$.

$$\displaystyle\max_{t,x} E_tx$$

Without any constraint except domains constraints: $$x\in \{0,1\}^3$$ and $$t\in\{1,2,3\}^3$$.

An optimal solution here would be:

$$x=(1,1,1)$$ and $$t=(1,1,1)$$ which would give an objective of $$5\times 3 =15$$.

Numerical example with $$Bt\le b_2$$ of such model would be:

$$n = 3$$

$$E = (5,-1,3),\quad \forall i \in \{1,2,3\}$$. Note that $$E_i$$ could be anything in $$\mathbb R$$.

$$\displaystyle\max_{t,x} E_tx$$

Constraints

$$t_i\ge 2,\quad \forall i\in\{1,2,3\}$$
$$\sum x \le 2$$

Domain constraints: $$x\in \{0,1\}^3$$ and $$t\in\{1,2,3\}^3$$.

An optimal solution here would be:

$$x=(1,0,1)$$ and $$t=(3,2,3)$$ which would give an objective of $$3+3=6$$. There is another optimal solution of value $$6$$: $$x=(1,0,1)$$ and $$t=(3,3,3)$$

• What is the relation between $i$ and $t$? Are there the same things? It seems the value of the variable $t$ is defined based on $i$ in an ordinary sense! Jan 31 at 11:27
• @A.Omidi, I have changed my example to answer your question. $t$ and the values of $E_t$ are independant.
– JKHA
Jan 31 at 13:02
• What is the motivation for the $c t \le b_2$ constraint? Also isn't $b_2 \in \mathbb{R}$ instead of $\mathbb{R}^n$? Jan 31 at 22:03
• @RobPratt, I have edited my question accordingly. Does this answer your comment?
– JKHA
Feb 2 at 10:30
• In your example, $b_2$ is a vector but $c$ is a matrix. Feb 2 at 13:38

You can do this with ILP/MILP by using a binary variable $$y_{i,j}$$ indexed over $$\lbrace 1,\dots, n\rbrace \times \lbrace 1,\dots, n\rbrace,$$ where $$y_{i,j}=1$$ if and only if the $$i$$-th component of $$E$$ is matched to the $$j$$-th component of $$x.$$ Constraints on $$y$$ are $$\sum_i y_{i,j} = 1\, \forall j$$ and $$\sum_j y_{i,j} = 1\, \forall i.$$

Your objective function is $$\sum_{i,j} E_i x_j y_{i,j}.$$ The second solution in your example would correspond to $$y_{3,1}=y_{2,2}=y_{1,3}=1.$$ The objective is quadratic but easy to linearize (by introducing more variables). How to linearize the product of two binaries has been answered (a few thousand times, I think) elsewhere on this site.

• Thank you for your answer. How would you modelize that $ct \le b_2$?
– JKHA
Feb 2 at 10:12
• I have edited my question with an example for $ct\le b_2$
– JKHA
Feb 2 at 10:30
• $y_{i,j}=1 \iff t_j = i.$ So $c't = \sum_j \sum_i c_j\cdot i \cdot y_{i,j}.$
– prubin
Feb 2 at 16:35

This is a complement to the answer given by @prubin.

I will start by restating the definition you presented, just for conciseness.

Let

• $$E \in \mathbb{R}^{n^{n + 1}}$$ be a "matrix";
• $$t \in \mathbb{N}^{*n}_{\leqslant n}$$ be an index of $$E$$, thus $$E_t \in \mathbb{R}^{n}$$;
• $$A \in \mathcal{M}_{n,n}$$; And
• $$b_1, b_2, c \in \mathbb{R}^n$$.

The initial formulation was presented as:

$$\max$$ $$E_t^T x$$

s.t. $$A x \leqslant b_1$$ (1)

$$c^i t^i \leqslant b_2^i \quad\quad \forall i \in \mathbb{N}^{*}_{\leqslant n}$$ (2)

$$t \in \mathbb{N}^{*n}_{\leqslant n}\quad$$ (3)

$$x \in \mathbb{B}^n$$ (4)

MIQP formulation:

Let's consider the following variables.

• $$e^i \in \mathbb{R}$$ be a variable standing for $$E_t^i$$, such that $$t \in \mathbb{N}^{*n}_{\leqslant n}$$; And
• $$y_t \in \mathbb{B}$$ be a flag variable telling whether setting $$t$$ is selected.

$$\max$$ $$\sum_{i = 1}^{n} e^i x^i$$

s.t. (Constraints 1)

$$e^i = \sum_{t \in \mathbb{N}^{*n}_{\leqslant n}} y_t E_t^i \quad\quad \forall i \in \mathbb{N}^{*}_{\leqslant n}$$ (5)

$$c^i \sum_{t \in \mathbb{N}^{*n}_{\leqslant n}} y_t t^i \leqslant b_2^i \quad\quad \forall i \in \mathbb{N}^{*}_{\leqslant n}$$ (6)

$$\sum_{t \in \mathbb{N}^{*n}_{\leqslant n}} y_t = 1$$ (7)

(Constraints 4)

MILP formulation:

Now, we will linearize the previous objective function, and propose a MILP. Let's consider the variable $$z^i \in \mathbb{R}$$ be a variable standing for $$E_t^i x^i$$, such that $$t \in \mathbb{N}^{*n}_{\leqslant n}$$ and $$i \in \mathbb{N}^{*}_{\leqslant n}$$.

$$\max$$ $$\sum_{i = 1}^{n} z^i$$

s.t. (Constraints 1, 5, 6, and 7)

$$e^i - (1 - x^i) M \leqslant z^i \leqslant x^i M \quad\quad \forall i \in \mathbb{N}^{*}_{\leqslant n}$$ (8)

$$\quad\quad\quad\quad\quad\quad\quad\quad z^i \leqslant e^i \quad\quad \forall i \in \mathbb{N}^{*}_{\leqslant n}$$ (9)

(Constraints 4)

$$z \in \mathbb{R}^n$$ (10)

We can take the constant $$M$$ as the largest entry of $$E$$.

As a takeaway, I would say that the toughest part is on the number of variables $$y$$, since the scope $$t \in \mathbb{N}^{*n}_{\leqslant n}$$ easily explodes.

Let me know case there is any error.

• I called $E$ a "matrix" by not knowing better terminology, sorry but I'm not a mathematician ... Jan 31 at 21:57