Choose a solution that does not violate constraints for MIP

Danylo Malyuta

• 2019年05月01日 17:03

I am solving a mixed-integer second order cone program (MISOCP). Boolean variables pick among a set of inequality constraints using the big-M formulation (I choose M as small as possible). I scale and center the variables to [-1,1], but the optimization problem is still numerically tricky:

Coefficient statistics:
Matrix range [9e-07, 1e+02]
QMatrix range [1e+00, 1e+00]
Objective range [1e-02, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-03, 4e+00]

Gurobi can solve the problem but it returns:

Warning: max constraint violation (1.6024e-05) exceeds tolerance

As a result (I think), when I fix the integer variable to the optimal value found by Gurobi, the resulting second order cone program (SOCP) fails (I am guessing that its infeasibility tolerance is more sensitive that the MIP solver's).

My current "hack" is, if the SOCP fails, to add an extra constraint in the MISOCP to pick an integer variable that is not equal to the one returned in the first run. This picks "the next most optimal" integer variable and most of the time the SOCP works for that one. So, clearly, a solution to the MISOCP exists that is maybe not strictly the "most optimal", but which violates the constraints less.

My question: is there a setting in Gurobi that can make it pick a solution which does not exceed the constraint violation tolerance? What is a better way than my "hack" to resolve this issue, that uses Gurobi's features?

0

• 

  Jakob Schelbert

  • 2019年05月02日 14:56

  

  

  Hi Danylo,

  As you already mentioned, your problem has a very wide range of matrix coefficients which makes the it numerically challenging. See http://www.gurobi.com/documentation/8.1/refman/numerics_gurobi_guidelines.html for some insights that might help you.

  Is it feasible to not scale the problem to [-1,1] but let gurobi choose the scaling and the scale the result afterwards?

  You could also try to make use of the general constraints capabilities of gurobi (see http://www.gurobi.com/documentation/8.1/refman/py_model_addgenconstrindic.html).

  Also, have a look at the following parameters: http://www.gurobi.com/documentation/8.1/refman/premiqcpform.html#parameter:PreMIQCPForm http://www.gurobi.com/documentation/8.1/refman/numericfocus.html#parameter:NumericFocus http://www.gurobi.com/documentation/8.1/refman/barqcpconvtol.html#parameter:BarQCPConvTol

  0
• 

  Danylo Malyuta

  • 2019年05月02日 15:20

  

  

  

  Hi Jakob,

  Thank you for the fast response. How do I "let Gurobi choose the scaling and scale the result afterwards"? Also, I was able to convert the big-M constraints to constraints of the form A_i*x<=b_i*z_i where z_i is binary - so there are no more issues coming from big-M.

  Kind regards,

  Danylo.

  0
• 

  Jakob Schelbert

  • 2019年05月03日 06:42

  

  

  Hi Danylo,

  You wrote earlier that "I scale and center the variables to [-1,1]". I was assuming that by doing this you change the coefficients in your constraints. My suggestion would then be to just leave the original coefficients and let gurobi do scaling internally, then scale the variables afterwards. If this is not possible or I did not catch your intended approach then have a look at some of the other suggestions.

  You also wrote in your previous answer that you could eliminate the big-M constraints. Do you still have issues solving your models? If so, can you again provide the statistics of the model or - even better - post some of the solving log output.

  0

サインインしてコメントを残してください。