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

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
    ACCEPTED ANSWER

    Re: Accessing the optimal solution

    ‏2012-11-28T16:33:11Z  in response to mrmag
    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
      ACCEPTED ANSWER

      Re: Accessing the optimal solution

      ‏2012-11-29T09:42:27Z  in response to SystemAdmin
      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
      ACCEPTED ANSWER

      Re: Accessing the optimal solution

      ‏2012-11-29T09:55:13Z  in response to SystemAdmin
      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
        ACCEPTED ANSWER

        Re: Accessing the optimal solution

        ‏2012-11-29T11:15:58Z  in response to mrmag
        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
          ACCEPTED ANSWER

          Re: Accessing the optimal solution

          ‏2012-11-29T11:46:37Z  in response to SystemAdmin
          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
            ACCEPTED ANSWER

            Re: Accessing the optimal solution

            ‏2012-11-29T11:52:40Z  in response to mrmag
            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
              ACCEPTED ANSWER

              Re: Accessing the optimal solution

              ‏2012-11-29T17:10:12Z  in response to mrmag
              Dear Philippe, I fixed it. The problem is solved. Thank you.
              • SystemAdmin
                SystemAdmin
                554 Posts
                ACCEPTED ANSWER

                Re: Accessing the optimal solution

                ‏2012-11-30T09:23:28Z  in response to mrmag
                By curiosity, can you tell us what was the problem ?

                Thanks

                Philippe
                • mrmag
                  mrmag
                  28 Posts
                  ACCEPTED ANSWER

                  Re: Accessing the optimal solution

                  ‏2012-12-04T14:48:36Z  in response to SystemAdmin
                  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.