3
$\begingroup$

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)$

$\endgroup$
6
  • 2
    $\begingroup$ 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! $\endgroup$
    – A.Omidi
    Jan 31 at 11:27
  • $\begingroup$ @A.Omidi, I have changed my example to answer your question. $t$ and the values of $E_t$ are independant. $\endgroup$
    – JKHA
    Jan 31 at 13:02
  • $\begingroup$ 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$? $\endgroup$
    – RobPratt
    Jan 31 at 22:03
  • $\begingroup$ @RobPratt, I have edited my question accordingly. Does this answer your comment? $\endgroup$
    – JKHA
    Feb 2 at 10:30
  • $\begingroup$ In your example, $b_2$ is a vector but $c$ is a matrix. $\endgroup$
    – RobPratt
    Feb 2 at 13:38

2 Answers 2

4
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.