Topic
  • 9 replies
  • Latest Post - ‏2012-12-04T14:48:36Z by mrmag
mrmag
mrmag
28 Posts

Pinned topic Accessing the optimal solution

‏2012-11-28T15:53:15Z |
Hello!

I have the following problem: there is an optimization problem which I solve in CP Optimizer. At the end I have the following result:

!
! Search terminated normally, 2 solutions found.
! Best objective : 0.25 (optimal - effective tol. is 1.#INF)
! Number of branches : 29379
! Number of fails : 13319
! Total memory usage : 2.5 MB (2.3 MB CP Optimizer + 0.2 MB Concert)
! Time spent in solve : 0.74s (0.74s engine + 0.00s extraction)
! Search speed (br. / s) : 39234.5
!

So there are two solutions which are optimal. But when I try to access the solution like that:

IloSolution sol(env);
for (int i=0; i<n; i++) {
sol.add(u(i));
sol.add(v(i));
}
if (cp.solve()) {
sol.store(cp);
cp.out() << "An optimal solution is " << sol << std::endl;
}

I get the following (variables u(i) and v(i) are binary):

An optimal solution is IloSolution[ u_0(-1.#INF..1.#INF) v_0(-1.#INF..1.#INF) u_1(-1.#INF..1.#INF) v_1(-1.#INF..1.#INF)
u_2(-1.#INF..1.#INF) v_2(-1.#INF..1.#INF) u_3(-1.#INF..1.#INF) v_3(-1.#INF..1.#INF) ]

It is not possible that all variables are not fixed and this is the optimal solution. Do I access the optimal solution incorrectly?
Updated on 2012-12-04T14:48:36Z at 2012-12-04T14:48:36Z by mrmag
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Accessing the optimal solution

    ‏2012-11-28T16:33:11Z  
    When the log says "2 solutions found" it means that it has found two solutions on the way to an optimal solution including the optimal one. You just have one optimal solution available.

    The way you store the optimal solution is correct but it seems that you are including brand new unbounded variables in the solution. So I am wondering what the u(i) and v(i) calls do exacly. Aren't you creating variable that are not in the model ? If not can you post a complete code ?

    For storing any solution found during search you need to write

    cp.startNewSearch();
    while(cp.next()){
    cp.store(sol);
    // handle solution sol here
    }

    Regards

    Philippe
  • mrmag
    mrmag
    28 Posts

    Re: Accessing the optimal solution

    ‏2012-11-29T09:42:27Z  
    When the log says "2 solutions found" it means that it has found two solutions on the way to an optimal solution including the optimal one. You just have one optimal solution available.

    The way you store the optimal solution is correct but it seems that you are including brand new unbounded variables in the solution. So I am wondering what the u(i) and v(i) calls do exacly. Aren't you creating variable that are not in the model ? If not can you post a complete code ?

    For storing any solution found during search you need to write

    cp.startNewSearch();
    while(cp.next()){
    cp.store(sol);
    // handle solution sol here
    }

    Regards

    Philippe
    Dear Philippe,

    I double checked that too. If think I do that correctly. Here is another problem. When I solve the problem and try to get the objective value:

    if (cp.solve()) {
    cout << "ObjValue: " << cp.getObjValue() << endl;
    }

    The program breaks with the following exeption:

    Concert exception caught: CP Optimizer Error : (10) IlcFloatExpI::getValue non-fixed constrained variable 003C72E8

    Does it mean that the objective function is not bounded? I am sure that the formulation of the problem is correct. Here is the complete output:

    !
    ! Minimization problem - 136 variables, 1107 constraints
    ! LogVerbosity = Terse
    ! LogPeriod = 5000
    ! AutomaticReplay = Off
    ! Initial process time : 0.03s (0.01s extraction + 0.01s propagation)
    ! . Log search space : 136.0 (before), 136.0 (after)
    ! . Memory usage : 588.5 kB (before), 620.5 kB (after)
    ! Using parallel search with 2 workers.
    !
    ! Best Branches Non-fixed W Branch decision
    * 0.375 894 0.09s 1 -
    * 0.25 2544 0.17s 1 -
    0.25 5000 15 1 0 = y_2_3
    0.25 5003 11 2 1 = x_2_0
    0.25 10000 8 2 0 = x_2_14
    0.25 10000 7 1 0 = y_1_15
    0.25 15006 7 1 1 = y_1_1
    !
    ! Search terminated normally, 2 solutions found.
    ! Best objective : 0.25 (optimal - effective tol. is 1.#INF)
    ! Number of branches : 29379
    ! Number of fails : 13319
    ! Total memory usage : 2.5 MB (2.3 MB CP Optimizer + 0.2 MB Concert)
    ! Time spent in solve : 0.81s (0.79s engine + 0.01s extraction)
    ! Search speed (br. / s) : 36926.6
    !
    Concert exception caught: CP Optimizer Error : (10) IlcFloatExpI::getValue non-fixed constrained variable 003C72E8

    What am I doing wrong?
  • mrmag
    mrmag
    28 Posts

    Re: Accessing the optimal solution

    ‏2012-11-29T09:55:13Z  
    When the log says "2 solutions found" it means that it has found two solutions on the way to an optimal solution including the optimal one. You just have one optimal solution available.

    The way you store the optimal solution is correct but it seems that you are including brand new unbounded variables in the solution. So I am wondering what the u(i) and v(i) calls do exacly. Aren't you creating variable that are not in the model ? If not can you post a complete code ?

    For storing any solution found during search you need to write

    cp.startNewSearch();
    while(cp.next()){
    cp.store(sol);
    // handle solution sol here
    }

    Regards

    Philippe
    Philippe ,

    concerning your question about u(i) and v(i). I have to sets of variables:

    IloBoolVarArray bvar(env);
    IloNumVarArray nvar(env);

    bvar – are decision variables. For convenience I address them via functions:

    vector<long int > U;
    vector<long int > V;
    vector<vector<long int > > X;
    vector<vector<long int > > Y;

    IloNumVar & u(int k) {
    return nvar[Uk];
    }
    IloNumVar & v(int k) {
    return nvar[Vk];
    }
    IloBoolVar & x(int i, int k) {
    return bvar[X[i]k];
    }
    IloBoolVar & y(int i, int k) {
    return bvar[Y[i]k];
    }
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Accessing the optimal solution

    ‏2012-11-29T11:15:58Z  
    • mrmag
    • ‏2012-11-29T09:55:13Z
    Philippe ,

    concerning your question about u(i) and v(i). I have to sets of variables:

    IloBoolVarArray bvar(env);
    IloNumVarArray nvar(env);

    bvar – are decision variables. For convenience I address them via functions:

    vector<long int > U;
    vector<long int > V;
    vector<vector<long int > > X;
    vector<vector<long int > > Y;

    IloNumVar & u(int k) {
    return nvar[Uk];
    }
    IloNumVar & v(int k) {
    return nvar[Vk];
    }
    IloBoolVar & x(int i, int k) {
    return bvar[X[i]k];
    }
    IloBoolVar & y(int i, int k) {
    return bvar[Y[i]k];
    }
    I think the problem must come from the IloNumVarArray nvar. We do not support IloNumVar as decision variables. It means that we do not instantiate them during search. You can still have IloNumVar in you model but they must be all fixed when fixing all the integer variables. That is they behave like numerical expressions. If you have unfixed IloNumVars when all integer variables are instantiated then you have only a partial assignment and not necessarily a solution. What is strange is that in this case, CP Optimizer should raise an exception, which does not seem to happen in your case.

    So maybe your problem cannot be solved because of these IloNumVars or you have to reformulate it differently.

    Philippe
  • mrmag
    mrmag
    28 Posts

    Re: Accessing the optimal solution

    ‏2012-11-29T11:46:37Z  
    I think the problem must come from the IloNumVarArray nvar. We do not support IloNumVar as decision variables. It means that we do not instantiate them during search. You can still have IloNumVar in you model but they must be all fixed when fixing all the integer variables. That is they behave like numerical expressions. If you have unfixed IloNumVars when all integer variables are instantiated then you have only a partial assignment and not necessarily a solution. What is strange is that in this case, CP Optimizer should raise an exception, which does not seem to happen in your case.

    So maybe your problem cannot be solved because of these IloNumVars or you have to reformulate it differently.

    Philippe
    I attached the model to the message. Decision variables are x_ and y_ , which are binary. u variables are general not integer, but u variables are equal the weighted sum of u and v variables. For that particular model here is the output of CP Optimizer:

    !
    ! Minimization problem - 36 variables, 153 constraints
    ! LogVerbosity = Terse
    ! LogPeriod = 5000
    ! AutomaticReplay = Off
    ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
    ! . Log search space : 36.0 (before), 36.0 (after)
    ! . Memory usage : 379.5 kB (before), 379.5 kB (after)
    ! Using parallel search with 2 workers.
    !
    ! Best Branches Non-fixed W Branch decision
    * 0.5 135 0.03s 1 -
    !
    ! Search terminated normally, 1 solution found.
    ! Best objective : 0.5 (optimal - effective tol. is 1.#INF)
    ! Number of branches : 1656
    ! Number of fails : 819
    ! Total memory usage : 1.3 MB (1.2 MB CP Optimizer + 0.0 MB Concert)
    ! Time spent in solve : 0.04s (0.04s engine + 0.00s extraction)
    ! Search speed (br. / s) : 35384.4
    !
    Concert exception caught: CP Optimizer Error : (10) IlcFloatExpI::getValue non-fixed constrained variable 0097A3C8
    So, there is still the problem. If you need the c++ code I can send it to you.

    Attachments

  • mrmag
    mrmag
    28 Posts

    Re: Accessing the optimal solution

    ‏2012-11-29T11:52:40Z  
    • mrmag
    • ‏2012-11-29T11:46:37Z
    I attached the model to the message. Decision variables are x_ and y_ , which are binary. u variables are general not integer, but u variables are equal the weighted sum of u and v variables. For that particular model here is the output of CP Optimizer:

    !
    ! Minimization problem - 36 variables, 153 constraints
    ! LogVerbosity = Terse
    ! LogPeriod = 5000
    ! AutomaticReplay = Off
    ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
    ! . Log search space : 36.0 (before), 36.0 (after)
    ! . Memory usage : 379.5 kB (before), 379.5 kB (after)
    ! Using parallel search with 2 workers.
    !
    ! Best Branches Non-fixed W Branch decision
    * 0.5 135 0.03s 1 -
    !
    ! Search terminated normally, 1 solution found.
    ! Best objective : 0.5 (optimal - effective tol. is 1.#INF)
    ! Number of branches : 1656
    ! Number of fails : 819
    ! Total memory usage : 1.3 MB (1.2 MB CP Optimizer + 0.0 MB Concert)
    ! Time spent in solve : 0.04s (0.04s engine + 0.00s extraction)
    ! Search speed (br. / s) : 35384.4
    !
    Concert exception caught: CP Optimizer Error : (10) IlcFloatExpI::getValue non-fixed constrained variable 0097A3C8
    So, there is still the problem. If you need the c++ code I can send it to you.
    u and v variables are general non integer, but u and v variables are equal the weighted sum of x_ and y_ variables.
  • mrmag
    mrmag
    28 Posts

    Re: Accessing the optimal solution

    ‏2012-11-29T17:10:12Z  
    • mrmag
    • ‏2012-11-29T11:52:40Z
    u and v variables are general non integer, but u and v variables are equal the weighted sum of x_ and y_ variables.
    Dear Philippe, I fixed it. The problem is solved. Thank you.
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Accessing the optimal solution

    ‏2012-11-30T09:23:28Z  
    • mrmag
    • ‏2012-11-29T17:10:12Z
    Dear Philippe, I fixed it. The problem is solved. Thank you.
    By curiosity, can you tell us what was the problem ?

    Thanks

    Philippe
  • mrmag
    mrmag
    28 Posts

    Re: Accessing the optimal solution

    ‏2012-12-04T14:48:36Z  
    By curiosity, can you tell us what was the problem ?

    Thanks

    Philippe
    The problem was in parameter AutomaticReplay which I turned off:

    cp.setParameter(IloCP::AutomaticReplay, IloCP::Off);

    The reason for that was an internal mistake of CP Optimizer. I had in the model restrictions like

    v = x*x + y*y;

    where v is fractional and x, y are binary decision variables. CP Optimizer crashed sometimes during the search with an internal error. In order to solve that problem I replaced v by (x*x + y*y) everywhere in my model. Now it is not possible to read the model but CP Optimizer can solve it.