Lower bound of non-convex problem not improving
AnsweredThe following is my code:
z = sdpvar(1);
f_a1 = sdpvar(n,1);
f_a2 = sdpvar(n,1);
for i = 1:n % Spans for all states
beta_c{i} = sdpvar(size(b{i},1),1);
beta_d{i} = sdpvar(size(b{i},1),1);
mu_c{i} = sdpvar(n*m,1);
mu_d{i} = sdpvar(n*m,1);
end
theta_c = sdpvar(n,1);
theta_d = sdpvar(n,1);
eta_c = sdpvar(n,1);
eta_d = sdpvar(n,1);
varsigma_c = sdpvar(n,1);
varsigma_d = sdpvar(n,1);
objective = z;
constraints = [
(1-alpha)*gamma*(varsigma_c - eta_c) <= z,
eta_c >= 0,
(1-alpha)*gamma*(varsigma_d - eta_d) <= ub,
eta_d >= 0,
f_a1 >= 0,
f_a2 >= 0,
f_a1 + f_a2 == 1,
f_a1 <=1,
f_a2 <=1,
z >= LB,
z <= UB,
];
for i = 1:n
constraints = [constraints,
f_a1(i)*c(i) + f_a2(i)*c(i) + beta_c{i}'*b{i} + mu_c{i}'*m_s + theta_c(i)*y(i) + eta_c(i) - I(i,:)*( I-alpha*( diag(f_a1)*P1 + diag(f_a2)*P2 ) )*varsigma_c == 0,
B{i}'*beta_c{i} - M_s*mu_c{i} - theta_c(i)*x_s - alpha*vertcat(f_a1(i)*I, f_a2(i)*I)*varsigma_c == 0,
norm(mu_c{i}, 2) <= theta_c(i),
beta_c{i} >=0,
theta_c(i) >= 0,
f_a1(i)*d(i) + f_a2(i)*d(i) + beta_d{i}'*b{i} + mu_d{i}'*m_s + theta_d(i)*y(i) + eta_d(i) - I(i,:)*( I-alpha*( diag(f_a1)*P1 + diag(f_a2)*P2 ) )*varsigma_d == 0,
B{i}'*beta_d{i} - M_s*mu_d{i} - theta_d(i)*x_s - alpha*vertcat(f_a1(i)*I, f_a2(i)*I)*varsigma_d == 0,
norm(mu_d{i}, 2) <= theta_d(i),
beta_d{i} >=0,
theta_d(i)
];
end
options = sdpsettings('solver','gurobi','verbose',1,'debug',1,'gurobi.Method', 3,'gurobi.MIPFocus',3);
optimize(constraints,objective,options);
LB and UB values are supplied by solving problems beforehand. But the best bound values stays the same (and is the LB value). The following is the log:
Optimize a model with 751 rows, 937 columns and 1009 nonzeros
Model fingerprint: 0xbcfc7f78
Model has 224 quadratic constraints
Coefficient statistics:
Matrix range [6e-02, 1e+00]
QMatrix range [3e-02, 1e+00]
QLMatrix range [5e-04, 9e+02]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 6e+02]
Warning: Only barrier available for SOCP models
Presolve removed 532 rows and 14 columns
Continuous model is non-convex -- solving as a MIP
Presolve removed 728 rows and 210 columns
Presolve time: 0.01s
Presolved: 1227 rows, 1022 columns, 7171 nonzeros
Presolved model has 196 quadratic constraint(s)
Presolved model has 294 bilinear constraint(s)
Variable types: 1022 continuous, 0 integer (0 binary)
Root relaxation presolve removed 1227 rows and 1022 columns
Root relaxation presolve: All rows and columns removed
Extra simplex iterations after uncrush: 294
Root relaxation: objective 2.050270e+02, 294 iterations, 0.01 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 205.02704 0 148 - 205.02704 - - 0s
H 0 0 214.2877027 205.02704 4.32% - 0s
0 0 205.02704 0 294 214.28770 205.02704 4.32% - 0s
0 0 205.02704 0 294 214.28770 205.02704 4.32% - 0s
0 2 205.02704 0 294 214.28770 205.02704 4.32% - 0s
1655 863 205.02704 22 168 214.28770 205.02704 4.32% 32.6 5s
4875 2376 205.02704 37 90 214.28770 205.02704 4.32% 51.2 10s
8350 3644 205.02704 45 122 214.28770 205.02704 4.32% 55.4 15s
10001 4264 205.02704 28 135 214.28770 205.02704 4.32% 60.8 20s
11262 4772 205.02704 17 90 214.28770 205.02704 4.32% 62.8 25s
12726 5461 205.02704 43 154 214.28770 205.02704 4.32% 68.6 34s
13053 5498 205.02704 42 143 214.28770 205.02704 4.32% 74.2 40s
H13353 5799 214.2876991 205.02704 4.32% 74.4 43s
13739 5938 205.02704 66 132 214.28770 205.02704 4.32% 75.3 45s
14538 6197 205.02704 57 145 214.28770 205.02704 4.32% 80.2 50s
15350 6531 205.02704 44 151 214.28770 205.02704 4.32% 84.3 56s
15693 6684 205.02704 44 103 214.28770 205.02704 4.32% 87.5 60s
H15765 6684 214.2876988 205.02704 4.32% 88.0 60s
17352 7130 infeasible 42 214.28770 205.02704 4.32% 88.5 68s
18010 7302 205.02704 45 154 214.28770 205.02704 4.32% 90.3 73s
18674 7444 infeasible 57 214.28770 205.02704 4.32% 91.7 76s
19330 7627 205.02704 66 74 214.28770 205.02704 4.32% 93.6 82s
H19525 7627 214.2876985 205.02704 4.32% 94.5 82s
H20171 7627 214.2876979 205.02704 4.32% 95.0 82s
20247 7755 205.02704 58 87 214.28770 205.02704 4.32% 95.3 87s
20811 7932 205.02704 41 77 214.28770 205.02704 4.32% 97.7 96s
21602 8049 205.02704 75 140 214.28770 205.02704 4.32% 99.2 101s
H22201 8343 214.2876787 205.02704 4.32% 101 111s
23321 8511 205.02704 63 84 214.28768 205.02704 4.32% 102 120s
24279 8779 205.02704 59 114 214.28768 205.02704 4.32% 104 129s
25351 8898 infeasible 57 214.28768 205.02704 4.32% 105 138s
26034 9147 infeasible 59 214.28768 205.02704 4.32% 107 148s
26929 9400 205.02704 62 68 214.28768 205.02704 4.32% 109 166s
28476 9854 205.02704 51 145 214.28768 205.02704 4.32% 109 186s
30360 10157 205.02704 63 77 214.28768 205.02704 4.32% 109 201s
32225 10602 infeasible 114 214.28768 205.02704 4.32% 109 217s
33886 11078 205.02704 89 100 214.28768 205.02704 4.32% 110 238s
Could you please help, what parameter should I possibly change to try getting some improvements?
-
Hi V,
Take a look at our section on Most Important Parameters in our documentation. I would start there, with parameters like MIPFocus and Presolve.
From your log we can see there is lots of branching, so you may wish to experiment with VarBranch or BranchDir (but note the docs say they rarely help).
I'd also experiment with our NoRelaxation heuristic.
Lastly, since you will be comparing the performance under different parameter settings, it may help to make yourself familiar with the following article: How can I make accurate comparisons?
- Riley
0 -
Hi, Thank you very much for the references.
One more question: When I vary the fixed parameters, some instances with MIPFocus=3 gives
Root relaxation: numerical trouble, 0 iterations, 0.00 seconds (0.00 work units)
Is this a scaling problem?
0 -
MIPFocus is a meta-parameter which is used to influence other parameters. I expect it is setting making the presolve routine aggressive, which can introduce numerical issues. Please refer to Solver Parameters to Manage Numerical Issues for ideas but in your case I would try setting Presolve=1, or Aggregate=1, or NumericFocus=1 when using MIPFocus=3 and see if that helps.
- Riley
0
Please sign in to leave a comment.
Comments
3 comments