I am trying to model (and solve) a variant of an assignment problem (let's say, patients to doctors, and I am considering a manytoone type assignment). One of the constraints I am dealing with is I do not want too many changes from the current assignment, which, of course, leads to penalties in objective function when being modeled. Let's say the current assignment from set (i in I) (patients) to (j in J) (doctors) is given by (a_{ij} in {0,1}), and the variables are (x_{i,j} in {0,1}). Then with a maximization of objective function (I have some other criteria which I am maximizing), I am adding (p*sum_i sum_j x_{ij}a_{ij}) in the objective function. Couple of questions here: (1) Is this the best way to capture and penalize transfers? I thought of using the above part rather than adding (sum_{j} p * sum_{i} (x_{ij}  a_{ij})) in the objective, since this could lead to circular transfers like: patient a goes from doctor x to y, patient b goes from doctor y to z and patient c goes from doctor z to x. Same goes for adding (sum_{i} p*sum_{j} max{x_{ij}a_{ij}, 0}). Although a transfer is penalized twice in the above formulation, it at least captures any transfer and penalizes that. (2) Now, obviously, the objective is becoming nonlinear. I did some research about linearizing this, but could not go too far. This reference talks about linearizing abs(.) in objective function, but they are of type (sum_{i} a_i x_i) type. Another reference talks about the case which is pretty close to mine, but it doubles the number of variables. Any other modeling insight to mitigate that? Thanks. asked 10 May '12, 01:53 Samik R.
showing 5 of 11
show 6 more comments

About linearization: your (a_{ij}) and (x_{ij}) can take values 0 or 1 so can formulate the absolute value as: [sum_{ij, a_{ij} = 1} (1  x_{ij}) + sum_{ij, a_{ij} = 0} x_{ij}] I ended up using a formulation which is easier to code in Excel, but is the same formulation as the answer above. It is to use this: (p cdot sum_{ij} a_{ij} cdot (1x_{ij}) + sum_{ij} (1a_{ij}) cdot x_{ij}), instead of the above, or what I originally mentioned: (p cdot sum_i sum_j x_{ij}a_{ij}). Works like a charm. Thanks.
(22 May '12, 16:33)
Samik R.
I thought TeX worked in comments too. Doesn't it?
(22 May '12, 16:39)
Samik R.
@Samik: Using
(23 May '12, 04:37)
fbahr ♦

If I understand your problem properly, it seems that you would want to create decision variables (x) with 3 indices: i = patient number, j = current physician, k = next assigned physician Then your objective function would contain nonzero penalty coefficients for x(i,j,k) where j<>k. There is no double counting and no absolute value processing is required. Note that you could cap the number of patient transfers as a hard constraint: SUM(x(i,j,k)) <= Upper Bound, where j<>k Moreover, if you have other objectives in the objective function, well you obviously need a way of relatively rationalizing the penalty values across the objective types. The AHP is one way to do that, or you could make all but one of the objectives constraints or consider Goal Programming. answered 11 May '12, 06:45 Steve Mack @Steve Mack: Thanks for the response. This modeling also seems correct, but I ended up using the other answer since that requires the same number of variables.
(22 May '12, 16:40)
Samik R.

Ah .. I never get the TeX stuff right ... still working !!
@Samik It's more than the second paragraph, in my browser the whole page gets messed up, when the Tex part is rendered. The page width is no respected. I am not sure, looks like a bug in the rendering modul.
I don't know about the problem with page width, but inline equations should be tagged with backslashbackslash( and backslashbackslash) to keep them stay on the line correctly as it seems you intended that way.
@Ehsan Please disregard previous comment, my bad didn't think.
@Bo: Thanks for letting me know about the slash.
By the way, this page width error seems related to something on this particular page as other ORX pages with MathJax are displayed correctly. Also, I checked multiple browsers (IE, Chrome, and Opera) and none of them shows this page correctly, so it's not a browserspecific error.
I created a new question with the same content and the page width problem happened again. However, when I copied the content of another question with equation, no problem occurred. Maybe, there is something wrong with the question content from a HTML, ASP, or ... perspective (I'm no expert in this field).
@Samik: Did a quickndirty "search & replace" fix; if you like to see some formulas put in math env (i.e., not displayed inline), change the "backslashbackslash(" pattern to "backslashbackslash[".
Thanks @fbahr, @Bo and @Ehsan  appreciate it. I need to keep a cheat cheet handy I think.
FYI, in order to show braces arounds sets (as in {0,1}) while in LaTeX mode, you need to escape them with doubled backslashes.
Don't know what all this talk of width problems is. The page renders fine for me (Firefox).
@Samik: I'm not understanding your first numbered point  the "rather than" expression is equivalent mathematically to the one you used. Another Adventure in LaTeX?
@Paul: You don't see the rendering problem @Bo and @Ehsan is talking about since @fbahr fixed it :) And you are right, the two expressions were same  not TeX adventure but my toolatenight adventure I suppose. Edited it  thanks for catching.