Announcement

Collapse
No announcement yet.

Multiple Solver Constraints in Solver

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

  • Multiple Solver Constraints in Solver

    I have a cell, D5, which is the sum of three other cells, A5 B5 and C5. (all currently empty). Cells A1 through C4 are filled with various numbers.

    What I've been trying to do is use solver to say: Make D5 equal 200, do it by manipulating only A5 B5 and C5, and make it subject to the constraint that A5 must equal a value selected from A1:A4, and B5 must equal a value from B1:B4, and C5 ...etc. I have deliberately set it up so that there is only one solution.

    I was doing fine until trying to create the constraints. How can I make a constraint that says "this cell" must equal "one of the following cells"? And if I can't do that, is there an alternate method of achieving the same result?

    Thanks,
    -Simon

  • #2
    Re: Tricky constraint in solver

    Can you post a small sample workbook of what you are trying to accomplish?

    Thanks
    -marc

    Comment


    • #3
      Re: Tricky constraint in solver

      simonsays,

      Try the attachment. I don't know if will suit your purposes if your question is a scaled down example.

      Jim
      PS-Welcome to OzGrid...
      Attached Files

      Comment


      • #4
        Re: Tricky constraint in solver

        Thanks Jim, I looked at the worksheet you provided. Unfortunately I don't think it'll do the trick. You suggested as constraints:

        A5 <= max of desired range
        A5 = integer
        A5 >= min of desired range

        In the particular instance of the data you provided, it works - but only because the solution happens to be the max values of all three data columns. Presumably it would also work fine when the solution used all the minimums.

        My problem is that the solution (I'm going to be using many more columns and perhaps 200 rows when I do this for real) is almost certainly going to involve many intermediate values, and I require that they be drawn exclusively from pre-existing values in my data column. My constraint needs to limit A5 to the specific values contained in a specific range.

        I'm starting to feel like maybe Solver can't do this. Do I need VBA? I've been holding off on learning it for as long as possible (saying "nah, I don't need it, I'll just use solver and reeeeeally long IF statements") but this might be the last straw.

        Any ideas? Thanks again,
        -Simon

        Comment


        • #5
          Re: Tricky constraint in solver

          Simonsays,

          I the following array formula in cell A7 for example and filled across.

          =MIN(ABS(A5-A1:A4)) confirm with ctrl+shift+enter

          If this formula returns zero then you mave a match with the required set of values. Set these formula cells equal to zero as a constraint.

          The problem is non-linear so you might need to play around with solver settings.

          hope this works,

          Paul
          Attached Files

          Comment


          • #6
            Re: Tricky constraint in solver

            Nice idea! I'll try that.

            -Simon

            Comment


            • #7
              Re: Tricky constraint in solver

              Simon,

              (had to edit because I forgot a constraint, doh! )

              After playing around, I think its a bit much for solver to handle. You really need to keep things linear for solver to have a chance. I've reworked the solver model, its a bit more complicated but everything is linear so it should work. You might be waiting a while for a large problem instance though.

              good luck

              Paul
              Attached Files
              Last edited by Paul Corry; September 11th, 2006, 10:02.

              Comment


              • #8
                Re: Multiple Solver Constraints in Solver

                That's a great solutions. Thanks. I'll apply it to my full model.

                The original idea like you said caused solver to blow a gasket. I'm not sure exactly what this linearity issue is. Could you explain it in simple language? Is it that solver can only find an answer when it makes small, discrete steps?

                -Simon

                Comment


                • #9
                  Re: Multiple Solver Constraints in Solver

                  Hi Simon,

                  Glad I could help, your problem was a fun little exercise. Here is a carsh course on linearity.

                  if your variables are denoted X1, X2 and X3, a linear expression takes the form:

                  aX1 + bX2 + cX3

                  where a,b and c are constants.

                  examples of non-linear expressions are:
                  aX1^2, sin(X1), abs(X1), max(X1,X2), etc.

                  Models which have only linear expressions have search spaces with smooth and predictable geometry, so given enough time Solver should be able to find a solution.

                  Non-linear models have "bumpy" and unpredictable search spaces so Solver can easly get trapped, unable to continue its search. Often (but not always), a non-linear model can be transformed into a linear model by introducing new variables and constraints.

                  The moral of the story is to try to use a linear formulation wherever possible.

                  There's my carsh course in linearity, hope it made sense,

                  Paul

                  Comment


                  • #10
                    Re: Multiple Solver Constraints in Solver

                    simonsays,
                    First you said:
                    What I've been trying to do is use solver to say: Make D5 equal 200, do it by manipulating only A5 B5 and C5, and make it subject to the constraint that A5 must equal a value selected from A1:A4, and B5 must equal a value from B1:B4, and C5 ...etc. I have deliberately set it up so that there is only one solution.
                    then:
                    My problem is that the solution (I'm going to be using many more columns and perhaps 200 rows when I do this for real) is almost certainly going to involve many intermediate values, and I require that they be drawn exclusively from pre-existing values in my data column. My constraint needs to limit A5 to the specific values contained in a specific range.
                    So, now I'm confused, did you try my solver set-up because I think it works for any values in the range as long as they are integers and there is only one solution (like you said at first)?

                    Jim

                    Comment


                    • #11
                      Re: Multiple Solver Constraints in Solver

                      Hi Jim,

                      Hope I'm not standing on Simon's toes but here goes...

                      The problem was to make sure each changing cell matched exactly one of the values in a given range. Your model addresses a different problem because it looks for integer values between the minimum and maximum values in the range. This doesn't guarantee a match. For example if you change the cell A1 in your spreadsheet from 75 to 76, solver still puts 75 in the changing cell even though it doesn't match anything in the range.

                      If you saw my solution to the problem it was fairly complex, perhaps there is a better way?

                      Paul

                      Comment


                      • #12
                        Re: Multiple Solver Constraints in Solver

                        Hi Paul,

                        No, I think you got it covered. After the drugs wore off, I understood the question more better. By the by, why doesn't using BIN result in exactly 1 or exactly 0? That just bugs me...

                        Jim

                        Comment


                        • #13
                          Re: Multiple Solver Constraints in Solver

                          Hi Jim,

                          That's just a precision error. If you go into solver options there is precision field. Solver treats anything within this margin of a binary as a binary. Same goes for integers. Lower precision means faster run times but less accurate results.

                          Solver uses a branch and bound algorithm which starts of by relaxing all integer/binary constraints which it then solves. As it goes it adds constraints one by one to force individual variables to be integer or binary, and then solves again. If it reaches an infeasible solution it backtracks and explores a new branch of the tree by trying different constraints. Certain conditions tell solver when a branch will not hold the optimal solution so it prunes those branches. Similar conditions tell solver when it has found the optimal solution (to within the tolerence set in options). It doesn't necessary have to explore the entire tree, but for certain models it can be a bloody long process.

                          To cut a long story short, the precision errors are a result of the constraint relaxation process and the required numerical precision.

                          Hope this kind of explains it....

                          Paul

                          Comment

                          Working...
                          X