Sunday, March 20, 2011

Semicontinuous Variables

This question pops up from time to time on various forums.  In a math programming model, how does one handle a variable that can either be zero or in some range not containing zero?  The mathematical description of the variable would be something like $$x\in {0} \cup [a,b]$$where $a>0$.  A couple of common applications in supply chain models include quantity discounts (a vendor offers a discounted price if you buy in bulk; $x$ is the amount purchased at the discounted price and $a$ is the minimum amount to qualify for the discount) and minimum lot sizes (where $x$ is the amount of a custom-made product obtained from a vendor who requires a minimum order of $a$ to justify the setup cost of the order).

The variable $x$ is known in math programming jargon as semicontinuous.  For whatever reason, the term is not well publicized; I taught a graduate course on integer programming for years without coming across it.  Some solvers can model these variables directly.  For instance, the C++ and Java APIs for CPLEX contain a class named IloSemiContVar.  I'm not sure which other solvers directly support semicontinuous variables. For solvers that do not recognize semicontinuous variables, there is a generic formulation.  You introduce a binary variable $y$ that will be 1 if $x$ is nonzero and 0 if $x$ is zero, and you add the contraints $x\ge ay$ and $x\le by$.

AMPL allows you to define a semicontinuous variable without explicitly adding constraints. Our example could be written in AMPL as -->
param a > 0;
param b > a;
var x in {0} union interval[a, b];
Currently, AMPL converts that into the pair of constraints mentioned above, even if the chosen solver is CPLEX.  Whether that will change in the future I do not know.

One potential virtue of directly modelling semicontinuous variables is that it may lead to a more parsimonious formulation.  If the solver understands semicontinuous variables, it can modify the branching logic to separate nodes based on $x=0$ versus $x\ge a$ without having to add the binary variable $y$ and the extra constraints.

9 comments:

  1. My 2 cents to add from past experience with the semi-cont approach in CPLEX on some practical examples.

    1. It is a cool and useful feature to have, but should be used with caution due to the 'big M' like structure hidden inside the resultant MIP.

    2. In many practical instances, the naive LP relaxation is weak.

    3. So, if possible, better to branch directly on the semi-cont. conditions (Nemhauser and Farias) rather than on the auxiliary binary variables x.

    ReplyDelete
  2. sorry, pt3 should read "... rather than on the auxiliary binary variables y".

    ReplyDelete
  3. @Shiva: Is it your impression that CPLEX inserts the auxiliary binary variable (and constraints) when it sees a semicontinuous variable? I thought it was branching on the condition (your third point). If so, that raises the question of how the sc variable's domain factors into LP relaxations prior to the branch (is it treated as having domain [0, b] until then, which would be my guess).

    ReplyDelete
  4. Yeah, that's what i thought. But i must confess that i used this feature practically 2-3 yrs ago, and it must have been least 2 versions prior to 12.x (we didn't have access to latest at that time). One would expect that by now, they would have implemented the best proven approach that can be practically integrated into an already complex code.

    Perhaps printing out the CPLEX-constructed .lp relaxation for a small example may give us a clue.

    ReplyDelete
  5. The LP relaxation apparently just treats the lower bound as zero. At least, if I set up a model with a semicontinuous variable and then add a conversion object to convert it to an ordinary float variable, the upper bound is preserved and the lower bound is set to zero.

    ReplyDelete
  6. Paul,

    I came across your blog just today. It is a great source for OR people. I am working as a OR specialist for a marketing company. What I would also like to see in your blog is a section for OR jobs that u come across through your friends. It would help lot of people searching for OR jobs.

    ReplyDelete
  7. @bharath: Thanks for the kind words. As it turns out, I'm among the last people on the planet to hear about OR job openings -- we don't offer any OR degrees here (we did 20+ years ago), so we don't have any recruiting for OR positions here. INFORMS has a "jobs bank" (http://www.informs.org/Build-Your-Career/OR-MS-Job-Bank), and there are occasional postings on LinkedIn either tagged OR or posted in the INFORMS group there. There was some discussion of job listings on OR-Exchange a while back, too.

    ReplyDelete
  8. @bharat I understand your request for OR job listing, sadly there are few (or none) really good listings. The information is squattered in various places and hard to find since the traditional key words is not really useful. Often companies look for other skills combined with OR.

    ReplyDelete
  9. @Jensen: I am more concerned with job search becasue, I faced lot of difficulties in getting an OR job. I still have some of my friends searching for a job in OR. It was very difficult for me to make an unknown person in linkedin to forward my resume. But, now I am not hesitating to forward someones resume. What they need is just an interview call through which they can prove themselves.

    ReplyDelete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.