I have an almost linear program I want to solve. But I encounter a problem with the condition, that either of two continous variables has to be zero (if a ~= 0 then b =0, if b ~= 0 then a =0).

An easy, but non-linear way to implement this would be a*b = 0. If anybody knows a way to linearize this with linear equality and/or inequality constraints, I would be really thankful.

Best regards, Marlon

asked 19 May '15, 09:01

Sillywumps's gravatar image

Sillywumps
111
accept rate: 0%


There is a name for what you are trying to model: complementarity.

I assume you have more than one pair of variables. Otherwise, just solve two problems. Unfortunately, while you can apply the trick that Slavko and Paul suggested above, you should not expect great performance in practice if you have very many variable pairs. You are better off taking a second look at the model and trying to improve the formulation along other directions.

There are, however, special cases under which these problems behave well. The Linear Complementarity Problem is as good as any a place to start.

link

answered 20 May '15, 05:44

Leo's gravatar image

Leo
1.1k17
accept rate: 8%

Unless the range of a or b extends to positive and negative values. I'll leave it as an exercise to the reader what to do in that situation.

(20 May '15, 11:54) Mark L Stone

If \(\epsilon\) is sufficiently small number, and \(M\) large enough, and \(u_i\) are binary, I can write constraints as follows.

\[ \begin{cases} & a \geq -M\cdot u_1 +\epsilon\cdot u_2 \\ & a \leq M\cdot u_2 -\epsilon\cdot u_1 \\ & b \geq -M\cdot u_3 +\epsilon\cdot u_4 \\ & b \leq M\cdot u_4 -\epsilon\cdot u_3 \\ & \sum u_i = 1 \end{cases} \]

link

answered 19 May '15, 10:26

Slavko's gravatar image

Slavko
20515
accept rate: 12%

edited 19 May '15, 10:27

1

This is fine for the "exclusive or" interpretation, with the usual proviso that neither \(a\) nor \(b\) can belong to the open set \((-\epsilon, 0) \cup (0, \epsilon)\). For the "inclusive or" interpretation (where \(a\) and \(b\) could be zero simultaneously), only one binary variable \(u\) is needed.

(19 May '15, 15:24) Paul Rubin ♦♦

I thank You for your comment, dear Professor. For the "inclusive or" interpretation I can write following conditions.

\[ \begin{cases} & -M\cdot u_1 \leq a \leq M\cdot u_2 \\ & -M\cdot u_3 \leq b \leq M\cdot u_4 \\ & \sum u_i \leq 1 \end{cases} \]

or

\[ \begin{cases} & -M\cdot u_1 \leq a \leq M\cdot u_1 \\ & -M\cdot u_2 \leq b \leq M\cdot u_2 \\ & u_1+u_2 \leq 1 \end{cases} \]

(20 May '15, 04:11) Slavko
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
×65
×16

Asked: 19 May '15, 09:01

Seen: 756 times

Last updated: 20 May '15, 12:00

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