Why do DICOPT and BARON come to contradictory conclusions?
Why do DICOPT and BARON come to contradictory conclusions?
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!
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 6 years ago, edited 2 times in total.
Re: Why the solvers can only give local optimals of my model?
Hard to help you with this little info. Send log and/or model and perhaps someone can be of help.
-Michael
-Michael
Re: Why the solvers can only give local optimals of my model?
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.
The Solution Report of the model is
In fact, we know the feasible solutions and corresponding total weights and total values of this problem are as follow.
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
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
So, I have two main questions about this example:
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;
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
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
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
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
- 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?
Re: Why can the solvers only give local optimals of my model?
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":
Q2:
-Michael
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
(copy and paste from the DICOPT manual "Introduction", https://www.gams.com/latest/docs/S_DICOPT.html)Although the algorithm has provisions to handle non-convexities, it does not necessarily obtain the global optimum.
-Michael
Re: Why can the solvers only give local optimals of my model?
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.
If I solve my MINLP model myPRSMiT using solver DICOPT without any starting value, the Solution Report is
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)
and whose log is
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
and the log of which is
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?
Here I would like to provide some more information about it.wutuhan wrote: ↑6 years 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!
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
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
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
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
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
Last edited by wutuhan 6 years ago, edited 1 time in total.
Re: Why can the solvers only give local optimals of my model?
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
-Michael
Re: Why can the solvers only give local optimals of my model?
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.
Re: Why do DICOPT and BARON come to contradictory conclusions?
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.
Now we add an new rule to let PSP-1 become an MINLP.
and it can be solved by DICOPT with status 2 Locally Optimal and by BARON with 1 Optimal.
Then, we further enrich this model.
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.
If we solve this model with solver DICOP, the Solution Report will be
while if we solve it with solver BARON, then the Solution Report is
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.
- 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?
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;
- 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.
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;
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.
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;
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.
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;
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
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
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.
-
- User
- Posts: 108
- Joined: 7 years ago
Re: Why do DICOPT and BARON come to contradictory conclusions?
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 ?
PS: Are you aware that a MILP formulation can (I think) also be written for PSP-2 ?
Re: Why do DICOPT and BARON come to contradictory conclusions?
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.