Disjunctive absolute value inequalities in convex linear programs

 1 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 384●4●18 accept rate: 0% Paul Rubin ♦♦ 14.6k●4●12 2 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 ♦

 0 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 Luebbecke ♦ 3.4k●1●6●15 accept rate: 16% 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
 toggle preview community wiki

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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

Tags:

Asked: 29 Mar '12, 10:54

Seen: 1,598 times

Last updated: 09 Jun '12, 10:36

Related questions

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