Hello, OR experts,

Now I want to express the following constraint:

A series of binary variables \(x_1, x_2, x_3,...\) satisfy \[\sum\limits_i {x_i} = 1\] But I want to set the one with the smallest indice to 1, i.e., \(x_1 = 1\). What I am thinking is to assign a weight to each variable, e.g., \(c_i\) to \(x_i\) satisfying \(c_i < c_{i-1}\), then add a constraint like this: \[c_i x_i \leq \sum\limits_j {c_j x_j}, \forall i\]

But it doesn't work. Do you have some ideas to express this in a constraint (not in the objective)?

Thank you very much.

asked 23 Jun '15, 17:32

LinYuan's gravatar image

LinYuan
80617
accept rate: 0%

edited 23 Jun '15, 17:36

Something about your problem statement doesn't make sense. The only solution is x=(1,0,0,...,0).

(23 Jun '15, 17:40) Austin Buchanan

@Austin Buchanan, Yes, that is right. Since in my problem, to break ties, I want to set the binary variable with the smallest indice to be 1 only. Then in a case, may be \(x_2, x_5, x_9\) satisfy all the constraints, but I want to set \(x_2 = 1\).

(23 Jun '15, 17:48) LinYuan

So your constraint is \( \sum_{i \in C} x_i =1\) for some \(C\subseteq {1,2,\dots, n}\)? Is your set C not part of the input to the problem?

(23 Jun '15, 17:51) Austin Buchanan

@Austin Buchanan, Yes, thank you for pointing it out. The set \(C\) is not an input to the problem, it is determined by the solving process. For example, now the optimal solution to my problem may be \(x_3 = 1\), or \(x_5 = 1\), or \(x_9 = 1\), since these three cases have the same objective value. To break ties and output a stable solution, I want to set the variable with the smallest indice to be 1, i.e., \(x_3 = 1\). So an additional constraint is required. Do you have some ideas for this constraint? Thank you very much.

(23 Jun '15, 19:53) LinYuan

I don't see how this can be done without more information. How is C determined via the solving process?

(23 Jun '15, 22:04) Austin Buchanan

@Austin Buchanan, I want to make the question simple, so I omit more details. See if this helps. we have another linear constraint: \[f(x_i) \leq g(x_i), \forall i \in I\] The set of indices that satisfy the constraint above is \(C \subset I\). Then I want to choose the one in set \(C\) that have the smallest indice.

(23 Jun '15, 22:16) LinYuan

Is your tie breaking part of the problem, or part of the solution process (as in symmetry breaking)? Maybe you could enforce the rule also during the branching?

(24 Jun '15, 03:21) rschwarz

In the new expression of the problem (\(C = \{i : f(x_i)\le g(x_i)\}\)), is \(x_i\) the same binary variable that you earlier said satisfied \(\sum_{i\in C}x_i = 1\)? This implies that exactly one of the inequalities will be satisfied (i.e., \(C\) is guaranteed to be a singleton).

(24 Jun '15, 17:35) Paul Rubin ♦♦

@Paul Rubin, In my problem, \(C\) may have multiple elements. I don't know how to express my problem more mathmetically. My problem is a kind of maximal covering location problem. I use constraints to represent the greedy adding algorithm. In each iteration, the facility that can capture the largest demand is open. In one iteration, two facilities may capture the same demand. In this case, I want to open the one with the least indice. The greedy algorithm is expressed using some constraints. C is the facilities that have the same maximizers. Dr Rubin, do you have ideas for this case? Thanks.

(25 Jun '15, 10:04) LinYuan
showing 5 of 9 show 4 more comments

I'm still not sure if I am understanding the problem correctly, but possible what I posted here might help.

link

answered 25 Jun '15, 11:30

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Maybe you want to solve two problems.

First, solve your problem only with the original constraints.

Then, add the expression for the objective of the original problem as a constraint, bounded by no worse than whatever the objective value you obtained. Now solve a new problem replacing the original objective with \( \min i*x_i \).

link

answered 23 Jun '15, 23:40

Leo's gravatar image

Leo
1.1k17
accept rate: 8%

edited 23 Jun '15, 23:41

Dr Leo, thanks for youe idea. Yes, this is a good alternative. I think this will work. But I prefer to express the issue directly using constraint, so that my model may be solved only once. Thank you. I think my problem is like this. Given binary variable \(x_1, x_2\) satisfying \(x_1 + x_2 =1\) and \(2_x1 + 3x_2 \geq 2\). I want to set \(x_1 = 1\) only. Since now the set \(C\) is clearly defined, we can always impose by \(x_1 \geq x_2\). However, in my real problem, the \(C\) is only known according to other constraints. See my comment to Dr Rubin above.

(25 Jun '15, 10:09) LinYuan
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:

×37
×25
×6

Asked: 23 Jun '15, 17:32

Seen: 621 times

Last updated: 25 Jun '15, 11:30

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