2
1

Hello All

I need to make a set of linear constraints to represent this problem:

There are two kinds of variables:
S = a free in sign continuous variable
Y = a 0-1 variable

Statuses are:
1. if S == 0, then Y should be 0, too.
2. if S <> 0, then Y should be 1.

The problem is that I need to model this statuses together in a set of linear constraints that work simultaneously. I wonder if any body knows an approach to figure this out.

Thanks
Anahita Esmaili
Student - Tehran University

asked 04 Aug '12, 13:44

a_esmaili's gravatar image

a_esmaili
213
accept rate: 0%

edited 17 Jan '14, 06:34

fbahr's gravatar image

fbahr ♦
4.6k716


Suppose \(L \leq S \leq U\) and we desire the following: $$ Y = \begin{cases} 0, & S = 0 \\ 1, & S \neq 0 \end{cases} $$ We relax this using \(\epsilon\) (a small positive number) as follows: $$ Y = \begin{cases} 0, & -\epsilon \leq S \leq \epsilon \\ 1, & \text{otherwise} \end{cases} $$

Formulation

We can use range constraints to model the above behavior: (range constraints are my go-to technique for these kinds of problems) $$ \delta_1 \epsilon + \delta_2 L + \delta_3(-\epsilon) \leq S \leq \delta_1 U + \delta_2 (-\epsilon) + \delta_3(\epsilon) $$ $$ \delta_1 + \delta_2 + \delta_3 = 1 $$ $$ Y = 1 - \delta_3 $$ where \(Y, \delta_3 \in \mathbb{R}\) and \( \delta_1, \delta_2 \in \{0,1\} \).

Check

If \(\epsilon \leq S \leq U\), this implies \(\delta_1 = 1, \delta_2 = 0, \delta_3 = 0\), therefore \(Y = 1\).

If \(L \leq S \leq -\epsilon \), this implies \(\delta_1 = 0, \delta_2 = 1, \delta_3 = 0\), therefore \(Y = 1\).

If \(-\epsilon \leq S \leq \epsilon \), this implies \(\delta_1 = 0, \delta_2 = 0, \delta_3 = 1\) therefore \(Y = 0\).

QED.

link

answered 04 Aug '12, 18:37

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 04 Aug '12, 18:55

A similar question, I see solvers provide feature of indicator variables and constraints. For example, if use cplex to model this one, it's something like:

IConstraint C1=CPLEX.EQ(S,0);
IConstraint C2=CPLEX.EQ(Y,0);
IConstraint C3=CPLEX.EQ(Y,1);
IConstraint C4=CPLEX.IFTHEN(C1,C2);
IConstraint C5=CPLEX.IFTHEN(CPLEX.NOT(C1),C3);

So C4 and C5 can be added into the IModel which I think also satisfy the requriement. However, I notice that in the manual of CPLEX, they encourage to use the indicator cosntraint rather than the big M or small epsilon approach as it may introcude "Numerical instability" (like here).

So the question is, how do they implement the indicator cosntraints? What do they mean by "numerical instability"?

link

answered 06 Aug '12, 02:14

jc%20W's gravatar image

jc W
258
accept rate: 0%

1

Numerical instability can be caused by having coefficients with large order of magnitude differences.

See this post for a nice explanation Making a singular matrix non-singular. Look for the explanation of condition number. Numerical instability means you have a large condition number, too large to warrant accurate results.

(08 Aug '12, 22:37) jfpuget
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:

×231
×127
×53

Asked: 04 Aug '12, 13:44

Seen: 2,075 times

Last updated: 17 Jan '14, 06:36

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