Why do DICOPT and BARON come to contradictory conclusions?

Solver related questions
Post Reply
wutuhan
User
User
Posts: 20
Joined: 4 months ago

Why do DICOPT and BARON come to contradictory conclusions?

Post by wutuhan » 4 months ago

Hello, GAMS experts,

I'm trying to solve my MINLP model using solvers DICOPT and BARON, but none of them give ideal results. The MODEL STATUS in the Solution Report using solver DICOPT is 2 Locally Optimal, and the final results of the 0-1 decision variables that the solver gives are always the same as the initial values I set at first. And even more strange is that,the MODEL STATUS of the same model using solver BARON is 19 Infeasible - No Solution. Why? What should I do?

I'm waiting for your answers. Thank you!
Last edited by wutuhan on Mon May 07, 2018 2:03 pm, edited 2 times in total.

User avatar
bussieck
Moderator
Moderator
Posts: 147
Joined: 2 years ago

Re: Why the solvers can only give local optimals of my model?

Post by bussieck » 4 months ago

Hard to help you with this little info. Send log and/or model and perhaps someone can be of help.

-Michael

wutuhan
User
User
Posts: 20
Joined: 4 months ago

Re: Why the solvers can only give local optimals of my model?

Post by wutuhan » 4 months ago

Thank you for your help! Maybe I can give a simple example here to explain my questions from another angle.

Let's consider a small 0-1 knapsack problem, in wchich we have 3 items to determine which to take to maximize the total value. The weights of the items are a1=0.1, a2=0.2, and a3=0.5. The values of them are c1=5, c2=10, and c3=15. Now we suppose the weight limit of the knapsack is b=0.7.

We know this problem is an MILP. To make it become an MINLP, here we add a new rule for it: we require that if item n-1 is taken, then item n can't be taken; if item n-1 is not taken, then item n can be taken or not, where n=2, 3. So I build the model as follow.

Code: Select all

Sets
NS /1 * 3/
;

Parameters
b the weight limit of the knapsack /0.7/
a(NS) the weight of each item
/
'1'		0.1
'2'		0.2
'3'		0.5
/
c(NS) the value of each item
/
'1'		5
'2'		10
'3'		15
/
;

Binary Variables
x(NS)
;
Variables
f
;

Equations
Constraint_1
Constraint_2(NS)
ObjFunc
;
Constraint_1..
	sum(NS, a(NS) * x(NS)) =l= b;
Constraint_2(NS)$(NS.val > 1)..
	x(NS - 1) * x(NS) =e= 0;
ObjFunc..
	f =e= sum(NS, c(NS) * x(NS));

Model myKnapsack /all/;
*OPTION MINLP = BARON;
*x.l('1') = 1;
*x.l('2') = 0;
*x.l('3') = 1;
Solve myKnapsack using MINLP maximizing f;
The Solution Report of the model is

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   myKnapsack          OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  DICOPT              FROM LINE  45

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      2 Locally Optimal           
**** OBJECTIVE VALUE               20.0000

 RESOURCE USAGE, LIMIT          0.078      1000.000
 ITERATION COUNT, LIMIT         9    2000000000
 EVALUATION ERRORS              0             0
In fact, we know the feasible solutions and corresponding total weights and total values of this problem are as follow.

Code: Select all

x1  x2  x3  sum(an*xn)  sum(cn*xn)
0   0   0       0           0
0   0   1       0.5        15
0   1   0       0.2        10
1   0   0       0.1         5
1   0   1       0.6        20
We can see that the so called 2 Locally Optimal DICOPT gives is actually a global optimal solution. If we use solver BARON to solve the model, the Solution Report will be

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   myKnapsack          OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  BARON               FROM LINE  45

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      8 Integer Solution          
**** OBJECTIVE VALUE               20.0000

 RESOURCE USAGE, LIMIT          0.120      1000.000
 ITERATION COUNT, LIMIT         0    2000000000
 EVALUATION ERRORS              0             0
in which the MODEL STATUS is 8 Integer Solution, which is also not 1 Optimal that I want.

What's more, if we change the weight limit of the knapsack to b=0.4, we know the global optimal solution will be (x1, x2, x3)=(0, 1, 0) with the objective value being 10, but the result DICOPT gives is (x1, x2, x3)=(1, 0, 0), and its Solution Report is

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   myKnapsack          OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  DICOPT              FROM LINE  45

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      8 Integer Solution          
**** OBJECTIVE VALUE                5.0000

 RESOURCE USAGE, LIMIT          0.077      1000.000
 ITERATION COUNT, LIMIT        15    2000000000
 EVALUATION ERRORS              0             0
So, I have two main questions about this example:
  • Q1. How can I tell whether the result given by the solvers is a global optimal solution if the MODEL STATUS is not 1 Optimal?
  • Q2. Why is solver DICOPT unable to give a global optimal solution to such a simple MINLP problem?
Thank you for your attention!

User avatar
bussieck
Moderator
Moderator
Posts: 147
Joined: 2 years ago

Re: Why can the solvers only give local optimals of my model?

Post by bussieck » 4 months ago

Q1: BARON obeys the GAMS option optCR (https://www.gams.com/latest/docs/UG_Gam ... AMSAOOptCR) which is by default at 0.1 (or 10%). I fully agree that this is a confusing default but due to backward compatibility we can't easily change this. Such BC "quirks" are described at https://www.gams.com/latest/docs/UG_Lan ... ntProblems. You need to set this to 0.0, e.g. "option optCR=0;". This will provide you with the global optimum and a status "Optimal":

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   myKnapsack          OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  BARON               FROM LINE  46

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      1 Optimal                   
**** OBJECTIVE VALUE               10.0000

 RESOURCE USAGE, LIMIT          0.030      1000.000
 ITERATION COUNT, LIMIT         0    2000000000
 EVALUATION ERRORS              0             0
Q2:
Although the algorithm has provisions to handle non-convexities, it does not necessarily obtain the global optimum.
(copy and paste from the DICOPT manual "Introduction", https://www.gams.com/latest/docs/S_DICOPT.html)

-Michael

wutuhan
User
User
Posts: 20
Joined: 4 months ago

Re: Why can the solvers only give local optimals of my model?

Post by wutuhan » 4 months ago

Thank you very much, Dr. Bussieck! Your help is very useful to me, and I learned a lot from it. But unfortunately, the following issue I mentioned earlier about my model has still not been resolved.
wutuhan wrote:
4 months ago
Hello, GAMS experts,

I'm trying to solve my MINLP model using solvers DICOPT and BARON, but none of them give ideal results. The MODEL STATUS in the Solution Report using solver DICOPT is 2 Locally Optimal, and the final results of the 0-1 decision variables that the solver gives are always the same as the initial values I set at first. And even more strange is that,the MODEL STATUS of the same model using solver BARON is 19 Infeasible - No Solution. Why? What should I do?

I'm waiting for your answers. Thank you!
Here I would like to provide some more information about it.

If I solve my MINLP model myPRSMiT using solver DICOPT without any starting value, the Solution Report is

Code: Select all

Solution Report     SOLVE myPRSMiT Using MINLP From line 4107


               S O L V E      S U M M A R Y

     MODEL   myPRSMiT            OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  DICOPT              FROM LINE  4107

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      5 Locally Infeasible        
**** OBJECTIVE VALUE                0.0000

 RESOURCE USAGE, LIMIT          0.016    360000.000
 ITERATION COUNT, LIMIT         0    2000000000
 EVALUATION ERRORS              0             0
If I set feasible starting values for some of the binary variables, I can get a 2 Locally Optimal using DICOPT as follows (the final values of the binary variables are the same as the starting values I set at first)

Code: Select all

Solution Report     SOLVE myPRSMiT Using MINLP From line 4107


               S O L V E      S U M M A R Y

     MODEL   myPRSMiT            OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  DICOPT              FROM LINE  4107

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      2 Locally Optimal           
**** OBJECTIVE VALUE        322696268.1994

 RESOURCE USAGE, LIMIT          0.640    360000.000
 ITERATION COUNT, LIMIT        33    2000000000
 EVALUATION ERRORS              0             0
and whose log is

Code: Select all

--- Job myRPSMiT.gms Start 05/03/10 10:07:44 WEX-VS8 24.0.2 x86/MS Windows        
GAMS Rev 240  Copyright (C) 1987-2013 GAMS Development. All rights reserved
Licensee: --
          ____
--- Starting compilation
--- myRPSMiT.gms(4147) 3 Mb
--- Starting execution: elapsed 0:00:00.050
--- myRPSMiT.gms(4105) 4 Mb
--- Generating MINLP model myPRSMiT
--- myRPSMiT.gms(4107) 7 Mb
---   6,297 rows  3,987 columns  20,572 non-zeroes
---   31,249 nl-code  10,320 nl-non-zeroes
---   585 discrete-columns
--- myRPSMiT.gms(4107) 5 Mb
--- Executing DICOPT: elapsed 0:00:00.256

Dicopt           Feb 14, 2013 24.0.2 WIN 38380.38394 VS8 x86/MS Windows       

--- DICOPT: Starting major iteration 1
--- DICOPT: Setting up first (relaxed) NLP.
CONOPT 3         Feb 14, 2013 24.0.2 WIN 38380.38394 VS8 x86/MS Windows       
 
 
    C O N O P T 3   version 3.15I
    Copyright (C)   ARKI Consulting and Development A/S
                    Bagsvaerdvej 246 A
                    DK-2880 Bagsvaerd, Denmark
 
 
   Iter Phase Ninf   Infeasibility   RGmax    NSB   Step InItr MX OK
      0   0        2.8980700828E+08 (Input point)
                                Pre-triangular equations:     2028
                                Post-triangular equations:     798
      1   0        3.1443302912E+03 (After pre-processing)
      2   0        1.0781665620E+02 (After scaling)
      3   0    48  1.0781665620E+02               0.0E+00      T  T
      4   0    48  1.0781665620E+02               0.0E+00      T  T
      5   0    48  1.0781665620E+02               0.0E+00      T  T
      6   0    48  1.0781665620E+02               0.0E+00      T  T
      7   0    48  1.0781665620E+02               0.0E+00      T  T
 
   Iter Phase Ninf   Infeasibility   RGmax    NSB   Step InItr MX OK
      8   0    48  1.0781665620E+02               0.0E+00      T  T
      9   0    48  1.0781665620E+02               0.0E+00      T  T
     10   0    48  1.0781665620E+02               0.0E+00      T  T
     11   0    48  1.0781665620E+02               0.0E+00      T  T
     12   0    48  1.0781665620E+02               0.0E+00      T  T
     13   0    48  1.0781665620E+02               0.0E+00      T  T
     14   0    48  1.0781665620E+02               0.0E+00      T  T
     15   0    48  1.0781665620E+02               0.0E+00      T  T
     16   0    48  1.0781665620E+02               0.0E+00      T  T
     17   0    48  1.0781665620E+02               0.0E+00      T  T
 
   Iter Phase Ninf   Infeasibility   RGmax    NSB   Step InItr MX OK
     18   0    48  1.0781665620E+02               0.0E+00      T  T
     19   0    48  6.3505922632E+01               1.0E+00      F  T
     20   1    45  5.9456160727E+01 9.1E+00     3 1.0E+00    3 T  T
     21   1    40  5.1922587839E+01 9.1E+00     5 1.0E+00    8 T  T
     22   1    33  4.3086403144E+01 7.2E+00    25 1.0E+00   13 T  T
     23   1    18  2.0823524973E+01 5.8E+00    19 1.0E+00   18 T  T
     24   1     2  9.6130980900E-01 2.7E+00    28 1.0E+00   18 T  T
 
 ** Feasible solution. Value of objective =   -357265755.905
 
   Iter Phase Ninf     Objective     RGmax    NSB   Step InItr MX OK
     25   3       -3.0283603603E+08 3.0E+07    17 1.0E+00    7 T  T
     26   3        9.6534838905E+07 6.2E+07    22 1.0E+00   16 T  T
     27   3        2.2318704173E+08 6.2E+07    20 1.0E+00   24 T  T
     28   3        2.9228431248E+08 3.0E+07    19 1.0E+00   27 T  T
     29   3        3.0469305891E+08 2.1E+07    30 1.0E+00   35 T  T
     30   3        3.2069725590E+08 7.6E+06    35 1.0E+00   37 T  T
     31   3        3.2242302559E+08 8.7E+05    38 1.0E+00   47 T  T
     32   3        3.2269626820E+08 2.6E+05    23 1.0E+00   20 T  T
     33   3        3.2269626820E+08 1.5E-08    23
 
 ** Optimal solution. Reduced gradient less than tolerance.
 
--- DICOPT: Setting up first MIP
--- DICOPT: Relaxed NLP gives integer solution

      The Relaxed NLP gave a solution where all the integer
      variables have integral values. There is no need to
      to continue the search.

--- Restarting execution
--- myRPSMiT.gms(4107) 0 Mb
--- Reading solution for model myPRSMiT
--- myRPSMiT.gms(4107) 3 Mb
--- Executing after solve: elapsed 0:00:01.111
--- myRPSMiT.gms(4110) 3 Mb
*** Status: Normal completion
--- Job myRPSMiT.gms Stop 05/03/10 10:07:45 elapsed 0:00:01.112
However, since I use solver BARON, the result has always been 19 Infeasible - No Solution, no matter whether I set the start values, as follows

Code: Select all

Solution Report     SOLVE myPRSMiT Using MINLP From line 4107


               S O L V E      S U M M A R Y

     MODEL   myPRSMiT            OBJECTIVE  f
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  BARON               FROM LINE  4107

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      19 Infeasible - No Solution 
**** OBJECTIVE VALUE               NA

 RESOURCE USAGE, LIMIT          3.620    360000.000
 ITERATION COUNT, LIMIT        NA    2000000000
 EVALUATION ERRORS              0             0
and the log of which is

Code: Select all

--- Job myRPSMiT.gms Start 05/03/10 10:09:46 WEX-VS8 24.0.2 x86/MS Windows        
GAMS Rev 240  Copyright (C) 1987-2013 GAMS Development. All rights reserved
Licensee: --
          ____
--- Starting compilation
--- myRPSMiT.gms(4147) 3 Mb
--- Starting execution: elapsed 0:00:00.032
--- myRPSMiT.gms(4105) 4 Mb
--- Generating MINLP model myPRSMiT
--- myRPSMiT.gms(4107) 7 Mb
---   6,297 rows  3,987 columns  20,572 non-zeroes
---   31,249 nl-code  10,320 nl-non-zeroes
---   585 discrete-columns
--- myRPSMiT.gms(4107) 5 Mb
--- Executing BARON: elapsed 0:00:00.241

GAMS/BARON       Feb 14, 2013 24.0.2 WIN 38380.38394 VS8 x86/MS Windows       

===========================================================================
 BARON version 11.9.1. Built: WIN-32 Sat Feb 2 22:39:03 EST 2013 

 If you use this software, please cite:
 Tawarmalani, M. and N. V. Sahinidis, A polyhedral
 branch-and-cut approach to global optimization,
 Mathematical Programming, 103(2), 225-249, 2005.

 BARON is a product of The Optimization Firm, LLC. http://www.minlp.com/
 Parts of the BARON software were created at the
 University of Illinois at Urbana-Champaign.
===========================================================================
 This BARON run may utilize the following subsolver(s)
 For LP:  ILOG CPLEX                                      
 For NLP: MINOS, SNOPT, GAMS external NLP, COIN IPOPT with MUMPS and METIS
===========================================================================
 Problem solved during preprocessing
 Upper bound is -.100000000000D+52

 Cleaning up solution and calculating dual

                         *** Normal Completion ***            

                   *** No feasible solution was found ***

  LP  subsolver time:        000:00:00,    in seconds:          0.00
  NLP subsolver time:        000:00:00,    in seconds:          0.00
  Cutting time:              000:00:00,    in seconds:          0.00
  All other time:            000:00:04,    in seconds:          3.62

  Total time elapsed:        000:00:04,    in seconds:          3.62
       on parsing:           000:00:04,    in seconds:          3.51
       on preprocessing:     000:00:00,    in seconds:          0.11
       on navigating:        000:00:00,    in seconds:          0.00
       on relaxed:           000:00:00,    in seconds:          0.00
       on local:             000:00:00,    in seconds:          0.00
       on tightening:        000:00:00,    in seconds:          0.00
       on marginals:         000:00:00,    in seconds:          0.00
       on probing:           000:00:00,    in seconds:          0.00

  Total no. of BaR iterations:      -1
  Best solution found at node:      -3
  Max. no. of nodes in memory:       0

  Cut generation statistics (number of cuts / CPU sec)
    Bilinear                       180         0.05
    Multilinears                     0         0.25
    Convexity                        0         0.06

 All done
===========================================================================
--- Restarting execution
--- myRPSMiT.gms(4107) 0 Mb
--- Reading solution for model myPRSMiT
--- Executing after solve: elapsed 0:00:04.276
--- myRPSMiT.gms(4110) 3 Mb
*** Status: Normal completion
--- Job myRPSMiT.gms Stop 05/03/10 10:09:50 elapsed 0:00:04.277
What I can't understand most is that, as we can see, DICOPT can give a locally optimal solution for the model, while BARON gets a conclusion that it is not feasible. Why did such a contradiction occur?
Last edited by wutuhan on Mon May 07, 2018 12:52 pm, edited 1 time in total.

User avatar
bussieck
Moderator
Moderator
Posts: 147
Joined: 2 years ago

Re: Why can the solvers only give local optimals of my model?

Post by bussieck » 4 months ago

I agree that this does not look right. There might be a couple of explanations (including bugs in DICOPT and/or BARON), but without being able to reproduce things, there is little we can do. So why don't you upload the model that solves to local optimality with DICOPT but where BARON reports infeasibility.

-Michael

wutuhan
User
User
Posts: 20
Joined: 4 months ago

Re: Why can the solvers only give local optimals of my model?

Post by wutuhan » 4 months ago

I'm so sorry, Dr. Bussieck. I'm very willing to upload the model, but it is too complex and I have to give a detailed description at the same time I send it, which will take a lot of time. Now I plan to check the model carefully again by myself. If I find the problem too strange to solve, I'll consult you again. Thank you again for your enthusiastic help! I will often come to visit this forum.

wutuhan
User
User
Posts: 20
Joined: 4 months ago

Re: Why do DICOPT and BARON come to contradictory conclusions?

Post by wutuhan » 4 months ago

I have found the problem, but it is too strange for me. I simplified my model as much as possible, and fabricated a small example to reflect its core issue, although this example may seem strange. We might as well call this example a Pen Selecting Problem (PSP). I hope my question can be solved with your help.
  • Pen Selecting Problem 1 (PSP-1). There are three brands (A, B, and C) of pens in the store, each with four different color styles: black cap & black body, black cap & white body, white cap & black body, and white cap & white body. We know that pens of different color styles in diferent brands are sold at different prices. Now we want to purchase a pen from each of the three brands at minimal total cost. How shall we select?
The model I build for PSP-1 is given as follow. This is an MILP and can be solved correctly.

Code: Select all

$title Pen Selecting Problem 1 (PSP-1)
$ontext
There are three brands (A, B, and C) of pens in the store, each with four different color styles:
black cap & black body, black cap & white body, white cap & black body, and white cap & white body.
We know that pens of different color styles in diferent brands are sold at different prices.
Now we want to buy a pen from each of the three brands at minimal total cost.
How shall we select?
$offtext

Sets
Brand /A, B, C/
CapColor /black, white/
;
alias(CapColor, BodyColor);

Table Price(Brand, CapColor, BodyColor)
            black     white
A.black       1         2
A.white       4         3
B.black       8         2
B.white       6         4
C.black       9        12
C.white       6         3
;

Binary Variables
x(Brand, CapColor, BodyColor)
;
Variables
Cost
;

Equations
Constraint(Brand)
ObjFunc
;
Constraint(Brand)..
    sum(CapColor, sum(BodyColor, x(Brand, CapColor, BodyColor))) =e= 1;
ObjFunc..
    Cost =e= sum(Brand, sum(CapColor, sum(BodyColor, Price(Brand, CapColor, BodyColor) * x(Brand, CapColor, BodyColor))));

Model myPenSelecting /all/;
Solve myPenSelecting using MINLP minimizing Cost;
Now we add an new rule to let PSP-1 become an MINLP.
  • Pen Selecting Problem 2 (PSP-2). Now we add a new rule: If a mixed color pen (black cap & white body or white cap & black body) is selected from brand A, then a mixed color pen with the same style as the one from brand A (i.e. same cap color and same body color) OR a single color (black cap & black body or white cap & white body) pen whose color is same as the body color of the pen from brand A must be select from brand B, and so on, for brand B and C.
Its GAMS model is

Code: Select all

$title Pen Selecting Problem 2 (PSP-2)
$ontext
There are three brands (A, B, and C) of pens in the store, each with four different color styles:
black cap & black body, black cap & white body, white cap & black body, and white cap & white body.
We know that pens of different color styles in diferent brands are sold at different prices.
Now we want to buy a pen from each of the three brands at minimal total cost.
How shall we select?
Now we add a new rule: If a mixed color pen (black cap & white body or white cap & black body) is 
selected from brand A, then a mixed color pen with the same style as the one from brand A (i.e. same
cap color and same body color) OR a single color (black cap & black body or white cap & white body) 
pen whose color is same as the body color of the pen from brand A must be select from brand B, and 
so on, for brand B and C.
$offtext

Sets
Brand /A, B, C/
CapColor /black, white/
;
alias(CapColor, BodyColor);

Table Price(Brand, CapColor, BodyColor)
            black     white
A.black       1         2
A.white       4         3
B.black       8         2
B.white       6         4
C.black       9        12
C.white       6         3
;

Binary Variables
x(Brand, CapColor, BodyColor)
;
Variables
Cost
;

Equations
Constraint_1(Brand)
Constraint_2(Brand, CapColor, BodyColor)
ObjFunc
;
Constraint_1(Brand)..
    sum(CapColor, sum(BodyColor, x(Brand, CapColor, BodyColor))) =e= 1;
Constraint_2(Brand, CapColor, BodyColor)$(ord(Brand) > 1)..
    (1 - x(Brand - 1, CapColor, CapColor)) * x(Brand - 1, CapColor, BodyColor) * (x(Brand, CapColor, BodyColor) + x(Brand, BodyColor, BodyColor))
     =e= (1 - x(Brand - 1, CapColor, CapColor)) * x(Brand - 1, CapColor, BodyColor);
ObjFunc..
    Cost =e= sum(Brand, sum(CapColor, sum(BodyColor, Price(Brand, CapColor, BodyColor) * x(Brand, CapColor, BodyColor))));

Model myPenSelecting /all/;
myPenSelecting.OptCR = 0;  
*OPTION MINLP = BARON;

x.l(Brand, 'black', 'black') = 1;
Solve myPenSelecting using MINLP minimizing Cost;
and it can be solved by DICOPT with status 2 Locally Optimal and by BARON with 1 Optimal.

Then, we further enrich this model.
  • Pen Selecting Problem 3 (PSP-3). Furthermore, we consider the user experience indices of the pens we selected. Assume that the user experience index of each pen is only related to its color style, which is described by table ExpIndex(CapColor, BodyColor) in GAMS.
So here we additionally declare variables Experience(Brand) and equations Constraint_3(Brand) in the code.

Code: Select all

$title Pen Selecting Problem 3 (PSP-3)
$ontext
There are three brands (A, B, and C) of pens in the store, each with four different color styles:
black cap & black body, black cap & white body, white cap & black body, and white cap & white body.
We know that pens of different color styles in diferent brands are sold at different prices.
Now we want to buy a pen from each of the three brands at minimal total cost.
How shall we select?
Now we add a new rule: If a mixed color pen (black cap & white body or white cap & black body) is 
selected from brand A, then a mixed color pen with the same style as the one from brand A (i.e. same
cap color and same body color) OR a single color (black cap & black body or white cap & white body) 
pen whose color is same as the body color of the pen from brand A must be select from brand B, and 
so on, for brand B and C.
Furthermore, we consider the user experience indices of the pens we selected. Assume that the user 
experience index of each pen is only related to its color style, which is described by table 
ExpIndex(CapColor, BodyColor). So here we additionally declare variables Experience(Brand) and equations 
Constraint_3(Brand).
$offtext

Sets
Brand /A, B, C/
CapColor /black, white/
;
alias(CapColor, BodyColor);

Table Price(Brand, CapColor, BodyColor)
            black     white
A.black       1         2
A.white       4         3
B.black       8         2
B.white       6         4
C.black       9        12
C.white       6         3
;
Table ExpIndex(CapColor, BodyColor)
        black   white
black    0.5     0.3
white    0.9     0.7             
;

Binary Variables
x(Brand, CapColor, BodyColor)
;
Variables
Cost
Experience(Brand)
;

Equations
Constraint_1(Brand)
Constraint_2(Brand, CapColor, BodyColor)
Constraint_3(Brand)
ObjFunc
;
Constraint_1(Brand)..
    sum(CapColor, sum(BodyColor, x(Brand, CapColor, BodyColor))) =e= 1;
Constraint_2(Brand, CapColor, BodyColor)$(ord(Brand) > 1)..
    (1 - x(Brand - 1, CapColor, CapColor)) * x(Brand - 1, CapColor, BodyColor) * (x(Brand, CapColor, BodyColor) + x(Brand, BodyColor, BodyColor))
     =e= (1 - x(Brand - 1, CapColor, CapColor)) * x(Brand - 1, CapColor, BodyColor);
Constraint_3(Brand)..
    Experience(Brand) =e= sum(CapColor, sum(BodyColor, ExpIndex(CapColor, BodyColor) * x(Brand, CapColor, BodyColor)));
ObjFunc..
    Cost =e= sum(Brand, sum(CapColor, sum(BodyColor, Price(Brand, CapColor, BodyColor) * x(Brand, CapColor, BodyColor))));

Model myPenSelecting /all/;
myPenSelecting.OptCR = 0;  
*OPTION MINLP = BARON;

x.l(Brand, 'black', 'black') = 1;
Solve myPenSelecting using MINLP minimizing Cost;
This model can also be normally solved: DICOPT gives status 2 Locally Optimal and BARON gives 1 Optimal.

However, when we consider a special case of the above model, problem arises.
  • Pen Selecting Problem 4 (PSP-4). Now let's consider a special case of PSP-3 where there are three brands (A, B, and C) of pens in the store, but each with only one color style: black cap & black body.
So the GAMS model of PSP-3 is modified as follow.

Code: Select all

$title Pen Selecting Problem 4 (PSP-4)
$ontext
There are three brands (A, B, and C) of pens in the store, each with four different color styles:
black cap & black body, black cap & white body, white cap & black body, and white cap & white body.
We know that pens of different color styles in diferent brands are sold at different prices.
Now we want to buy a pen from each of the three brands at minimal total cost.
How shall we select?
Now we add a new rule: If a mixed color pen (black cap & white body or white cap & black body) is 
selected from brand A, then a mixed color pen with the same style as the one from brand A (i.e. same
cap color and same body color) OR a single color (black cap & black body or white cap & white body) 
pen whose color is same as the body color of the pen from brand A must be select from brand B, and 
so on, for brand B and C.
Furthermore, we consider the user experience indices of the pens we selected. Assume that the user 
experience index of each pen is only related to its color style, which is described by table 
ExpIndex(CapColor, BodyColor). So here we additionally declare variables Experience(Brand) and equations 
Constraint_3(Brand).
Now let's consider a special case where there are three brands (A, B, and C) of pens in the store, 
but each with only one color style: black cap & black body. So the original model is modified as 
follow.
$offtext

Sets
Brand /A, B, C/
CapColor /black/
;
alias(CapColor, BodyColor);

Table Price(Brand, CapColor, BodyColor)
            black
A.black       1  
B.black       8  
C.black       9  
;
Table ExpIndex(CapColor, BodyColor)
        black
black    0.5  
;

Binary Variables
x(Brand, CapColor, BodyColor)
;
Variables
Cost
Experience(Brand)
;

Equations
Constraint_1(Brand)
Constraint_2(Brand, CapColor, BodyColor)
Constraint_3(Brand)
ObjFunc
;
Constraint_1(Brand)..
    sum(CapColor, sum(BodyColor, x(Brand, CapColor, BodyColor))) =e= 1;
Constraint_2(Brand, CapColor, BodyColor)$(ord(Brand) > 1)..
    (1 - x(Brand - 1, CapColor, CapColor)) * x(Brand - 1, CapColor, BodyColor) * (x(Brand, CapColor, BodyColor) + x(Brand, BodyColor, BodyColor))
     =e= (1 - x(Brand - 1, CapColor, CapColor)) * x(Brand - 1, CapColor, BodyColor);
Constraint_3(Brand)..
    Experience(Brand) =e= sum(CapColor, sum(BodyColor, ExpIndex(CapColor, BodyColor) * x(Brand, CapColor, BodyColor)));
ObjFunc..
    Cost =e= sum(Brand, sum(CapColor, sum(BodyColor, Price(Brand, CapColor, BodyColor) * x(Brand, CapColor, BodyColor))));

Model myPenSelecting /all/;
myPenSelecting.OptCR = 0;  
*OPTION MINLP = BARON;

x.l(Brand, 'black', 'black') = 1;
Solve myPenSelecting using MINLP minimizing Cost;
If we solve this model with solver DICOP, the Solution Report will be

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   myPenSelecting      OBJECTIVE  Cost
     TYPE    MINLP               DIRECTION  MINIMIZE
     SOLVER  DICOPT              FROM LINE  67

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      2 Locally Optimal           
**** OBJECTIVE VALUE               18.0000

 RESOURCE USAGE, LIMIT          0.000      1000.000
 ITERATION COUNT, LIMIT         4    2000000000
 EVALUATION ERRORS              0             0
while if we solve it with solver BARON, then the Solution Report is

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   myPenSelecting      OBJECTIVE  Cost
     TYPE    MINLP               DIRECTION  MINIMIZE
     SOLVER  BARON               FROM LINE  67

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      19 Infeasible - No Solution 
**** OBJECTIVE VALUE               NA

 RESOURCE USAGE, LIMIT          0.090      1000.000
 ITERATION COUNT, LIMIT        NA    2000000000
 EVALUATION ERRORS              0             0
As we can see, DICOPT can give a locally optimal solution for the model, while BARON gets a conclusion that it is not feasible. Why?

Thank you very much for your time and patience. I am not sure if I have stated the problem clearly. Look forward to your help.

cladelpino
User
User
Posts: 108
Joined: 1 year ago

Re: Why do DICOPT and BARON come to contradictory conclusions?

Post by cladelpino » 4 months ago

Just to add small data, COUENNE also reports 18.00 as the optimal solution, so BARON is not agreeing here. Furthermore, if you feed the solution back to BARON it is correctly identified as optimal.

PS: Are you aware that a MILP formulation can (I think) also be written for PSP-2 ?

wutuhan
User
User
Posts: 20
Joined: 4 months ago

Re: Why do DICOPT and BARON come to contradictory conclusions?

Post by wutuhan » 4 months ago

Thank you a lot. I know a MILP formulation can be written for PSP-2 and here I just want to describe the problem. In fact, I know that this problem can be avoided, but I just want to know the reason, although it seems that it is not so important.

Post Reply