3
$\begingroup$

The following problem has only two integer variables; however, they appear in the index of the parameters. Appreciate it if anyone has any efficient idea to transform it into a canonical integer programming model.

$$ \begin{alignat*}{2} &&\max \quad & (d_y - d_x)^2 \\ &&\text{s.t.} \quad & d_y - d_x \geq \alpha \\ && & x,y \in \mathbb{Z}_+ \\ \end{alignat*} $$

Improve this question
$\endgroup$
  • $\begingroup$ $d:\mathbb{Z}_+ \to \mathbb{R}$ is a fixed sequence? $\endgroup$ – RobPratt Aug 18 '20 at 17:34
  • $\begingroup$ @RobPratt. Yes. $\endgroup$ – Mohammad Namakshenas Aug 18 '20 at 17:37
  • $\begingroup$ OK, canonical integer programming does not allow an infinite amount of input. Do you have any upper bound on $x$ and $y$? Or maybe a formula that defines $d$? $\endgroup$ – RobPratt Aug 18 '20 at 17:45
  • $\begingroup$ @RobPratt. Yes. We have upper bounds on $x$ and $y$. $\endgroup$ – Mohammad Namakshenas Aug 18 '20 at 17:59
3
$\begingroup$

Suppose $x,y\in\{0,\dots,n\}$. I think I would just loop over these $(n+1)^2$ pairs and keep the best one that satisfies the constraint.

But if you insist on integer programming, introduce binary variables $x_i$ and $y_i$ for $i\in\{0,\dots,n\}$, with the interpretation that $d_x=\sum_i d_i x_i$ and $d_y=\sum_i d_i y_i$. The problem is to maximize $$\left(\sum_i d_i (y_i - x_i)\right)^2$$ subject to \begin{align} \sum_i x_i &= 1\\ \sum_i y_i &= 1\\ \sum_i d_i (y_i - x_i) &\ge \alpha \end{align} If you want, you can linearize the objective.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer. Do you have any alternative for integer programming? $\endgroup$ – Mohammad Namakshenas Aug 18 '20 at 18:49
  • 2
    $\begingroup$ In constraint programming, you can use element constraints to use a variable as an index. $\endgroup$ – RobPratt Aug 18 '20 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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