Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
10 replies Latest Post - ‏2013-03-13T16:58:19Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts
ACCEPTED ANSWER

Pinned topic Getting multiple solution of MIP for only linear variable

‏2013-02-20T14:19:41Z |
Hi all,

I will be grateful if any of you can help me with the follwoing

I am using JAVA concert technology - my model is MIP , having one Boolean and two linear variable

I want to get multiple solution out of my model with the following characters-tics
1. Boolean variables should be same
2. objective must be same
3. only mentioned linear variable can change its value.

I tried using populate but it does not restrict to my conditions and also it gives something like

New ROute Entered:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 32 1 0 4MT 1976.7795591334097
32 1 1 0 1 4MT 3060.0 6.075

32 1 3 0 1 4MT 80.00000000000006 0.20000000000000015

32 2 2 0 1 4MT 350.0 0.85

32 3 2 0 1 4MT 350.0 0.85

32 4 3 0 1 4MT 260.0 0.65

New ROute Entered:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 33 1 0 4MT 1976.7795591334095
33 1 1 0 1 4MT 3060.0 6.075

33 1 3 0 1 4MT 80.00000000000064 0.2000000000000016

33 2 2 0 1 4MT 350.0 0.85

33 3 2 0 1 4MT 349.9999999999992 0.8499999999999981

33 4 3 0 1 4MT 260.0 0.65
I want to restrict model upto two decimal, is it possible in cplex , if yes how?

Thanks
Arun Lila
Updated on 2013-03-13T16:58:19Z at 2013-03-13T16:58:19Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-20T22:50:01Z  in response to SystemAdmin
    I don't think populate will be of any use; the MIP solver is simply not designed to look for multiple optima that differ only in the continuous variables.

    Once you have solved the MIP, convert the problem to a "fixed" LP (by fixing the values of the integer variables) and solve it that way. It likely will produce the same values for the continuous variables, but who knows, you might get a second optimum (if one exists). Either way, use the sensitivity output to see if other solutions may exist (see here for details -- the last paragraph suggests one way to find additional solutions). Another possible approach (still using the fixed LP) is described at the end of this post.

    Paul

    Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: Getting multiple solution of MIP for only linear variable

      ‏2013-02-21T07:06:37Z  in response to SystemAdmin
      Thanks Paul, your suggestions are helpful and my model is giving required results.

      I just want to know one more thing , Is there any way we can do "solve MIP, then populate" in java , like we do in AMPL setting populate == 1 or 2.

      Regards
      Arun Lila
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: Getting multiple solution of MIP for only linear variable

        ‏2013-02-21T09:05:50Z  in response to SystemAdmin
        Can we also populate result for a particular binary variable, I have two variables and i does not want the change in the one , i want result only changing the second variable.

        Thanks
        Arun Lila
        • T_O
          T_O
          444 Posts
          ACCEPTED ANSWER

          Re: Getting multiple solution of MIP for only linear variable

          ‏2013-02-21T09:19:44Z  in response to SystemAdmin
          > XV05_Arun_Lila wrote:
          > Can we also populate result for a particular binary variable, I have two variables and i does not want the change in the one , i want result only changing the second variable.

          Just fix the first variable by setting its upper and lower bound to the same value.

          Best regards,
          Thomas
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: Getting multiple solution of MIP for only linear variable

            ‏2013-02-21T13:17:34Z  in response to T_O
            Thanks Thomas,

            to implemet your suggestion I am trying following thing
            if ( subcplex.solve() )
            {
            System.out.println("objective = " + subcplex.getObjValue());
            }
            for(int q=0;q<arc_selected.length;q++)
            {
            System.out.println("Arc is::::::::::arc selected::"+subcplex.getValue(arc_selected[q]));
            double i = subcplex.getValue(arc_selected[q]);
            arc_selected[q].setLB(i);
            arc_selected[q].setUB(i);
            }
            subcplex.setParam(IloCplex.IntParam.PopulateLim, 10);
            subcplex.setParam(IloCplex.IntParam.SolnPoolIntensity, 4);
            subcplex.setParam(IloCplex.IntParam.SolnPoolReplace, 1);
            subcplex.setParam(IloCplex.IntParam.SolnPoolCapacity , 1000);
            subcplex.setParam(IloCplex.DoubleParam.SolnPoolGap, 1000000000);
            subcplex.setParam(IloCplex.DoubleParam.SolnPoolAGap, 1);

            if ( subcplex.populate() )
            {
            System.out.println();
            System.out.println("knapsack solved");
            numsol = subcplex.getSolnPoolNsolns();
            System.out.println("The solution pool contains " + numsol + " solutions.");
            }

            where arc_selected[] is Boolean variable.

            But it throws an exception , it seems i can not add the constraints to the solved model.

            Please suggest a way out,

            Also i would like to know if can fix the search for linear variable upto maximum two points of decimal.
            Reagrds
            Arun LIla
            • SystemAdmin
              SystemAdmin
              7929 Posts
              ACCEPTED ANSWER

              Re: Getting multiple solution of MIP for only linear variable

              ‏2013-02-21T13:27:15Z  in response to SystemAdmin
              Could you please provide details about the exception that is thrown? What is the type of the exception? What is the exception message? What is the backtrace?
              Also note that this is potentially calling for trouble:
              double i = subcplex.getValue(arc_selected[q]);
              arc_selected[q].setLB(i);
              arc_selected[q].setUB(i);
              

              Due to tolerances or round-off errors i may be slightly non-integral and you may be fixing the variable to a non-integral value. A safer variant of your code would be to round the value for i:
              double i = Math.round(subcplex.getValue(arc_selected[q]));
              

              That ensures that you actually fix to integral values.

              What do you mean by "fix the search for linear variable upto maximum two points of decimal"? Do you mean that only values like 1.11, 1.12 etc. are allowed for that variable but not 1.234? That is not possible since it would turn a continuous variable into a discrete variable (basically it would just be a scaled integral variable). To get things like that you will have to model with integer variables and scale them appropriately.
              Updated on 2014-03-24T22:39:37Z at 2014-03-24T22:39:37Z by iron-man
              • SystemAdmin
                SystemAdmin
                7929 Posts
                ACCEPTED ANSWER

                Re: Getting multiple solution of MIP for only linear variable

                ‏2013-02-21T13:50:02Z  in response to SystemAdmin
                Even when I put the loop like

                for(int q=0;q<arc_selected.length;q++)
                {
                System.out.println("Arc is::::::::::arc selected::"+subcplex.getValue(arc_selected[q]));
                arc_selected[q].setLB(0);
                arc_selected[q].setUB(1);
                }

                it just enter the lop once and say
                Arc is::::::::::arc selected[0]::1.0
                :::::::::::::::::::::::::::::::Concert Error: ilog.cplex.CpxException: CPLEX Error 1217: No solution exists.

                the problem seems, once you solve the model u can not add the new constraint

                Is the process I am following is right or there is another process for calling solve multiple times.

                Thanks
                Arun Lila
                • T_O
                  T_O
                  444 Posts
                  ACCEPTED ANSWER

                  Re: Getting multiple solution of MIP for only linear variable

                  ‏2013-02-21T13:58:53Z  in response to SystemAdmin
                  I guess that changing the bounds discards the solution in the following iterations. So you should first obtain the solution and then change the bounds.

                  Best regards,
                  Thomas
                  • SystemAdmin
                    SystemAdmin
                    7929 Posts
                    ACCEPTED ANSWER

                    Re: Getting multiple solution of MIP for only linear variable

                    ‏2013-02-21T14:18:33Z  in response to T_O
                    Thomas, you are exactly right here. Changing any part of the model will discard the solution.
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-03-13T16:58:19Z  in response to SystemAdmin
    Thanks It was helpful...