Constraint violation in finding the extreme ray.
AnsweredDear Madam or Sir,
I am using Gurobi to run an optimisation problem as following
maximize c^T x
subject to A x <=b
I implement this problem using C++. I run the same piece of code on two different machines, my own laptop (Mac) and a HPC from my university. My laptop gives an extreme ray that is correct. However, the HPC gives me an extreme ray that even violates the constraint specified.
I have been searching the Google for a couple of days to try to find a solution. However, I could not solve this problem. I really need to solve it and know why this happens. Could you please help me?
Please find enclosed one file which includes the parameters of the problem, the other file which includes the extreme ray obtained by GUROBI on my laptop and on the HPC, and the piece of code. Please note that I have multiplies the extreme ray obtained by a factor 1000. If I do not multiplies the factor, the extreme rays obtained from HPC is also feasible. However, as it is the extreme ray, we can multiply it by any factor and the vector should also be feasible to the problem. I need to multiply the factor so that I can do the column generation later. If you need any further information, please let me know. Thank you very much!
Best wishes,
Chao
this is the c vector
0.14 0.3 0.23 0.33 0.01 0.21 0.52 0.26 0.02 0.42 0.37 0.19 0.19 0.28 0.53 0.01 0.23 0.16 0.39 0.21 0 0.37 0.21 0.42 0.08 0.55 0.37 0.35 0.65 0.38 0.62 0.14 0.47 0.39
This is the A matrix
0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1
0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1
0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0
1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0
0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0
0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0
1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0
0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0
0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0
0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1
0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1
0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1
0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1
0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0
This is the b vector
5.5 9.71 5.5 5.5 9.39 0 5.5 0 9.71 5.5 9.39 5.5 0 5.5 5.5 9.71 9.39 9.39 9.39 9.71 9.39 5.5 5.5 5.5 5.5 9.71 5.5 5.5
This is the result obtained from different machines
Result from my Laptop
The extreme ray is
0 0 1000 1000 -1000 -1000 -1000 -2000 0 1000 0 -1000 1000 0 1000 1000 1000 0 0 0 -1000 -1000 -1000 0 0 0 2000 0 -1000 -1000 0 1000 0 1000
The extreme ray founded satisfies all constraints
Result from the HPC
The extreme ray is
0 0 0 0 -500 -500 0 0 0 500 0 0 0 0 0 0 0 500 0 0 0 -500 0 0 500 0 0 0 0 0 0 0 0 0
Does not satisfy the constraint as 1000 > 9.39
int main() {
string file_path = "/Users/wz/Documents/one_case/";
int size_u = 34, size_constraint = 28; vector<double> p_vec(size_u), reveneu_vec(size_constraint); vector<vector<int>> A_T(size_constraint);
double read_value_d; int read_value_i;
string line_HPC;
stringstream filename_HPC;
filename_HPC << file_path << "data.txt";
ifstream fin_HPC (filename_HPC.str().c_str());
if (!fin_HPC.is_open()) {
// leave -1's in the raw data tables
cout << "No file named ---------" << filename_HPC.str() << " OR " << filename_HPC.str() <<endl;
} else{
while (getline(fin_HPC, line_HPC)){
if(line_HPC == "this is the c vector "){
for (int i = 0; i < size_u; ++i){
fin_HPC>> read_value_d;
p_vec[i] =read_value_d;
}
}
if(line_HPC == "This is the A matrix"){
for (int i = 0; i < size_constraint; ++i){
vector<int> one_row(size_u);
for(int j=0; j < size_u; ++j){
fin_HPC >> read_value_i;
one_row[j] = read_value_i;
}
A_T[i] = one_row;
}
}
if(line_HPC == "This is the b vector"){
for(int i=0; i < size_constraint; ++i){
fin_HPC >> read_value_d;
reveneu_vec[i] = read_value_d;
}
}
}
}
// Check if the GUROBI running is correct.
GRBEnv *env = new GRBEnv();
GRBModel model = GRBModel (*env);
model.set(GRB_IntParam_OutputFlag, 0);
model.set (GRB_IntParam_Threads, 4);
model.set(GRB_DoubleParam_TimeLimit, 3600);
GRBVar *u = model.addVars (size_u,GRB_CONTINUOUS);
GRBVar tau = model.addVar (-GRB_INFINITY , GRB_INFINITY, 1.0, GRB_CONTINUOUS); // epigraphical variable for objective function
// set up objective function
model.set (GRB_IntAttr_ModelSense, GRB_MAXIMIZE);
for (int i = 0; i < size_u; ++i){
u[i].set(GRB_DoubleAttr_LB,-GRB_INFINITY);
}
GRBLinExpr expr;
// epigraphical constraints: tau <= p'u
expr = 0;
cout << "this is the c vector " <<endl;
for (int k = 0; k < size_u; ++k){
expr += p_vec[k] * u[k];
cout << p_vec[k] << " ";
}
cout << endl;
model.addConstr (tau <= expr);
// Constraints A^{pi}' u <= gamma^{pi} + sum_{j <= n} alpha^{pi}_j x_j + sum_{j <= n} beta^{pi}_i (1-x_i)
cout << "This is the A matrix" <<endl;
for (int preference_id = 0; preference_id < size_constraint; ++ preference_id){
expr = 0;
for (int l = 0; l <size_u; ++l){
expr += A_T[preference_id][l]*u[l];
cout << A_T[preference_id][l] << " ";
}
cout << endl;
model.addConstr (expr <= reveneu_vec[preference_id]);
}
cout << "This is the b vector" <<endl;
for( int u_id = 0; u_id < size_constraint; ++u_id)
cout << reveneu_vec[u_id] << " ";
cout <<endl;
// solve the problem
model.optimize();
model.set(GRB_IntParam_InfUnbdInfo, 1);
// If the problem is not feasible
int optimal_status = model.get(GRB_IntAttr_Status);
if (optimal_status == GRB_INF_OR_UNBD){
model.set(GRB_IntParam_Presolve, 0);
model.optimize();
optimal_status = model.get(GRB_IntAttr_Status);
}
// Get the extreme ray
if(optimal_status == 5){
vector<double> extreme_u_ray(size_u);
cout << "The extreme ray is " << " ";
for (int l = 0; l< size_u; ++l){
extreme_u_ray[l] = u[l].get(GRB_DoubleAttr_UnbdRay); // Here, it is becuase we have multiplied a factor 1000.
cout << extreme_u_ray[l] << " ";
}
cout << endl;
bool satisfy_all_constraints = true;
for (int preference_id = 0; preference_id < size_constraint; ++ preference_id){
double left_value = 0;
for (int l = 0; l <size_u; ++l){
left_value += A_T[preference_id][l]*extreme_u_ray[l];
}
if(left_value > reveneu_vec[preference_id]){
satisfy_all_constraints = false;
cout << "Does not satisfy the constraint as " << left_value << " > " << reveneu_vec[preference_id] <<endl;
break;
}
}
if(satisfy_all_constraints)
cout << "The extreme ray founded satisfies all constraints" <<endl;
} else {
cout<<"Wired, the problem does not seem to be unbounded !!!!!!!!!!!" <<endl;
exit(-1);
}
delete []u;
}
-
Hi Chao,
The constraint corresponding to 9.39 and the extreme ray you produced are
0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0
0 0 0 0 -500 -500 0 0 0 500 0 0 0 0 0 0 0 500 0 0 0 -500 0 0 500 0 0 0 0 0 0 0 0 0The HPC extreme ray adds up to 0, because you have \( (- 500 + 500)\) as these are the only variables participating with a \(1\) coefficient. Thus, the constraint is satisfied.
It is normal to see different solutions provided by Gurobi when executed on different machines. For more information, see [Is Gurobi Optimizer deterministic?](https://support.gurobi.com/hc/en-us/articles/360031636051-Is-Gurobi-Optimizer-deterministic-)
Best regards,
Jaromił -
Hi Jaromil,
Thank you for your help. I agree that this constraint is satisfied. However, there is another constraint (the 11th line in A matrix) that is not satisfied.
0 0 0 0 -500 -500 0 0 0 500 0 0 0 0 0 0 0 500 0 0 0 -500 0 0 500 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0Thank you very much if you could have a look at this one.
Best wishes,
Chao
-
Hi Chao,
This is correct. However, please note that the original solution point satisfies the constraint. You are, correct that you can scale the objective function, but you also have to scale the constraints properly. As an example take
\[\begin{align} \min_x &-x \\ \text{s.t.} &x \leq 1 \end{align}\]
The optimal solution point is \(x=1\). Now, when you multiply \(x\) with \(1000\) the constraint \(x \leq 1\) is no longer satisfied, because \(1000\not\leq 1\). In this case you have to scale the constraint by \(1000\) as well.
Best regards,
Jaromił -
Hi Jaromil,
I agree with your example. However, in your example, the problem is bounded so the solution you proposed is not an extreme ray.
On the contrary, in my case, I am trying to obtain an extreme ray from GUROBI as my problem is unbounded. As I said, for an extreme ray, we can multiply any large positive factor without violate the constraint. So my example above show that GUROBI on the HPC does not give me a correct extreme ray.
Thank you!
Best wishes,
Chao
Please sign in to leave a comment.
Comments
7 comments