Possible problems with MIP-CPLEX

Problems with modeling
Post Reply
ferrib
User
User
Posts: 14
Joined: 5 years ago

Possible problems with MIP-CPLEX

Post by ferrib »

Hi,

I am coding a Mixed Integer Programming, to be solved with CPLEX. This is a market clearing problem, and objective function is to minimize costs. Apologize me, i cannot post the code, but hopefully with some hints, based on your experience, you might be able to form an opinion and help me.

1 - If i simplify the problem using few demand and offers in the market, the program finds a solution. The solution makes sense, so i guess the code is correct.

2 - If i use real market data with, say, 50 times more players from both demand and offers side (hence increasing the solution space) the program doesn't solve. In fact it doesn't even run properly: increasing "reslim" doesn't solve this, because the problem returns an error in one equation infeasible, all entries at implied bounds after running for around 15 seconds, which means it doesn't go past the presolve. But looking at my data, I am sure there is a solution, and also concretely for that equation that is being flagged as the problem. I tried several relaxations for that equation, for example using =g= instead of =e= and lowering its values, but program will only run if i leave it =e= 0; using it =g= 0.001 will throw me to the infeasible, all entries at implied bounds again. I also tried to fix some variables that would solve this equation, and it still doesn't work.

So my question is whether CPLEX should find a solution, because i know there is at least one.

Does anyone have an intuition of what might be the problem? If you think you can help me if i give you more info regarding the problem, i would be grateful.
Fred
Posts: 372
Joined: 7 years ago

Re: Possible problems with MIP-CPLEX

Post by Fred »

Hi,

A good way to go about analyzing infeasibilities is to provide a "feasible" solution to the problem (you claim to have such a feasible point). To do so, you can manually set the variable level values (x.l(i,j) = ...) and then generate the model with a full equation listing (option limrow=1e9;) This will flag the constraints that are infeasible with your "feasible" solution (INFES =...).

You could also ask CPLEX to give you the smallest relaxation of your model to make it feasible ( https://www.gams.com/latest/docs/S_CPLE ... LEXfeasopt) or instruct CPLEX to compute the smallest set of constraints that are infeasible via the iis option (see https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXiis).

Do you have any discrete variables in your model that can potentially be greater than 100? If so, you might also want to look at option intvarup (https://www.gams.com/latest/docs/UG_Gam ... AOintvarup).

I hope this helps!

Fred
ferrib
User
User
Posts: 14
Joined: 5 years ago

Re: Possible problems with MIP-CPLEX

Post by ferrib »

Hi Fred,

Thanks a lot for your input. I will need to take a look at the "feasopt" (i will try to learn from https://www.gams.com/latest/gamslib_ml/ ... sopt1.html) and "iis" as you suggest.
I had stumbled upon the "intvarup" issue before and made sure that is not the problem.

But before, let me step back and ask a more general question: knowing that there exists a possible solution, will CPLEX always find it (at cost of increasing time and iterations), or is there a risk that it doesn't, because there are too many variables and equations?
Fred
Posts: 372
Joined: 7 years ago

Re: Possible problems with MIP-CPLEX

Post by Fred »

Hi Ferrib,

People (including myself) often "know" that there is a feasible solution to their problem and in the end it turns out that there is none because of some model or data mistake... Finding a feasible solution can take forever but at least CPLEX should not classify a feasible model as infeasible. However, some models are on the edge of feasiblity/infeasibility. Often this goes together with poor scaling which gives the solver a hard time and may lead to inaccurate results.

As mentioned before, if you know that there is a feasible solution, a good idea is to use that solution as a starting point and analyze the equation listing.

Best,
Fred
Post Reply