Forum Discussion
Xpress solver claims suboptimal solution to be optimal
Hi, I'm working on a inventory assignment problem with future arrival assignment as well. Basically, there are:
- a constant onhand value, and
- constant known demand[S, L, T] for sku S at location L at time T.
- constant known future arrival[S, L, T] for sku S at location L at time T.
Then there are decision variables:
- x[S, L, T] for the volume assigned for demand[S, L, T] from initial on-hand.
- y[S, L, T, L1, T1] for redirecting future arrival from location L at T to demand location T1 at time T1
- Also support D.V. of shortage delta[S, L, T] for the shortage to fulfill demand[S, L, T]
- And an indicator epsilong[S, L, T] is binary telling if demand[S, L, T] is not fully fulfilled.
The wired observation I had is, I used higher penalty for on x and lower penalty on y in objective function. However, Xpress didn't give me the solution I desire.
with objective value = 5.360416666665202e-03
and solution on x:
{
('135', 'N', 1): 10.0,
('135', 'N', 3): 20.0
('135', 'N', 6): 0.0,
}
However, if I force x['135', 'N', 1] = 20.0,, it returned the solution I want with objective value = 5.277916666666667e-03.
As this is a minimization problem, thus, Xpress solver didn't find the optimal solution in the first round, and my arbitrary assignment gave a better solution.
I wonder if it is because of any know solver limitation or my configuration has problem that triggered this solver behavior to declare a suboptimal solution to be optimal.
Thanks a lot
Appendix of additional info:
The .lp file is as following and config using is:
solver_config = {
"miprelstop": 0.05, # optimality gap tolerance
"MIPTOL": 1e-5, # MIP numerical tolerance
"feastol": 1e-5, # feasiblity numerical tolerance
"thread": 1, # number of thread used
"maxtime": 900, # max number of seconds allowed on solving
"MAXSTALLTIME": 300, # max time the Optimizer continue to search for improving solution after finding a new incumbent
}
\Problem name: noname
\FICO Xpress v8.13.0, Hyper, written 10:53:53, Feb 29, 2024
Minimize
0.00018333333333333334 y_135_N_1_N_3
+ 0.00017083333333333333 y_135_N_1_N_6
+ 0.00019166666666666667 y_135_N_1_N_1
+ 7.500000000000001e-07 x_135_N_6 + 9.583333333333336e-07 x_135_N_1
+ 8.750000000000001e-07 x_135_N_3 + 1.0333333333333334 delta_135_N_6
+ 1.04 delta_135_N_1 + 1.037037037037037 delta_135_N_3
Subject To
R123: y_135_N_1_N_6 + x_135_N_6 + delta_135_N_6 = 20
R124: y_135_N_1_N_1 + x_135_N_1 + delta_135_N_1 = 20
R125: y_135_N_1_N_3 + x_135_N_3 + delta_135_N_3 = 20
R126: x_135_N_6 + x_135_N_1 + x_135_N_3 <= 30
R127: y_135_N_1_N_3 + y_135_N_1_N_6 + y_135_N_1_N_1
<= 30
R128: - 0.025 delta_135_N_6 + epsilon135_N_6 >= 0
R129: - 0.025 delta_135_N_1 + epsilon135_N_1 >= 0
R130: - 0.025 delta_135_N_3 + epsilon135_N_3 >= 0
R131: - 40 delta_135_N_6 + epsilon135_N_6 <= 0
R132: - 40 delta_135_N_1 + epsilon135_N_1 <= 0
R133: - 40 delta_135_N_3 + epsilon135_N_3 <= 0
R134: x_135_N_6 >= 0
R135: x_135_N_1 >= 0
R136: x_135_N_3 >= 0
R137: y_135_N_1_N_3 >= 0
R138: y_135_N_1_N_6 >= 0
R139: y_135_N_1_N_1 >= 0
R140: delta_135_N_6 >= 0
R141: delta_135_N_1 >= 0
R142: delta_135_N_3 >= 0
Bounds
Generals
y_135_N_1_N_3 y_135_N_1_N_6 y_135_N_1_N_1
x_135_N_6 x_135_N_1 x_135_N_3 delta_135_N_6 delta_135_N_1
delta_135_N_3
Binaries
epsilon135_N_6 epsilon135_N_1 epsilon135_N_3
End
Engine log without arbitrary assignment:
*** Solution found: 41.409334 Time: 0 Heuristic: T ***
*** Solution found: .005360 Time: 0 Heuristic: e ***
Its Obj Value S Ninf Nneg Sum Dual Inf Time
0 -41.398365 D 4 0 .000000 0
3 .005360 D 0 0 .000000 0
Problem is cut off
*** Search completed ***
Uncrunching matrix
Final MIP objective : 5.360416666665202e-03
Final MIP bound : 5.350416666665202e-03
Solution time / primaldual integral : 0s/ 100.000000%
Number of solutions found / nodes : 2 / 0
Max primal violation (abs/rel) : 0.0 / 0.0
Max integer violation (abs ) : 0.0
Engine log with arbitrary assignment:
Final objective : 5.277916666666667e-03
Max primal violation (abs/rel) : 0.0 / 0.0
Max dual violation (abs/rel) : 0.0 / 0.0
Max complementarity viol. (abs/rel) : 0.0 / 0.0
Starting root cutting & heuristics
Its Type BestSoln BestBound Sols Add Del Gap GInf Time
a .005278 .005278 2 0.00% 0 0
*** Search completed ***
Uncrunching matrix
Final MIP objective : 5.277916666666666e-03
Final MIP bound : 5.277916666666666e-03
Solution time / primaldual integral : 0s/ 97.927631%
Number of solutions found / nodes : 2 / 1
Max primal violation (abs/rel) : 0.0 / 0.0
Max integer violation (abs ) : 0.0
2 Replies
In general I think your observation is not too surprising: by default Xpress is allowed to stop if a solution is "optimal within tolerances". In particular, there are tolerances mipabsstop and miprelstop that allow Xpress to stop with a non-zero gap. You even set miprelstop=0.05 and the relative difference of the two solutions is below that limit. Does the problem persist if you set both of these controls to 0?
What is strange in your case is that the second solution (5.277916666666666e-03) is better than the best dual bound in the first run (5.350416666665202e-03). That should not be since it indeed means that the first run missed a solution.
On the other hand, you are explicitly setting the feasibility tolerance to 1e-5 while you have coefficients of 1e-7. Does the problem persist if you tighten the feasibility tolerance?
Also, you are using a rather old version of Xpress. Does the problem persist if you switch to a newer/the most recent version?
If you post further logs, could you please post the full log? The full log should display Xpress version number as well as non-default parameter settings at the beginning. This is important information when trying to investigate potential issues.
Nice findings and insights, yeah, the config seems like messed it up. Thanks!!
