Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 5 down vote accepted

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.

share|improve this answer
oh, thank you very much. Do you mind provide me with a link or a name of one of the paper? Thank you:) – user40780 Jul 21 '14 at 20:48
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. – Geoff Oxberry Jul 21 '14 at 21:06
Actually, I will not hesitate to up vote if I have enough reputations :) – user40780 Jul 21 '14 at 21:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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