2
$\begingroup$

Consider the optimization problem

\begin{align} \max ~~ &x && \label{f}\\ \text{subject to}\ & \sum_{i=1}^{x} y_{i} = a && \label{s}\\ & y_{i} + y_{j} \ge b && \forall i,j \in \{1,\dots,x\} \text{ and } i \ne j \label{fd}\\ & y_{i} \in \{\ell,\dots,u\} && \forall i \in \{1,\dots,x\} \label{ad}\\ & x \in\{0,1,2,\dots\}. && \label{d} \end{align}

in which $x$ and $y_i$ are decision variables (unknowns) and $a$ and $b$ are given parameters. As can be seen, the decision variable $x$ is used in the $\sum$ notation. It is not hard to formulate this optimization problem as an integer linear programming formulation. The current form is good as it is more compact.

Question 1. Is it all right to write the formulation in such a form (using a decision variable in the $\sum$ notation)? Is it consistent with the common notation used in optimization community? Are you aware of possible optimization problems written similarly?

Question 2. According to INFORMS, a Semi-infinite program is "a mathematical program with a finite number of variables or constraints, but an infinite number of constraints or variables, respectively." I am wondering if the above problem could be called an "infinite program"?

Edit

As per comments, I modify the formulation by changing the domain of $y_i$ from $\{1,\dots,100\}$ to $\{\ell,\dots,u\}$ where $\ell$ and $u$ can take any non-negative integer values with $\ell < u$. I also add the following integer linear programming formulation of the problem. This is only one of different possible formulations.

\begin{align} \max \ &\sum_{k\in K} z_{k} && \label{A1_0}\\ \text{s.t.}\ &\sum_{k\in K}y_{k} = a && \forall k \in K \label{A1_1}\\ &y_{k} \le u\,z_{k} && \forall k\in K \label{A1_5}\\ &\ell\,z_{k} \le y_k && \forall k\in K \label{fggf} \\ &z_{k} \le y_k && \forall k\in K \label{fgf} \\ &y_{k} + y_{l} \ge b\,(z_{k}+z_{l}-1) && \forall k\in K, \, l\in K\setminus\{k\} \label{A1_6}\\ & y_{k} \in \{0,\dots,u\} && \forall k\in K \label{A1_7}\\ & z_{k} \in \{0,1\} && \forall k\in K \label{A1_8} \end{align}

In this formulation, $K:= \{1,\dots,v\}$ in which $v$ is an upper bound on the number of $y_i$ variables. In order for the problem to be a standard integer linear program, $v$ must be a given number. For example, if $\ell=1$ then we can simply set $v=a$. Note that for $\ell \ge 1$ the constraint $z_{k} \le y_k$ is redundant and can be eliminated from the model.

$\endgroup$
  • 1
    $\begingroup$ Independently of your questions, have you tried to find a closed form solution? I think this is possible. I have already solved some cases. Would be interesting if you also share your model as a MILP. $\endgroup$ – John D Sep 5 '17 at 11:39
  • $\begingroup$ Actually, the formulation I've written here is a simplified version of a bigger problem. I had to formulate this problem as a binary linear program from scratch since the original formulation is rather different (and I formulated it a long time ago). I agree that there is a closed form (I found one for the original problem) but I did not try to find a closed form solution for the above problem. $\endgroup$ – Opt Sep 5 '17 at 12:01
  • $\begingroup$ I asked this quesiton mainly because a university professor (whose field of study is operations research) mentioed that "You can't define an indexing set using a variable in the problem.". He mentioned that it is "non-standard". He somehow mentioned that this problem is not even semi-infinite because it does not follow the standard mathematical notation! I myself believe that a mathematical model should be as simple as possible, but It must be written in the standard language! $\endgroup$ – Opt Sep 6 '17 at 6:36
  • $\begingroup$ Well, sounds like your professor is a bit too married with the implementation and solution of the problem, instead of communicating the actual problem. It is a notation which clearly explains the model, but it does not explain the implementation or tractability. Your MILP model is the complete opposite, it is very standard and ready for implementation, but its purpose is hard to understand unless you've been told what it actually does. In a typical paper, you first explain the model on a high-level, and then you show how it can be reformulated to standard form. $\endgroup$ – Johan Löfberg Sep 7 '17 at 5:45
  • $\begingroup$ and I have doubts in your MILP model. To begin with $y_k \leq \ell$ is not correct as you lower bound is 1. Additionally, I see nothing in your model which prevents $z$ from having holes. Let $a = \ell = u = 1$, and the only feasible solution is to have 1 non-zero element in $y$ in its first element. Your model though allows us to place that 1 anywhere and have zeros in the first elements. $\endgroup$ – Johan Löfberg Sep 7 '17 at 6:03
2
$\begingroup$
  1. You can of course write it like this if you want as it is convenient and clearly shows what you want to optimize, but in the end you have to solve it, and the most likely way to do this is by a MILP solver, and thus you need to write it as a MILP

  2. There is a finite number of constraints and variables (as the length of $y$ is bounded), so calling it a (semi)-infinite dimensional problem would be weird.

$\endgroup$
  • $\begingroup$ Thanks Johan, but the number of $y_i$ variables would be as many as $x$ and $x$ has no explicit upper bound. Generally, the domain of $y_i$ has nothing to do with the number of them. $\endgroup$ – Opt Sep 5 '17 at 10:25
  • $\begingroup$ However, you may be able to perform a preprocessing and eliminate some redundant variables which is not the case here. $\endgroup$ – Opt Sep 5 '17 at 10:31
  • $\begingroup$ As $y_i$ cannot be smaller than $1$, you cannot have $x$ larger than $a$. $\endgroup$ – Johan Löfberg Sep 5 '17 at 10:38
  • $\begingroup$ I assumed that you already had that figured out, as you say it is easy to derive a MILP model, and such a model would require an explicit upper bound when deriving the model (unless you have some MILP model which I fail to see) $\endgroup$ – Johan Löfberg Sep 5 '17 at 10:40
  • $\begingroup$ Thank you for your comment. I edit the question by modifying the domain of $y_i$. However, it is a good point. Do we consider the possible preprocessing for a problem in categorizing it as a semi-definite program? In other words, we may be able to find an upper bound on the number of variables of the problem. Of course, such an upper bound would exist if the problem has a bounded solution. It is only a matter of time when we find it! $\endgroup$ – Opt Sep 5 '17 at 11:39

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.