2
$\begingroup$

Is there a mathematical optimization branch that explicitly tries to optimize this (type) problem?

$$\eqalign{ & \min \cr & \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + {J_2}s[i]*s[i + 1]*s[i + 2] + ... + {J_m}s[i]*s[i + 1]*...s[i + m])} \cr & s[i] \in \{ 0,1\} \quad \forall i \in \{ 1,2...,N + m\} \cr} $$

Currently, I only know things about Mixed integer programming (and its implementation using Gurobi)...

$\endgroup$

1 Answer 1

5
$\begingroup$

If the $s_{i}$ are integers, there are reformulations of integer polynomial terms that result in mixed-integer (linear) programs, at the cost of introducing additional variables and constraints. Fred Glover has a sequence of papers to that effect in the mid-to-late 1970s, and subsequent work has built upon it.

For example:

Fred Glover, "Improved Linear Integer Programming Formulations of Nonlinear Integer Problems", Management Science, 22(4), 455-460, 1975.

$\endgroup$
3
  • $\begingroup$ oh, thank you very much. Do you mind provide me with a link or a name of one of the paper? Thank you:) $\endgroup$
    – user40780
    Jul 21, 2014 at 20:48
  • 2
    $\begingroup$ If it's useful, upvote my answer. One big problem we have is that people post useful answers to questions, and then the answers are not upvoted, which discourages users from contributing. $\endgroup$ Jul 21, 2014 at 21:06
  • $\begingroup$ Actually, I will not hesitate to up vote if I have enough reputations :) $\endgroup$
    – user40780
    Jul 21, 2014 at 21:21

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.