How to intrepret and fix the following result
308 views
Skip to first unread message
Harprinder
Aug 9, 2021, 3:43:57 PM8/9/21
to AMPL Modeling Language
Hi,
I want to intrepret the following result. My optimization problem does have binary variables.
CPLEX 20.1.0.0: optimal (non-)integer solution; objective 56773.6609
33877 MIP simplex iterations
6396 branch-and-bound nodes
absmipgap = 7.27596e-12, relmipgap = 1.27873e-16
2 integer variables rounded (maxerr = 1.33576e-09).
Assigning integrality = 7e-10 might help.
Currently integrality = 1e-05.
Did it found the optimal solution? Should I change anything? How to fix it? Is there any issue in the modeling?
Harprinder
Harprinder
Aug 9, 2021, 3:45:31 PM8/9/21
to AMPL Modeling Language
The previous version of AMPL wasn't giving such results for the same problem. I just got new license and find these weird results.
Harprinder
AMPL Google Group
Aug 10, 2021, 6:18:21 PM8/10/21
to AMPL Modeling Language
Try adding integrality=7e-10 to your cplex_options string; or if you are not setting a cplex_options string yet, give the command
option cplex_options 'integrality=7e-10';
before you solve. If still you get the "optimal (non-)integer solution" message, then use integrality=0 instead.
Here's some explanation: CPLEX's solution procedure treats slightly fractional variables as if they were integral. Specifically, by default, if a variable's value is closer than 1e-05 to an integer value, CPLEX's solution procedure treats the variable the same as one that has exactly an integer value. Then at the end of the CPLEX run, there may be some integer (including binary) variables that have slightly fractional values in the optimal solution, and CPLEX has to clean up by rounding them to integers. In your example, two binary variables were rounded by as much as 1.33576e-09, which is probably too small to make a difference.
CPLEX's integrality parameter determines how close to an integer a variable has to be before it is treated as an integer. The default is 1e-05, but by changing it to a sufficiently small value, you can eliminate any messages about rounding (though CPLEX may take a little longer to return a solution).
option cplex_options 'integrality=7e-10';
before you solve. If still you get the "optimal (non-)integer solution" message, then use integrality=0 instead.
Here's some explanation: CPLEX's solution procedure treats slightly fractional variables as if they were integral. Specifically, by default, if a variable's value is closer than 1e-05 to an integer value, CPLEX's solution procedure treats the variable the same as one that has exactly an integer value. Then at the end of the CPLEX run, there may be some integer (including binary) variables that have slightly fractional values in the optimal solution, and CPLEX has to clean up by rounding them to integers. In your example, two binary variables were rounded by as much as 1.33576e-09, which is probably too small to make a difference.
CPLEX's integrality parameter determines how close to an integer a variable has to be before it is treated as an integer. The default is 1e-05, but by changing it to a sufficiently small value, you can eliminate any messages about rounding (though CPLEX may take a little longer to return a solution).
--
Robert Fourer
am...@googlegroups.com
On Mon, Aug 9, 2021 at 7:45 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
The previous version of AMPL wasn't giving such results for the same
problem. I just got new license and find these weird results.
Harprinder
Harprinderjot Singh
Aug 10, 2021, 7:07:10 PM8/10/21
to am...@googlegroups.com
Okay. Thank you for the explanation. I have one more question. Shouldn't the smaller value of integrality be more hard constraint as it has to be more close to the integer. How it is working the other way? A
Also, what would it mean for setting integrality exactly 0? Wouldn't it affect the solution substantially?
Can the values of integrality be less than 0 or way smalller.
Harprinder
--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1596168297-4653256920-1628633898-784477693%40helpscout.net.
AMPL Google Group
Aug 11, 2021, 12:30:37 PM8/11/21
to AMPL Modeling Language
Values of the integrality parameter must be >= 0.
With integrality=0, the solver's branch-and-bound algorithm considers a binary variable to have an integer value if it equals exactly 0 or 1, and to have a fractional value otherwise. The is the usual mathematical way of defining integrality in the algorithm, and it will give the most precise results, but also requires the most work.
With integrality=1e-05, the algorithm considers a binary variable to have an integer value if it is <= 0.00001 or if it is >= 0.99999. This is a more numerically robust way of defining integrality, it requires less work, and occasionally it gives a useful solution when integrality=0 reports no feasible solution. But it does sometimes give less precise results.
Similarly with integrality=7e-10, the algorithm considers a binary variable to have an integer value if it is <= 0.0000000007 or if it is >= 0.9999999993. So this gives results that have properties in between integrality=1e-05 and integrality=0.
It is only in some rare cases that the integrality parameter makes a difference. For most MIPs that I have seen, the integrality setting does not affect the operation of the algorithm, and the solution using integrality=1e-05 is the same as the solution using integrality=0.
With integrality=0, the solver's branch-and-bound algorithm considers a binary variable to have an integer value if it equals exactly 0 or 1, and to have a fractional value otherwise. The is the usual mathematical way of defining integrality in the algorithm, and it will give the most precise results, but also requires the most work.
With integrality=1e-05, the algorithm considers a binary variable to have an integer value if it is <= 0.00001 or if it is >= 0.99999. This is a more numerically robust way of defining integrality, it requires less work, and occasionally it gives a useful solution when integrality=0 reports no feasible solution. But it does sometimes give less precise results.
Similarly with integrality=7e-10, the algorithm considers a binary variable to have an integer value if it is <= 0.0000000007 or if it is >= 0.9999999993. So this gives results that have properties in between integrality=1e-05 and integrality=0.
It is only in some rare cases that the integrality parameter makes a difference. For most MIPs that I have seen, the integrality setting does not affect the operation of the algorithm, and the solution using integrality=1e-05 is the same as the solution using integrality=0.
--
Robert Fourer
am...@googlegroups.com
On Tue, Aug 10, 2021 at 11:07 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
Okay. Thank you for the explanation. I have one more question. Shouldn't the smaller value of integrality be more hard constraint as it has to be more close to the integer. How it is working the other way? A
Also, what would it mean for setting integrality exactly 0? Wouldn't it affect the solution substantially?
Can the values of integrality be less than 0 or way smalller.
Harprinder
On Tue, Aug 10, 2021 at 10:17 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:
Try adding integrality=7e-10 to your cplex_options string; or if you are not setting a cplex_options string yet, give the command
option cplex_options 'integrality=7e-10';
before you solve. If still you get the "optimal (non-)integer solution" message, then use integrality=0 instead.
Here's some explanation: CPLEX's solution procedure treats slightly fractional variables as if they were integral. Specifically, by default, if a variable's value is closer than 1e-05 to an integer value, CPLEX's solution procedure treats the variable the same as one that has exactly an integer value. Then at the end of the CPLEX run, there may be some integer (including binary) variables that have slightly fractional values in the optimal solution, and CPLEX has to clean up by rounding them to integers. In your example, two binary variables were rounded by as much as 1.33576e-09, which is probably too small to make a difference.
CPLEX's integrality parameter determines how close to an integer a variable has to be before it is treated as an integer. The default is 1e-05, but by changing it to a sufficiently small value, you can eliminate any messages about rounding (though CPLEX may take a little longer to return a solution).
--
Robert Fourer
am...@googlegroups.com
Harprinderjot Singh
Aug 11, 2021, 5:38:28 PM8/11/21
to am...@googlegroups.com
Okay. Now it make sense.
Thank you very much for all information.
Harprinder
--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-1596168297-4655720559-1628699434-2079802246%40helpscout.net.
Harprinderjot Singh
Aug 12, 2021, 5:49:12 PM8/12/21
to am...@googlegroups.com
Another clarification. Is the solution obtain using (non-)integer solution is also the optimal solution? I guess so with binary variable in the range close to integrality. I change the integrality to 1e-11 and it has increased time substantially and as I have to do multiple runs it made problem complicated. I want to clarify the problem. I have a variable y varying over a set of t={1,2,3,.....24} which can take positive or negative value.
However, if it takes positive value then OBJ function is:
OBJ:Sum_t{a*y[t]}+linear combination of other variables
if y is negative, it should be:
OBJ: Sum_t {b*y[t]}+linear combination of other variables.
Here, a and b are constants.
To address this I introduced binary variables x over the set t and OBJ and additional constraint is as follows:
OBJ: Sum_t [ax[t]+b*(1-x[t])]*y[t] + linearcombination of other variables.
s.t.:
y[t]>=(x[t]-1)*M
y[t]<=M*x[t]
Where, M is a constant very large number 10^6. However, it introduces non linearity to the problem. To address the non linearity. I modified the problem with new variable as z, as follows:
OBJ:Sum_t z[t]+linear combination of other variables
s.t:
y[t]>=(x[t]-1)*M
y[t]<=M*x[t]
z[t]-Mx[t]<=y[t]*b<=z[t]+M*x[t]
z[t]-M*(1-x[t])<=y[t]*a<=z[t]+M*(1-x[t])
Then it should automatically set z[t] with what I desired keeping the problem linear. I wanted to confirm if there is any easier, different and faster way to handle this problem? Should, I trust the solution of CPLEX based on the above changes? Shall, I change the solver? Any insights would be welcome.
Harprinder
AMPL Google Group
Aug 13, 2021, 1:22:19 PM8/13/21
to AMPL Modeling Language
The solution that you see when CPLEX reports "optimal (non-)integer solution" is usually optimal, but there is a small chance there will be a better solution.
Using a "big M" value like 10^6 is a common cause of the integer rounding messages that you are seeing. If you can use a smaller value without making the constraints invalid, that might help. Also, while other MIP solvers also have an integrality tolerance, one solver might do a better job than another in automatically reducing the big M values. Thus you might want to try Gurobi and/or Xpress, if you have them available.
Finally, a function that is a*y[t] where y[t] >= 0 and b*y[t] where y[t] <= 0 is a piecewise-linear function as described in Chapter 17 of the AMPL book. As explained there, AMPL has a special notation for this function:
<<0; b,a>> y[t]
See in particular the discussion of "Reversible activities" on page 377. AMPL automatically linearizes any expression like this that appears in the model, adding binary variables when b > a (if minimizing) or b < a (if maximizing). If binary variables are needed, however, then you will want to take care to put reasonable lower and upper bounds on the y[t] variables, as lack of reasonable bounds leads to large "big M" values in the linearization.
Using a "big M" value like 10^6 is a common cause of the integer rounding messages that you are seeing. If you can use a smaller value without making the constraints invalid, that might help. Also, while other MIP solvers also have an integrality tolerance, one solver might do a better job than another in automatically reducing the big M values. Thus you might want to try Gurobi and/or Xpress, if you have them available.
Finally, a function that is a*y[t] where y[t] >= 0 and b*y[t] where y[t] <= 0 is a piecewise-linear function as described in Chapter 17 of the AMPL book. As explained there, AMPL has a special notation for this function:
<<0; b,a>> y[t]
See in particular the discussion of "Reversible activities" on page 377. AMPL automatically linearizes any expression like this that appears in the model, adding binary variables when b > a (if minimizing) or b < a (if maximizing). If binary variables are needed, however, then you will want to take care to put reasonable lower and upper bounds on the y[t] variables, as lack of reasonable bounds leads to large "big M" values in the linearization.
--
Robert Fourer
am...@googlegroups.com
On Thu, Aug 12, 2021 at 9:49 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
Another clarification. Is the solution obtain using (non-)integer solution is also the optimal solution? I guess so with binary variable in the range close to integrality. I change the integrality to 1e-11 and it has increased time substantially and as I have to do multiple runs it made problem complicated. I want to clarify the problem. I have a variable y varying over a set of t={1,2,3,.....24} which can take positive or negative value.
However, if it takes positive value then OBJ function is:
OBJ:Sum_t{a*y[t]}+linear combination of other variables
if y is negative, it should be:
OBJ: Sum_t {b*y[t]}+linear combination of other variables.
Here, a and b are constants.
To address this I introduced binary variables x over the set t and OBJ and additional constraint is as follows:
OBJ: Sum_t [ax[t]+b*(1-x[t])]*y[t] + linearcombination of other variables.
s.t.:
y[t]>=(x[t]-1)*M
y[t]<=M*x[t]
Where, M is a constant very large number 10^6. However, it introduces non linearity to the problem. To address the non linearity. I modified the problem with new variable as z, as follows:
OBJ:Sum_t z[t]+linear combination of other variables
s.t:
y[t]>=(x[t]-1)*M
y[t]<=M*x[t]
z[t]-Mx[t]<=y[t]*b<=z[t]+M*x[t]
z[t]-M*(1-x[t])<=y[t]*a<=z[t]+M*(1-x[t])
Then it should automatically set z[t] with what I desired keeping the problem linear. I wanted to confirm if there is any easier, different and faster way to handle this problem? Should, I trust the solution of CPLEX based on the above changes? Shall, I change the solver? Any insights would be welcome.
Harprinder
On Wed, Aug 11, 2021 at 9:38 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
Okay. Now it make sense.
Thank you very much for all information.
Harprinder
On Wed, Aug 11, 2021 at 4:30 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:
Values of the integrality parameter must be >= 0.
With integrality=0, the solver's branch-and-bound algorithm considers a binary variable to have an integer value if it equals exactly 0 or 1, and to have a fractional value otherwise. The is the usual mathematical way of defining integrality in the algorithm, and it will give the most precise results, but also requires the most work.
With integrality=1e-05, the algorithm considers a binary variable to have an integer value if it is <= 0.00001 or if it is >= 0.99999. This is a more numerically robust way of defining integrality, it requires less work, and occasionally it gives a useful solution when integrality=0 reports no feasible solution. But it does sometimes give less precise results.
Similarly with integrality=7e-10, the algorithm considers a binary variable to have an integer value if it is <= 0.0000000007 or if it is >= 0.9999999993. So this gives results that have properties in between integrality=1e-05 and integrality=0.
It is only in some rare cases that the integrality parameter makes a difference. For most MIPs that I have seen, the integrality setting does not affect the operation of the algorithm, and the solution using integrality=1e-05 is the same as the solution using integrality=0.
--
Robert Fourer
am...@googlegroups.com
Harprinderjot Singh
Aug 31, 2021, 11:40:12 AM8/31/21
to am...@googlegroups.com
I implemented the piece-wise linear function as in the suggestions that were mentioned. However, I just want to confirm if the AMPL treats this piece-wise linear function as linear programming problem. In other words, can I use CPLEX to solve this piece-wise linear function? (as cplex is used for linear problems)
Harprinder
AMPL Google Group
Aug 31, 2021, 6:29:29 PM8/31/21
to AMPL Modeling Language
AMPL transforms models that contain piecewise-linear functions to equivalent linear models. So you can use CPLEX (or any other linear solver).
--
Robert Fourer
am...@googlegroups.com
On Tue, Aug 31, 2021 at 3:40 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
I implemented the piece-wise linear function as in the suggestions that were mentioned. However, I just want to confirm if the AMPL treats this piece-wise linear function as linear programming problem. In other words, can I use CPLEX to solve this piece-wise linear function? (as cplex is used for linear problems)
Harprinder
On Fri, Aug 13, 2021 at 5:21 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:
The solution that you see when CPLEX reports "optimal (non-)integer solution" is usually optimal, but there is a small chance there will be a better solution.
Using a "big M" value like 10^6 is a common cause of the integer rounding messages that you are seeing. If you can use a smaller value without making the constraints invalid, that might help. Also, while other MIP solvers also have an integrality tolerance, one solver might do a better job than another in automatically reducing the big M values. Thus you might want to try Gurobi and/or Xpress, if you have them available.
Finally, a function that is a*y[t] where y[t] >= 0 and b*y[t] where y[t] <= 0 is a piecewise-linear function as described in Chapter 17 of the AMPL book. As explained there, AMPL has a special notation for this function:
<<0; b,a>> y[t]
See in particular the discussion of "Reversible activities" on page 377. AMPL automatically linearizes any expression like this that appears in the model, adding binary variables when b > a (if minimizing) or b < a (if maximizing). If binary variables are needed, however, then you will want to take care to put reasonable lower and upper bounds on the y[t] variables, as lack of reasonable bounds leads to large "big M" values in the linearization.
--
Robert Fourer
am...@googlegroups.com
Reply all
Reply to author
Forward
0 new messages