1
$\begingroup$

I transform my minimization problem into one with only an objective function (no constraints). I only have one variable, which is binary.

  • Can I derivate the objective and make it equal to 0 to find the objective values?
  • If so, How? If you can send me an example, link, or a book to check how to derivate stuff like this, it would be amazing.

My objective function is as follows,

$$ \min_x \sum_{j\in J}\sum_{i \in I} C_{ij} \sum_{i'=\tau}^i X_{i'j} $$

Added:
Let $\tau=min(0,i-5)$ for example. And $X_{i,j} \in \{0,1\}$ with $i,j \in IxJ$.

$\endgroup$
4
  • 1
    $\begingroup$ Maybe this one can be helpful. $\endgroup$
    – A.Omidi
    Feb 28, 2022 at 10:30
  • 1
    $\begingroup$ Can you say something about the signs, domains and dimensions of the variables? $\endgroup$ Feb 28, 2022 at 15:15
  • $\begingroup$ Specifically, what is $\tau$ in the final summation? $\endgroup$
    – prubin
    Feb 28, 2022 at 15:26
  • $\begingroup$ Hi, X is binary with i,j in IxJ. And I 𝜏 is a function of i, should have fixed that. $\endgroup$
    – orpanter
    Mar 1, 2022 at 15:44

1 Answer 1

4
$\begingroup$

First order stationary point conditions will usually not help when your variables are discrete.

In this particular case, if $\tau$ is a constant (and assuming $x$ and $X$ are the same thing), the solution is trivial. Rewrite the objective as $$\min_X \sum_{i\in I : i \ge \tau}\sum_{j\in J} \left[ \sum_{k\in I : k\ge i} C_{kj} \right] X_{ij}.$$ Let $d_{ij} = \sum_{k\in I : k\ge i} C_{kj}.$ The optimal solution is found by inspection:$$X_{ij}=\begin{cases} 1 & d_{ij}<0\\ 0\textrm{ or }1 & d_{ij}=0\\ 0 & d_{ij}>0 \end{cases}.$$

$\endgroup$
2
  • $\begingroup$ Nice! I ended with something similar but was not sure it was good. Do you know where I can find a mathematical justification? Like a paper of book or theorem? I need to cite it for a paper. $\endgroup$
    – orpanter
    Mar 1, 2022 at 15:48
  • 1
    $\begingroup$ Sorry, no. I think I've encountered a mention in passing once or twice (an author pointing out the obvious solution), but I don't recall where, and in any case I would not consider such a mention worth citing. I would just state it in the paper as "obvious" or "by inspection". $\endgroup$
    – prubin
    Mar 1, 2022 at 17:58

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.