2
1

In looking over the documentation for CPLEX (voluminous, and often hard to navigate) they describe (for example using Concert Technology) general logical constraints. They imply that they're implemented using indicator variables. That much I can see: For every inequality \(c \cdot x \le a\) one can define a 0/1 (indicator) variable \(y\) and add the two constraints \( y == 1 \Rightarrow c \cdot x \le a\) and \( y == 0 \Rightarrow c \cdot x > a \) (though I'm not sure how they deal with the strict inequality). Usually indicator constraints like \( y == 1 \Rightarrow c \cdot x \le a \) can be dealt with by using big \(M\) -- let \(M\) be an upper bound on \(c \cdot x\), and then add the inequality \(c \cdot x \le a + M(1-y)\). However, my impression, is that Cplex does something more sophisticated than this. At the very least I could imagine that the \(M\) could be modified dynamically, but I'm guessing that there's more to it than that. Can anyone shed some light on this?

asked 07 Sep '13, 13:43

VictorSMiller's gravatar image

VictorSMiller
343215
accept rate: 0%

edited 07 Sep '13, 13:45

1

I did find the following -- how SCIP handles indicator constraints: http://scip.zib.de/doc-2.0.2/html/cons__indicator_8c.html

(08 Sep '13, 12:38) VictorSMiller

I don't think CPLEX will modify M midstream. My impression is that CPLEX uses some (likely proprietary) internal logic to choose between doing a big-M formulation with its own estimate of M or enforcing the indicator constraint in the branching logic, but I may be wrong: it may always use branching logic. By branching logic, I mean that the indicator constraint is monitored but has no effect until branching makes the antecedent true, at which point the consequent is also enforced at that node (and any descendants). Done thus way, the constraint has no influence on node relaxations early in the tree, which is consistent with the "weak bounds" comment in the link Ehsan provided.

link

answered 09 Sep '13, 16:17

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

You forgot to mention that @VictorSMiller probably should also post this rather heavily technical question in IBM's CPLEX Optimizer forum – even if this would just mean you'd repeat your answer over there ;-)

(09 Sep '13, 16:34) fbahr ♦
1

@fbahr: I've posted the question in the Cplex Optimizer forum, as you've suggested.

(09 Sep '13, 16:52) VictorSMiller
2

@fbahr: Actually, I've been working hard on not repeating myself so much (a habit to which we geezers are prone).

(09 Sep '13, 17:00) Paul Rubin ♦♦
2

@Paul, I got this reply from Tobias Achterberg: https://www.ibm.com/developerworks/community/forums/html/topic?id=41d4c2a9-5bc0-4f65-b971-e614fee6a76a#c69693bd-6db6-476c-b239-fc00c19eaea4

It looks like you were pretty close to spot on. The only thing that he didn't explain is how indicators are used in separation. He just said that it isn't the same way that SCIP does it.

Here's a meta-question: is or-exchange more like math.stackexchange.com -- in that questions here are not supposed to be advanced research questions (or heavily technical)? If so, where is a better venue for those?

(10 Sep '13, 10:58) VictorSMiller
4

This is a fairly low volume site, so we're not too finicky about questions as long as (a) they visibly relate to OR (so new "where's a good place to eat in Podunk) and (b) they aren't of the "please do my homework for me" flavor. Questions that are specific to an individual software package and are particularly technical usually get better and/or faster results on software-specific support sites, but I wouldn't say they're unwelcome here (as long as the software is stuff some of us would use).

(10 Sep '13, 12:02) Paul Rubin ♦♦

@Paul, Thanks for the answer. I didn't know about the cplex specific site until it was pointed out to me. Even though I asked it about cplex (since they seemed have pioneered in having support for indicator constraints -- correct me if I'm wrong) it was meant for a general understanding of indicators. Given Cplex's reputation I thought that they might have the most advanced technology.

(10 Sep '13, 12:37) VictorSMiller
showing 5 of 6 show 1 more comments

The CPLEX official comparison of these two methods (available here) is a good start if you want to know which one you should select.

link

answered 07 Sep '13, 15:46

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

@Ehsan, Thanks. Although I'm certainly interested in which one I should select, what I'm really after is how the indicator variable contraint \( y == 0 \Rightarrow c \cdot x \le a \) is implemented. For example, are these constraints treated separately from the linear ones? And what's actually done to enforce them?

(07 Sep '13, 23:16) VictorSMiller
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×191
×2

Asked: 07 Sep '13, 13:43

Seen: 5,616 times

Last updated: 10 Sep '13, 12:37

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