I have a linear integer model

$$ min sum_{iin N}(c_i x_i)\s.t. \ p_i s_ile x_i le s_i q_i,\ s_iin{0,1}\ sum_{iin N} x_i ge C\ ...$$

in which every (x_i) is either 0 or between (p_i) and (q_i). The model is actually more complicated, in particular there are costs associated to (s_i) as well, but what I'm trying to achieve is to quicly compute an heuristic solution, because instances are very large, e.g. I have (|N|>800,000), and clients need to get the solution in short time.

So I devised an iterative heuristic which uses an approximated decomposition of the problem into two submodels: a continuous and an integer one. At every iteration each submodel improves its approximation by using the information provided by the other model's previous solution.

So I relaxed the model in the continuous by removing the variables (s_i) and putting (x_i) between 0 and and (q_i). To get every (x_i) back in the range ({0}cup[p_i,q_i]) I considered adding the following constraints

$$ |x_i - frac{p_i}{2}|ge frac{p_i}{2}quadforall iin N $$

but the model wouldn't be convex any more. Do you know any alternatives or solutions for this kind of problem?


asked 29 Mar '12, 10:54

Andrea%20T's gravatar image

Andrea T
accept rate: 0%

edited 09 Jun '12, 10:36

Paul%20Rubin's gravatar image

Paul Rubin ♦♦


I'm not sure I understand: are you trying to model a semi-continuous variable without using integer variables? I'm not sure if that is possible. The semi-continuous domain (0 union [p,q]) is disconnected and therefore inherently non-convex. However, what you can do is to tell your solver that x is semi-continuous -- and it'll know how to handle it. (although most solvers will probably end up reformulating it into the MIP you wrote above)

(29 Mar '12, 19:30) Gilead ♦

what is it that you want to solve? the relaxation? your integer model looks just fine. does it help to "shift" the variables by (p_i), i.e., replace (x_i) by (x_i-p_i) everywhere, and adjust the bounds on the variables accordingly?


answered 29 Mar '12, 20:03

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%

edited 29 Mar '12, 20:10

Shifting wouldn't help because that would imply each (s_i) is fixed at 1 in the integer solution. I need the continuous model to give me a good guess of which (s_i) needs to be at 1.

(30 Mar '12, 04:28) Andrea T

ok, just to make sure: why don't you solve the integer program as you stated it? it seems to be an "easier" one for a solver...

(30 Mar '12, 04:33) Marco Luebbecke ♦

it's a small excerpt of a bigger and more complicated problem. The difficulty lies with the size of the problem and the variety of constraints. Long story short: clients want a solution (heuristic or exact) in short time and computing the integer variables directly takes too long. A reduced version of the model was fed to CPLEX and let it run for 10 days, after which the process was halted. For now I thank both of you for your attention and patience, and I apologize for the lack of clarity.

(30 Mar '12, 14:01) Andrea T
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 29 Mar '12, 10:54

Seen: 1,598 times

Last updated: 09 Jun '12, 10:36

OR-Exchange! Your site for questions, answers, and announcements about operations research.