Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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

1 Answer 1

up vote 4 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 at 20:48
2  
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 at 21:06
    
Actually, I will not hesitate to up vote if I have enough reputations :) –  user40780 Jul 21 at 21:21

Your Answer

 
discard

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.