Hello, now I have a problem, in which \(x\) is the binary variable, constant \(a \ge 0\), \(f(x)\) is a function of \(x\).

How to represent the following relationship:

If \(a \le f(x)\), then \(x=0\).

Do you have some ideas for the constraint above? Many thanks for that, it seems a bottle-neck in my current problem. I want to fix it. Thank you.

asked 10 Mar '15, 10:52

LinYuan's gravatar image

LinYuan
80617
accept rate: 0%

edited 10 Mar '15, 16:21

fbahr's gravatar image

fbahr ♦
4.6k716


One way to model this, is \( a \geq f(x) + \varepsilon - (1-x)M \). Sensible values for \( \varepsilon \) and \( M \) depend on your problem formulation though.

Note that when this constraint does not admit a conic representation (due to f(x)), you are solving a mixed integer nonlinear programming problem. These problems are generally challenging.

link

answered 10 Mar '15, 11:00

optimizer's gravatar image

optimizer
17615
accept rate: 6%

edited 10 Mar '15, 11:00

That is pretty good. I really appreciate that. When a<= f(x), this constraint requires x=0 exactly; while if a > f(x), it doesn't influence the value of x. In my problem, f(x) is a linear function of x. Thank you very much. Have a good day.

(10 Mar '15, 11:06) LinYuan

You might be able to apply what I wrote in Indicator Implies Relation to the contrapositive of your constraint (\(x = 1 \implies a \gt f(x)\)), with the usual necessity to relax the strict inequality a bit (or introduce an \(\epsilon\) gap as in what @optimizer wrote).

link

answered 10 Mar '15, 15:48

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

That is exactly what I want. According to the link, I find many related topics in your blog. Many thanks for the kind materials. They really help me a lot for my future research. For this problem, can we simply set ϵ=0 ?

(10 Mar '15, 21:31) LinYuan

Yes, because \(x\) binary implies \(f(x)\) takes only two possible values ... which also makes the constraint somewhat trivial. Let \(f_0 = f(0)\) and \(f_1 = f(1)\). Presumably you can compute these before solving the model. If \(f_1 \ge a\) then \(x\) must be 0. If \(f_1 \lt a \le f_0\), the constraint is vacuous (it basically says \(x = 0 \implies x = 0\)). If both values of \(f\) are less than \(a\), the constraint can never come into play.

(11 Mar '15, 10:46) Paul Rubin ♦♦
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:

×65
×27
×12
×6

Asked: 10 Mar '15, 10:52

Seen: 658 times

Last updated: 11 Mar '15, 10:46

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