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? TIA asked 29 Mar '12, 10:54 Andrea T Paul Rubin ♦♦ 
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_ip_i) everywhere, and adjust the bounds on the variables accordingly? answered 29 Mar '12, 20:03 Marco Luebbecke ♦ 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 ♦
1
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

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