I am dealing with a situation similar to the one described here but a complex version of the same.

Using the same problem setting from the other thread, my constraint goes as follows : If patient i1 is treated by doctor j, I want the same doctor to treat patient i2 as well. I will have a pre-processing routine to identify (i1,i2) pairs. I can easily handle this with an additional constraint, but given the sizes of I and J, I would like to handle this as a penalty/incentive in the objective function. In this case, my objective is (-p*sum_i sum_j |x_{i2,j}-x_{i1,j}|)

It is also possible that this constraint can be violated with a penalty. For example, if (i1,i2) and (i1,i3) are predecessor-successor patient pairs but i2&i3 overlap(in time dimension), doctor j can treat only one of i2 or i3. So my constraint is x_{i1,j} <= x_{i2,j}+x_{i3,j}

The rest of my constraint matrix is structured such that the MIP solves in the root node, but this constraint causes the MIP to go into Branch & Bound. Hence trying to model it in the objective itself.

Any thoughts on this?

Thanks, Raj

asked 25 Jul '16, 23:32

Rajeev%20N's gravatar image

Rajeev N
13129
accept rate: 0%

edited 26 Jul '16, 14:28


Why not introduce the explicit constraints \(x_{i_1,j} = x_{i_2,j}\) for all \(j\) and let the presolver substitute them away? Your proposed penalized objective alternative artificially increases the problem size, requires you to come up with a penalty, and does not guarantee constraint satisfaction.

If you are running up against some limit on the number of constraints, you can do some offline work instead, as follows. Create a graph \(G\) with a node for each \(i\in I\) and an edge for each of your \((i_1,i_2)\) pairs. Now the \(x\) variables collapse according to the connected components of \(G\). For each component, choose a representative \(i\) and use that index in place of the other members of that component. For example, if \(I = \{1,2,3,4\}\) and your pairs are \(\{(1,2),(2,3)\}\), the connected components of \(I\) are \(\{1,2,3\}\) and \(\{4\}\), and you would replace each occurrence of \(x_{2,j}\) and \(x_{3,j}\) with \(x_{1,j}\). But it's simpler to just let the presolver do this for you.

link

answered 26 Jul '16, 09:20

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 26 Jul '16, 09:22

Thanks for your guidance, Rob. There are some more details I missed in the original post.

It is also possible that this constraint can be violated with a penalty. For example, if (i1,i2) and (i1,i3) are predecessor-successor patient pairs but i2&i3 overlap(in time dimension), doctor j can treat only one of i2 or i3. So my constraint is x_{i1,j} <= x_{i2,j}+x_{i3,j}

The rest of my constraint matrix is structured such that the MIP solves in the root node, but this constraint causes the MIP to go into Branch & Bound. Hence trying to model it in the objective itself.

Thanks!

(26 Jul '16, 14:27) Rajeev N

OK, it looks like I might have misinterpreted your desired implication to be two-way rather than one-way. So I think you wanted \(x_{i_1,j} \le x_{i_2,j}\) rather than equality. To change the constraint from hard to soft, you can introduce a nonnegative slack variable \(s_{i_1,i_2}\) and include it as follows: \(x_{i_1,j} \le x_{i_2,j} + s_{i_1,i_2}\). Now penalize the slack variables in the objective.

(26 Jul '16, 17:35) Rob Pratt

Thanks Rob. I tried a tighter version of your constraint - /( x_{i1j} <= x_{i2j}+x_{i3j} + s_{i1} /) - and penalized s variables in the objective.

But as expected, the model does not solve at the root node using CPLEX anymore. Can there be a better constraint which can maintain the solution at root node? My other constraints are the covering constraints(every patient should be treated by at least one doctor) and capacity constraints(a doctor can treat only one patient at a time)

(27 Jul '16, 13:33) Rajeev N

The \(x\) variables are binary? If so, your absolute values are equivalent to the exclusive or of the two variables. The only way I know to linearize that introduces multiple additional constraints, as well as an auxiliary variable, for each pair of indices \(i_1 \neq i_2\). So I would go with Rob's answer.

link

answered 26 Jul '16, 15:42

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Yes Prof. Rubin. They are binary variables. As I mentioned above, the additional constraints are altering the constraint matrix structure, making it difficult to achieve optimality

(27 Jul '16, 14:24) Rajeev N

Well, you can try linearizing the absolute values (instructions posted at http://orinanobworld.blogspot.com/2011/02/binary-exclusive-or.html), but I doubt it will be any kinder to the constraint matrix.

(27 Jul '16, 15:41) 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
×2

Asked: 25 Jul '16, 23:32

Seen: 1,023 times

Last updated: 27 Jul '16, 15:41

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