Topic
  • 10 replies
  • Latest Post - ‏2013-03-13T16:58:19Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-20T22:50:01Z  
    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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T07:06:37Z  
    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)
    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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T09:05:50Z  
    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
    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
    448 Posts

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T09:19:44Z  
    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
    > 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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T13:17:34Z  
    • T_O
    • ‏2013-02-21T09:19:44Z
    > 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
    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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T13:27:15Z  
    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
    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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T13:50:02Z  
    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:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">double i = subcplex.getValue(arc_selected[q]); arc_selected[q].setLB(i); arc_selected[q].setUB(i); </pre>
    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:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">double i = Math.round(subcplex.getValue(arc_selected[q])); </pre>
    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.
    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
    448 Posts

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T13:58:53Z  
    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
    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

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-02-21T14:18:33Z  
    • T_O
    • ‏2013-02-21T13:58:53Z
    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
    Thomas, you are exactly right here. Changing any part of the model will discard the solution.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Getting multiple solution of MIP for only linear variable

    ‏2013-03-13T16:58:19Z  
    Thanks It was helpful...