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

Improve this question
$\endgroup$
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.

Improve this answer
$\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 '14 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$
    – Geoff Oxberry
    Jul 21 '14 at 21:06
  • $\begingroup$ Actually, I will not hesitate to up vote if I have enough reputations :) $\endgroup$
    – user40780
    Jul 21 '14 at 21:21

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.