I am trying to model (and solve) a variant of an assignment problem (let's say, patients to doctors, and I am considering a many-to-one 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 non-linear. 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?


asked 10 May '12, 01:53

Samik%20R.'s gravatar image

Samik R.
accept rate: 2%

edited 10 May '12, 11:22

Ah .. I never get the TeX stuff right ... still working !!

(10 May '12, 02:04) Samik R.

@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.

(10 May '12, 02:27) Bo Jensen ♦

I don't know about the problem with page width, but inline equations should be tagged with backslash-backslash-( and backslash-backslash-) to keep them stay on the line correctly as it seems you intended that way.

(10 May '12, 02:51) Ehsan ♦

@Ehsan Please disregard previous comment, my bad didn't think.

(10 May '12, 03:05) Bo Jensen ♦

@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 OR-X 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 browser-specific error.

(10 May '12, 03:17) Ehsan ♦

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).

(10 May '12, 04:02) Ehsan ♦

@Samik: Did a quick-n-dirty "search & replace" fix; if you like to see some formulas put in math env (i.e., not displayed inline), change the "backslash-backslash-(" pattern to "backslash-backslash-[".

(10 May '12, 08:10) fbahr ♦

Thanks @fbahr, @Bo and @Ehsan - appreciate it. I need to keep a cheat cheet handy I think.

(10 May '12, 10:01) Samik R.

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).

(10 May '12, 11:09) Paul Rubin ♦♦

@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?

(10 May '12, 11:12) Paul Rubin ♦♦

@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 too-late-night adventure I suppose. Edited it - thanks for catching.

(10 May '12, 11:25) 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}]


answered 10 May '12, 05:37

Emilie's gravatar image

accept rate: 14%

edited 10 May '12, 09:47

fbahr's gravatar image

fbahr ♦

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 (1-x_{ij}) + sum_{ij} (1-a_{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 * for multiplication may cause troubles (in Markdown, asterisks around a word mean emphasis); use \cdot or \times instead.

(23 May '12, 04:37) fbahr ♦

Thanks @fbahr.

(23 May '12, 11:29) Samik R.

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 non-zero 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%20Mack's gravatar image

Steve Mack
accept rate: 0%

edited 11 May '12, 07:22

@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.
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



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



Asked: 10 May '12, 01:53

Seen: 7,619 times

Last updated: 23 May '12, 11:29

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