Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
  • 1.  strange problem in CPLEX...???

    Posted Mon June 17, 2013 02:35 AM

    Originally posted by: karlomc


    Hi all,

         to solve a problem, the result correct should be 141 (
    the sum of all the edges)... but CPLEX performs an incorrect assignment and optimal returns as 144. What is the problem?... that is a simple problem, that is not running correctly?...

    Thanking you for your help, code attached...
    regards
    C. C.


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: strange problem in CPLEX...???

    Posted Mon June 17, 2013 07:22 AM

    I guess the offending model is modelo.lp in your tarball? Solving this with CPLEX 12.5.1 in the interactive optimizer gives:

    CPLEX> read modelo.lp
    Problem 'modelo.lp' read.
    Read time = 0.00 sec. (0.00 ticks)
    CPLEX> opt
    Found incumbent of value 144.000000 after 0.00 sec. (0.01 ticks)
    Tried aggregator 1 time.
    MIP Presolve eliminated 29 rows and 109 columns.
    All rows and columns eliminated.
    Presolve time = 0.00 sec. (0.04 ticks)

    Root node processing (before b&c):
      Real time             =    0.00 sec. (0.05 ticks)
    Parallel b&c, 2 threads:
      Real time             =    0.00 sec. (0.00 ticks)
      Sync time (average)   =    0.00 sec.
      Wait time (average)   =    0.00 sec.
                              ------------
    Total (root+branch&cut) =    0.00 sec. (0.05 ticks)

    Solution pool: 1 solution saved.

    MIP - Integer optimal solution:  Objective =  1.4400000000e+02
    Solution time =    0.00 sec.  Iterations = 0  Nodes = 0
    Deterministic time = 0.05 ticks  (48.97 ticks/sec)

    CPLEX> disp sol qual  
    Incumbent solution:
    MILP objective                                 1.4400000000e+02
    MILP solution norm |x| (Total, Max)            2.90000e+01  1.00000e+00
    MILP solution error (Ax=b) (Total, Max)        0.00000e+00  0.00000e+00
    MILP x bound error (Total, Max)                0.00000e+00  0.00000e+00
    MILP x integrality error (Total, Max)          0.00000e+00  0.00000e+00
    MILP slack bound error (Total, Max)            0.00000e+00  0.00000e+00

    And the same result with presolve disabled. The solution looks good. When I change your problem to LP then the objective function value of this LP is 144, meaning that no solution better than 144 can exist. Since your model is so simple it can even be solved manually (just pick one variable from each constraint and set it 1) and even for that I get an objective function value of 144.

    Why do you think the optimal solution should be 141? Is it possible you set up the model in a wrong way? Could you please provide the solution vector for objective function value 141?


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: strange problem in CPLEX...???

    Posted Mon June 17, 2013 12:06 PM

    Originally posted by: karlomc


    Thanks for your answer Daniel Junglas,

    This model is simple and consists of required and non-required edges (Rural Postman Problem) ... missing some restrictions but the question is  irrelevant. If only consider the restriction to ensure service to each required edge, and I'm minimizing the optimum would be easily the sum of required edges.

    Node i Node j Coste Required Edge
    1 2 5
    2 3 3
    2 4 3
    3 4 10
    4 5 8
    6 7 7
    6 8 3
    6 9 5
    10 11 9
    11 12 8
    12 13 6
    12 14 3
    15 16 9
    15 17 5
    18 20 6
    20 21 1
    19 21 4
    21 23 3
    22 23 4
    24 26 5
    26 25 3
    26 27 3
    28 29 5
    29 30 7
    29 31 6
    31 32 4
    28 32 2
    32 33 2
    8 9 2

    Optimal Solution = sum... coste required edges = 141. The difference between 144 and 141 is for an assignment of "x" incorret (red)...

    Var (x):
     1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     
    The first assignments are equal to one because the restriction assures me service required edges (this is ok) ... but not for assignment in red, this does not correspond to a restriction, plus I'm inimizando ...CPLEX why is assigning the value one to the variable x (in red)?...I do not understand

    Thanking reply
    regards


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: strange problem in CPLEX...???

    Posted Mon June 17, 2013 01:31 PM

    I don't understand how those nodes and edges in your model map to the model in modelo.lp. Looking at modelo.lp I see these constraints:

    Subject To
    c1:  x1 + x2  = 1
    c2:  x3 + x4  = 1
    c3:  x5 + x6  = 1

    All constraint look like this, that is, all constraints are of the form

    x[i] + x[i+1]

    with all x[i] being binary variables and each variable appearing in at most one constraint.

    Looking at the variable x[i] and x[i+1] in a constraint one can see that both variables have the same coefficient in the objective function. Each constraints x[i]+x[i+1]=1 states the requirement "set either x[i] or x[i+1] to 1, but not both". If you now pick an (arbitrary) variable in each constraint and sum up the objective function coefficients for the selected variables then you get 144, not 141. Since the variables in a single constraint have the same coefficient in the objective function, it does not really matter which variable you pick in a constraint.

    So CPLEX correctly finds the optimal objective function.

    To me it looks like the model you create is not what you want to create. Maybe it is a good idea to assign names to all the x variables:

    x[i][j][k] = IloBoolVar(env2);
    std::stringstream s;
    s << "x#" << i << "'#" << j << "#" << k;
    x[i][j][k].setName(s.str().c_str());

    run the program again and double check that the constraint in modelo.lp look like expected.
     


    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: strange problem in CPLEX...???

    Posted Mon June 17, 2013 02:04 PM

    Originally posted by: karlomc


    Thanks again Tomas, the truth is that you check the code again ... and the problem was in reading problem parameters ...so the difference in results.

    I appreciate your help,
    regards


    #CPLEXOptimizers
    #DecisionOptimization


  • 6.  Re: strange problem in CPLEX...???

    Posted Wed June 19, 2013 03:29 PM

    Originally posted by: EdKlotz


    If you have a situation like this where you believe a better solution exists than the one CPLEX declares as optimal, here's a way you can let CPLEX do some of the work that Daniel did manually to figure out what is happening.    Take the model which CPLEX declares as optimal with objective 144.   Add a constraint that the objective <= 141 (or whatever the objective associated with the solution you believe is better).    Run this modified version of the model.   If CPLEX now finds a solution with objective 141, you have some proven inconsistent behavior in the optimizer.   More likely, however, CPLEX will correctly declare this model infeasible.   In that case, run CPLEX's conflict refiner to obtain an explanation of the infeasibility.   The resulting conflict information will include the constraint that the objective <= 141, plus some other constraints that conflict with this requirement.   Typically that will shed light on the part of your model that is not specified the way you intended.

    Doing this with your model generates the following conflict, which confirms Daniel's analysis to be correct:

     

    \ENCODING=ISO-8859-1
    \Problem name: junk.lp_conflict

    Minimize
     obj:
    Subject To
     conobj: 5 x1 + 5 x2 + 3 x3 + 3 x4 + 3 x5 + 3 x6 + 10 x7 + 10 x8 + 8 x9 + 8 x10
             + 7 x11 + 7 x12 + 3 x13 + 3 x14 + 5 x15 + 5 x16 + 9 x17 + 9 x18
             + 8 x19 + 8 x20 + 6 x21 + 6 x22 + 3 x23 + 3 x24 + 9 x25 + 9 x26
             + 5 x27 + 5 x28 + 6 x29 + 6 x30 + x31 + x32 + 4 x33 + 4 x34 + 3 x35
             + 3 x36 + 4 x37 + 4 x38 + 5 x39 + 5 x40 + 3 x41 + 3 x42 + 5 x43
             + 5 x44 + 7 x45 + 7 x46 + 6 x47 + 6 x48 + 4 x49 + 4 x50 + 2 x51
             + 2 x52 + 2 x53 + 2 x54 + 2 x55 + 2 x56 + 12 x57 + 12 x58 + 16 x59
             + 16 x60 + 3 x61 + 3 x62 + 15 x63 + 15 x64 + 7 x65 + 7 x66 + 18 x67
             + 18 x68 + 10 x69 + 10 x70 + 7 x71 + 7 x72 + 3 x73 + 3 x74 + 21 x75
             + 21 x76 + 7 x77 + 7 x78 + 16 x79 + 16 x80 + 6 x81 + 6 x82 + 14 x83
             + 14 x84 + 12 x85 + 12 x86 + x87 + x88 + 12 x89 + 12 x90 + 3 x91
             + 3 x92 + 16 x93 + 16 x94 + 6 x95 + 6 x96 + 6 x97 + 6 x98 + 5 x99
             + 5 x100 + 6 x101 + 6 x102 + 11 x103 + 11 x104 + 3 x105 + 3 x106
             + 9 x107 + 9 x108 + x109 <= 141
     c1:     x1 + x2  = 1
     c2:     x3 + x4  = 1
     c3:     x5 + x6  = 1
     c4:     x7 + x8  = 1
     c5:     x9 + x10  = 1
     c6:     x11 + x12  = 1
     c7:     x13 + x14  = 1
     c8:     x15 + x16  = 1
     c9:     x17 + x18  = 1
     c10:    x19 + x20  = 1
     c11:    x21 + x22  = 1
     c12:    x23 + x24  = 1
     c13:    x25 + x26  = 1
     c14:    x27 + x28  = 1
     c15:    x29 + x30  = 1
     c16:    x31 + x32  = 1
     c17:    x33 + x34  = 1
     c18:    x35 + x36  = 1
     c19:    x37 + x38  = 1
     c20:    x39 + x40  = 1
     c21:    x97 + x98  = 1
     c22:    x41 + x42  = 1
     c23:    x43 + x44  = 1
     c24:    x45 + x46  = 1
     c25:    x47 + x48  = 1
     c26:    x49 + x50  = 1
     c27:    x51 + x52  = 1
     c28:    x53 + x54  = 1
     

    ...

     


    #CPLEXOptimizers
    #DecisionOptimization