1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Integer programming model (alternating constraints)

  1. Nov 16, 2017 #1
    1. The problem statement, all variables and given/known data
    Formulate as a mixed integer programming problem but do not solve. Maximize ##x_1 + x_2## subject to ##2x_1 + 3x_2 \le 12## or {##3x_1 + 4x_2 \le 24## and ##-x_1 + x_2 \ge 1##} ##x_1, x_2 \ge 0##

    2. Relevant equations


    3. The attempt at a solution
    if the first constraint is met, we have upper bounds ##x_1 = 6, x_2 = 4##,
    so ##2x_1 + 3x_2 - 12 \le 2(6) + 3(4) -12 = 12##

    if the set of constraints is met, from the first constraint of the set we have upper bounds ##x_1 = 8, x_2 = 6## and from the second constraint of the set we have upper bounds ##(-x_1 \ge 1) \rightarrow (x_1 \le -1) \rightarrow x_1 = 0?, x_2## is not bounded above.

    Therefore, for the whole set, we have upper bounds ##x_1 = 0, x_2 = 6##

    Therefore, ##3x_1 + 4x_2 - 24 \le 3(0) + 4(6) - 24 = 0##
    and ##-x_1 + x_2 - 1 \ge -(0) +(0) - 1 = -1##

    So the model is Maximize ##x_1 + x_2##
    subject to
    ##2x_1 + 3x_2 - 12 \le 12(1 - y_1)##
    ##3x_1 + 4x_2 - 24 \le 0(1 - y_2)##
    ##-x_1 + x_2 -1 \ge -1(1 - y_2)##

    ##y \space \epsilon##{0,1} and ##x_i \ge 0## for all i.

    the answer key has ##-x_1 + x_2 -1 \ge -7(1 - y_2)## instead of -1 in my third constraint... where did i go wrong?
     
  2. jcsd
  3. Nov 16, 2017 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You can use ##2x_1+3x_2-12 \leq M_1 (1-y)##, ##3x_1 + 4x_2 -24 \leq M_2 \,y## and ##-x_1+x_2-1 \geq -M_3\, y##, where ##M_1, M_2, M_3>0## are chosen large enough that constraints ##2x_2 + 3 x_2 - 12 \leq M_1##, ##3x_1 + 4x_2 - 24 \leq M_2## and ##-x_1 + x_2 -1 \geq -M_3## are all redundant. It does not really matter a lot what values of the ##M_i## you choose, just as long as they are not much too large: if ##M = 20## will work, do not choose ##M = 2,00,000##.

    Among the three constraints, the second one ##3x_1 + 4x_2 \leq 24## is the "loosest", giving ##x_1 \leq 8## and ##x_2 \leq 6##. Therefore, ##2x_1 + 3x_2 \leq 2(8) + 3(6) = 30,## so we can pick ##M_1 = 30-12 = 18##. We have ##3x_1 + 4 x_2 \leq 3(8) + 4(6) = 48##, so we can pick ##M_2 = 48-24 = 24.## Finally, ##-x_1 + x_2 \geq -8 + 0 = -8;## thus ##-x_1 + x_2 - 1 \geq -9## is redundant, so we can pick ##M_3 = 9##.

    With a bit more work we might be able to come up with smaller ##M_i##, but I doubt that it is worth worrying about. (It might be worth worrying about if we had ##M_1 = 1800## for example---in a problem where ##M_1 = 18## will do---because that would lead to feasible ##(x_1,x_2,y)## region in the LP relaxation that is long and narrow, thus magnifying the effects of computational roundoff errors and making it harder to distinguish between branches and bounds in a search tree for the integer problem.)
    Apparently, your book was able to use ##M_3 = 7## instead of ##M_3 = 9##, but as I said, that is not very important in practice.
     
    Last edited: Nov 16, 2017
  4. Nov 16, 2017 #3
    Thanks for the reply.

    Since we chose the "loosest" constraint's upper bounds, ##U_1 \ge x_1, U_2 \ge x_2## in constraint 3, that means they are also upper bounds of the first constraint's variables and the third constraint's variables, since an upper bound is just some number that is greater than or equal to all ##x_i## of some set ##X##. Then what I did was too much, I can just use the greatest upper bound and apply it to all constraints. Do I understand you?

    edit: I am confused.. If we let ##M_i## get bigger or smaller doesn't that mean our set of feasible solutions also changes? And isn't that bad?
     
  5. Nov 16, 2017 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If we let ##M_i## get bigger, the feasible region for the mixed IP problem remains exactly the same, but the feasible region of the LP relaxation gets larger. If it gets a bit larger that will not matter very much, but making it much, much larger that it needs to be is definitely not advisable.

    Generally, there is a tradeoff when modelling such situations: should we spend a lot of time and effort getting nearly the best ##M_i## possible, or should we just go with "reasonable" ##M_i## and then get on with the problem-solving process? Of course, generally speaking, the problem solving process is shorter and more efficient if we use smaller ##M_i##, but it is hard to know the exact tradeoff. Remember: in industrial-sized problems like yours we may have hundreds of thousands of variables and tens to hundreds of thousands of constraints, so what looks simple enough in a 2-variable, 3-constraint example might be pretty horrible in a realistic scenario.
     
  6. Nov 16, 2017 #5
    That makes sense, thank you.
     
  7. Nov 16, 2017 #6

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    The point of making the M values large is to get it's constraint out of the way when it is not applicable to the "or" option that is being solved. So a big M value is fine. If making it bigger changes the solution, then it was not big enough to start with.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Integer programming model (alternating constraints)
  1. Integer Problem (Replies: 4)

  2. Problems on integers (Replies: 8)

  3. Complex integer (Replies: 6)

Loading...