How does one deal with Mixed integer linear programs where one bunch of variables takes values from a set. Example

\(x \in \{1,2,3,4\}\), \(y \in \{0.5,0.6,0.8\}\) and other variables are integer or continuous.

Thanks in advance,

asked 17 Jun '14, 01:17

pondy's gravatar image

pondy
434
accept rate: 0%

edited 17 Jun '14, 05:14

fbahr's gravatar image

fbahr ♦
4.6k716


There might be more efficient ways, but a simple one to implement is to define binary variables for each variable and have the binary variables multiplied by their corresponding values. You should also add a constraint that enforce selecting at most one of the binary variables (i.e., values).

For example, for \(x\) you would have binary variables \(w_1\), \(w_2\), \(w_3\), and \(w_4\). To represent \(x\) in the objective function or a constraint, you would write \(w_1+2w_2+3w_3+4w_4\). Finally, you should add the constraint \(w_1+w_2+w_3+w_4 \le 1\).

Please note that this does not work well with large problems that have many discrete variables as you have described.

EDIT (Thanks to @Sune): The inequality in the constraint \(w_1+w_2+w_3+w_4 \le 1\) assumes that zero is also part of the acceptable values. If that's not the case, then you should use the equality version.

link

answered 17 Jun '14, 02:30

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 17 Jun '14, 07:49

2

Minor comment: maybe you even need an equality instead of the "less than one" if the variable has to take a value in the set. Otherwise x might take a value of zero if it is optimal to have it at its lower bound.

(17 Jun '14, 04:03) Sune

@Sune: Good point. If the \(x\) does not take zero as its value, the formulation could be improved by removing the first the binary variable.

(17 Jun '14, 04:31) Ehsan ♦

Perhaps we are just thinking of different ways of formulating it, but I think equality is required if x wants to be at its lower bound. Take for example \(\min\{ x:x\in \{ 1,2,3,5,8\}\}\). The optimal value is clearly 1. If we formulate that as \( \min w_1+2w_2+3w_3+5w_4+8w_5 \text{ such that: } w_1+w_2+w_3+w_4+w_5\leq 1 \text{ all binary}\) the optimal value will be zero. However, if we use an equality, we find the right solution, namely \(x=1\).

(17 Jun '14, 07:26) Sune

@Sune: I think we're on the same page. If \(0\) is not part of the acceptable values for \(x\), then equality is necessary for the constraint.

My point in the previous comment was that if the minimum acceptable value for \(x\) is \(1\) and not \(0\), then you could write \(x\) as \(1+w_2+2w_3+4w_4+7w_5\) in constraints and just add the constraint \(w_2+w_3+w_4+w_5 = 1\).

(17 Jun '14, 07:43) Ehsan ♦

@Ehsan: Then we are indeed on the same page!

(17 Jun '14, 08:59) Sune
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
×101
×4

Asked: 17 Jun '14, 01:17

Seen: 1,067 times

Last updated: 17 Jun '14, 10:03

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