Originally posted by: Phoebe_Qi

Dear all, 

Hi. 

I am using C++ CPLEX to solve a resource allocation problem in wireless networks, and one of the parameters is number of time slots available in the network. 

Since the problem is MILP and the problem size is large, solving each network instance to its optimality takes a long time. 

If I only want to test how many time slots is feasible to the problem, is there a way to test the feasibility of the problem without actually solving it ?

Thanks. 

Phoebe

Hi,

if you only need to test feasibility why do not you remove the objective part ?

And then your model is not any more a max/minimization problem

regards

From a theoretical point of view, feasibility in MILP is as hard as optimality (both are NP).

If you are concerned only about feasibility then the following things come to mind:

1. Like Alex suggested, clear the objective. This may allow presolve to do more reductions and you may get a proof of (in)feasibility faster.
2. Use the feasopt feature of CPLEX. In phase I of feasopt, as soon as the dual bound is larger than 0, you know that your problem is infeasible.
3. Check your model for constraints that do not affect feasibility and remove those. This may (or may not) speed up the proof of (in)feasibility.
4. Not sure if this is useful in your case but you could also change the objective to "minimize the number of time slots". This way you will know the smallest number of time slots for which the model is still feasible.