Sensitivity analysis and Computational complexity for MIP

[Thiruselvan S]

Hi all,

I have solved a mixed integer program for my class assignment in AIMMS. Please help me in how to do sensitivity analysis and derive the computational complexity of the MIP problem. I have gone through AIMMS Modeling Guide - Sensitivity Analysis (Chapter 4). In that they mentioned only for linear programming and said there are limitations for integer programming. 

-- 

Thanks & Regards,

Thiruselvan S

[Guido Diepen]

Hi Thiruselvan,

regarding the sensitivity analysis on a MIP problem, this actually was explained in a recent answer by Peter in the thread https://groups.google.com/d/topic/aimms/yyfOgs-bbTo/discussion

Regarding the computational complexity of the MIP problem, in general MIP problems are NP hard (see also the excellent post by Jean Francois Puget about this: https://www.ibm.com/developerworks/community/blogs/jfp/entry/np_or_not_np_that_is_the_question49?lang=en). If your MIP model has some very specific properties, it might be possible that the solution to the LP relaxation of your MIP is actually an integer solution. In this case, it means you can actually solve your problem in polynomial time.

Guido Diepen

[José Magalhaes Jr.]

HI Guido Diepen !

Thanks for you answer. 

I am facing the same situation of Thirulselvan.

My problem is a MIP problem  and I´d like to perform a Sensitivity Analysis.

In the AIMMS documentation, there is the following explanation:

 "If you want to apply these types of analysis to the final solution of a mixed-integer

program, you should fix all integer variables to their final solution (using the

.NonVar sufix) and re-solve the resulting mathematical program as a linear

program (e.g. by adding the clause WHERE type:=’lp’ to the SOLVE statement)."

It seems that I have to run the project twice.

Firts, Solve the problem (project) as a MIP;

And then, fix the binary/integer variables and solve the problem "again" as LP problem.

Guido, I don´t know how to do it.

Please, could you help me?

I understant the logic (idea) to perform the Sensitivity Analysis in MIP problem,

But I don´t know how to implement it in AIMMS.

Could you send me a Screenshot of a simple example of MIP Problem with Sensitivity Analysis ?!

Some "Step-by-step" explanation showing the implementation of Sensitivity Analysis in MIP problem.

Thank you very much for all help. 

Best Regards,

            José.

--
You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling System" group.
To unsubscribe from this group and stop receiving emails from it, send an email to aimms+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Marcel Hunting]

Hi,

If you are interested in shadow prices or reduced costs then AIMMS can calculate them automatically for you (during a postsolve step) if you solve your MIP. The easiest way is to switch on the general solvers option 'Always store marginals' but you can also set the ReducedCost or ShadowPrice property of the variables and constraints you are interested in.

For CPLEX and Gurobi also the solvers option 'MIP Calculate Basis and Sensitivities' has to be set to 'Yes' but that is already the default setting.

Best regards,

Marcel Hunting

AIMMS Software Developer

[José Magalhaes Jr.]

Hi Marcel !

Thanks for your help.

I did what you suggested, it doesn´t work (see file attached).

I have 03 variables in Objective Function, AIMMS shows "ZERO" for reduced costs for all variables.

 

Please, See the attached file.

In the file, I tried to show what I did and the results that AIMMS shows.

I set my binary/integer variables to continuos.

This way, my problem becomes LP, instead of MIP.

When the problem becomes LP, AIMMS shows the right reduced cost for all variables in Objective Function.

It seems thai I have to do as the AIMMS Documentatios says:

"..fix all integer variables to their final solution (using the .NonVar sufix) and re-solve the resulting mathematical program as a linear.."

 

How to implement this solution using the property " NonVar" sufix? 

Thank you very much for all help.

José

Em Domingo, 2 de Fevereiro de 2014 15:47, José Magalhaes Jr. <maga...@yahoo.com.br> escreveu:

Hi Marcel !

Thanks for your help.

I did what you suggested.

I have 03 variables in Objective Function, AIMMS shows "ZERO" for reduced costs/coefficientRange for all variables.

It seems this procedure doesn´t work to get the reduced cost in MIP problem.

Please, See the attached file.

In the file, I tried to show what I did and the results that AIMMS shows.

to try to understand the problem in AIMMS environment ,

I set my ALL "binary/integer" variables to continuos.

This way, my problem becomes LP instead of MIP.

When the problem becomes LP, AIMMS shows the right reduced cost for all variables in Objective Function.

But My problem is MIP,  I do need binary variables.

It seems that I have to implement the solution as the AIMMS Documentatios says:

"..fix all integer variables to their final solution (using the .NonVar sufix) and re-solve the resulting mathematical program as a linear.."

Please Guys,

How to implement this solution using the property " NonVar" sufix? 

Is there another way to get the reduced costs in MIP problem?

Thank you very much for all help.

Regards,

       José

Em Domingo, 2 de Fevereiro de 2014 15:04, José Magalhaes Jr. <maga...@yahoo.com.br> escreveu:

Hi Thiruselvan,

Regarding the computational complexity of the MIP problem, in general MIP problems are NP hard (see also the excellent post by Jean Francois Puget about this: https://www.ibm.com/ developerworks/community/ blogs/jfp/entry/np_or_not_np_ that_is_the_question49?lang=en ). If your MIP model has some very specific properties, it might be possible that the solution to the LP relaxation of your MIP is actually an integer solution. In this case, it means you can actually solve your problem in polynomial time.

Guido Diepen

On Sunday, February 2, 2014 12:49:16 PM UTC+1, Thiruselvan S wrote:

Hi all,

I have solved a mixed integer program for my class assignment in AIMMS. Please help me in how to do sensitivity analysis and derive the computational complexity of the MIP problem. I have gone through AIMMS Modeling Guide - Sensitivity Analysis (Chapter 4). In that they mentioned only for linear programming and said there are limitations for integer programming. 

-- 

Thanks & Regards,

Thiruselvan S

--
You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling System" group.
To unsubscribe from this group and stop receiving emails from it, send an email to aimms+un...@ googlegroups.com.
For more options, visit https://groups.google.com/ groups/opt_out.