Originally posted by: CarlosSuazoM.

Guys,

I am solving repeatedly several versions of a same problem using different input data.

In average, CPLEX takes 1 minute to solve it to MIP Gap = 1%. For some reason, the attached LP file takes more than 48 hrs to reach same gap.

Any recommendation to tackle this issue??

Many thanks in advance,

Carlos

I looked at the file and nothing is obviously goofy about it. (BTW, for future reference, it's better to post a SAV file than an LP file.) The constraint coefficients look okay, and kappa statistics show 100% stable bases (can't beat that). The objective coefficients might be a wee bit concerning -- you have a 13 order of magnitude spread (from 1e-09 to 1e+04). The relatively teeny "epsilon" coefficients might invite some rounding error issues. I tried changing them to 1e-07, though, and it didn't seem to speed up solution all that much.

The solver log (using defaults) suggests that CPLEX gets okay solutions reasonably quickly, something that might be approaching optimal in "reasonable" time (not one minute, though), and then suffers from slow progress in the lower bound. As an ad hoc approach, you might try the following:

1. Set the MIP emphasis to 4 (find hidden feasible solutions) and run for a few minutes (ideally long enough to get an incumbent below 0.049). If you're solving this in the interactive solver, you can just watch the log. Otherwise, you can set either a time limit or a MIP gap (in which case you'll need to remember to revert whatever limit you used).
2. Now set the MIP emphasis to 3 (push the best bound) or maybe 2 (optimality) and solve again. CPLEX will resume with the node tree it had when the first run terminated.

You might also run the tuning tool and see if it suggests any nondefault parameter settings.

Setting the branch direction to "down" might help a little. (I'm not sure about that.)

One last possibility (the least satisfying, in my opinion) is to change the random seed CPLEX is using. You never know ...

None of this explains why your luck ran out on this particular instance.

Originally posted by: CarlosSuazoM.

Thanks Paul for your insights.

I didn't realize we had a 13 order of magnitude spread in the objective coefficients. In order to 'force' convergence of some variables to their lower bound when a degenerated is formulated, we introduce a small coefficient 1e-9 in the objective function for these variables (minimization problem): I'm wondering if there is a better way to tell the solver that we prefer solutions closer to their lower bound. Do you have any suggestions??

Anyways, we followed your recommendation to set the MIP emphasis to 4, and we fixed some numerical issues during the formulation, and time was dramatically reduced!!

The approach you're taking to put downward pressure on variables is the first approach I would try. I assume from your choice of 1e-9 that you are not willing to trade any measurable degradation of the objective value to get smaller variable values.

You might want to test a revised model with zeros for those coefficients. If solution time is similar, then those coefficients aren't the culprits, so you can leave them alone (but perhaps make them a bit larger -- 10^-9 is smaller than the default tolerance settings for rounding errors). If solution time with zeros is much faster, then you might try solving the revised model to optimality. Call the objective function z and its optimal value z*. Now add the constraint z <= z* + epsilon, change the objective function to minimize the sum of all the variables (or all the variables on which you would like to put downward pressure) and see if the second model solves quickly enough.

Originally posted by: PingLiu

Dear Paul,

That is a very good suggestion. I have a same issue with penalty variables. in contrast, we put a big penalty on the variables (continuous) on which I would like to put downward pressure. I think this would cause numerical issues when combining multiple objectives into a single objective.

https://www.slideshare.net/IBMOptimization/2013-11-informsminingthenodelog

Do you think random seed would help with such issue related to penalty variables?

Thanks,

Ping

The random seed will not help with performance problems in general. On any given problem instance, a different seed might produce faster convergence, but it might equally well produce slower convergence (or have no effect).

Putting a very large penalty on variables is dangerous. Yes, it will put downward pressure on them, but quite possibly to the point of producing a wrong answer. Consider, for example, a simple production scheduling problem (where your decisions are what to make in each period and how much to ship). If you decide that you want downward pressure on inventory levels and heavily penalize the inventory variables, your solution is liable to be make nothing, ship nothing (and thereby store nothing).

Finding penalty coefficients large enough to apply "appropriate" downward pressure but small enough not to produce suboptimal solutions can be very tricky. The original question related to getting rid of small positive values (above lower bound) on variables in a degenerate solution. Is that what you are trying to accomplish?

Originally posted by: PingLiu

I tried your suggestion 1) solving the revised model to optimality. Call the objective function z and its optimal value z*.

2) Now add the constraint z <= z* + epsilon, change the objective function to minimize the sum of all the variables (or all the variables on which you would like to put downward pressure) .

when combining penalty variables with other cost function into a single objective, it can solver much faster than what you suggested above.

the single problem took several minutes to solve (due to the large coefficient of penalty variables, not sure whether the solution is optimal or not). the first step of your suggestion was fast, but the second step took 8 hours to finish.

I also notice that z* is lower than what we got from the single problem.

Do you think benders decomposition would be an option by separating penalty variables into the first stage while keeping all the remaining cost function in the second stage problem?

If the purpose of the penalties is to force variables that would be close to zero without the penalties to be zero, then I don't see how Benders would help.

Originally posted by: PingLiu

I have a 20-year transportation planning problem. each year t each path i has a binary variable x_(i,t) indicating whether to build the path or not.

During the 20-year period, each path can only be built once.

sum(x_(i,tm))<=1, 1<=tm<=20.

I also have another binary variable y_(i,t) which indicates so far whether the path i at year t has been built or not.

y_(i,t) = sum(x_(i,tm)), tm<=t.

that means for each path there will be two binaries variables. but y_(i,t) is depending on x_(i,t).

DO you think this method will increase the computational time or not? Is there any way to reduce the binary variable y_(i,t) while only keeping x_(i,t)?

Thanks,

Ping

There is no need to declare the y variables binary, since they are sums of binary variables. You can make y continuous. (Continuous variables are "cheap" in computational terms.) It's also possible that the presolver will eliminate the y variables and substitute sums of x variables ... but it also might not, since doing so makes the constraint matrix denser. I suggest making y continuous and then not worrying about it.

Originally posted by: EdKlotz

Here are a few general recommendations, followed by some more specific ones:

• If you are solving the same model with different data instances and one instance is much harder than all the others, compare the hard one with the easy one, looking for differences.    For example, in this case, is the range of objective coefficients larger for the hard model than all the easier ones?   Likewise, if you decide to post the hard model to the forum like you did, also post one of the easier ones so anyone who tries to answer your question can do similar comparison.
• Look at the node log to determine where the lack of progress comes from. That can guide you to settings that can improve performance.   
• Based on your model description, your model has time periods, and it also has variables y that depend on variables x.   Both of these suggest that branching priorities might help performance.   Give higher priority to the earlier time periods, and within a given time period, give high priority to the independent variables x (assuming you decide to leave the y variables as binary rather than declare them as continuous, as Paul suggested).
• Based on examining the node log, slow progress in the best node value appeared to be the primary performance challenge here.    Based on your description, your model sounds highly symmetric, and the constraints involving sums of binaries being <= 1 suggested aggressive probing might help.    With that in mind, I set probing to 3 and symmetry to 5, the most aggressive settings for those parameters.   Based on the lack of progress in the best node, I also set the mip emphasis parameter to 3, and to compensate for potential declines in feasible solutions with that setting, I set the RINS heuristic frequency to 100 nodes.   Here are the results using CPLEX 12.7.1, 8 threads, running 5 different random seeds to make sure that the results were consistent:

====== runseeds statistics of 5 runs

    exit  sol    objective     gap  iteration      node   runtime   dettime
run code stat        value     (%)      count     count   seconds     ticks
  1    0  102    0.0482927    0.01    1107253      8846     84.97  40591.18
  2    0  102    0.0482928    0.01     665403      8000     72.75  33966.95
  3    0  102    0.0482928    0.01     822924      3538     50.60  27671.60
  4    0  102    0.0482927    0.01     938859      5805     73.15  35640.42
  5    0  102    0.0482928    0.01     774696      3716     54.11  28378.32

Optimization status codes:
                 objective     gap  iteration      node   runtime   dettime
                     value     (%)      count     count   seconds     ticks
    102 : integer optimal, tolerance (5 times)
     average:    0.0482928    0.01     861827      5981     67.12  33249.69
     minimum:    0.0482927    0.01     665403      3538     50.60  27671.60
     maximum:    0.0482928    0.01    1107253      8846     84.97  40591.18
     std dev:   3.2806e-08    0.00     168712      2419     14.40   5361.27

So this looks like it takes care of the performance problem.

Finally, here's a technote that is a good starting point beyond the CPLEX user guide for troubleshooting MIP performance problems:

http://www-01.ibm.com/support/docview.wss?uid=swg21400023

Originally posted by: yanzhiping

Thanks @EdKlotz 76679752-a695-4301-a8a6-a46603aab7bb for the detailed information.

I am impressed with the good performance you achieved with the suggested strategies in parameter setting.

but I still have some questions as below.

what is the appropriate number of threads for a MIP job? is it the more the better?

How do you find the model sounds highly symmetric?

why do we need to Give higher priority to the earlier time periods?

could you help me answer them?

Best,

Originally posted by: EdKlotz

> what is the appropriate number of threads for a MIP job? is it the more the better?

For most MIPs, you will get the best results with 8-16 threads.   The MIP algorithm is more complex than a simple task like searching a huge amount of data of occurrences of a particular word.    The latter task can be divided into subtasks whose run time is similar.   So you have balanced loads among a large number of threads, and typically more threads will work better.    With the branch and bound algorithm, different threads receive different subtrees, and the run time can vary.   This can cause unbalanced loads that increase the wait time when you want to synchronize the threads.   So for most problems, the gain from processing more nodes exceeds the cost of unbalanced loads for somewhere between 8 and 16 threads, then the tradeoff becomes unfavorable as the thread count increases beyond that.    Plus, more threads require more memory, and if you may incur some runtime costs there as well.

> How do you find the model sounds highly symmetric?   

Primarily based on your model description posted here.  If a model has alternate solutions with the same objective values, the model is symmetric.  Here's a starting point for recognizing symmetry:

https://www-304.ibm.com/support/docview.wss?uid=swg21400016

If you want more info, Google the work of Jim Ostrowski on Symmetry in MIP.

> why do we need to Give higher priority to the earlier time periods?

The variables associated with earlier time periods are more independent.   The later time periods depend on decisions made in the earlier ones.   You don't want CPLEX to spend a lot of time branching on later time periods for decisions in the earlier time period that ultimately won't be selected.   I don't know the details of your model, but you mention building paths over time.    So if you are building from east to west, it doesn't make sense to build a path from Las Vegas to Los Angeles until you determine that you want to build a path to Las Vegas in the first place.

Originally posted by: yanzhiping

Thanks for the answers.

I am trying to test the cplex distributed MIP too.

How many nodes do you think would perform the best? Is it problem dependent?

Is there a good number too,so  beyond that the performance for distributed MIP will go down?

Originally posted by: EdKlotz

Given that during this thread some parameter settings emerged that consistently solved this particular model in 2 minutes, I don't think you need to look at distributed MIP for this particular model.   Distributed MIP is more likely to be useful on models that generate a huge number of nodes fairly quickly, or models which exhibit high performance variability, so running on multiple workers with different random seeds can be useful because the run will stop as soon as one of the workers solves the model.    So far, neither of those characteristics appear to fit your model (at least with the parameter settings previously mentioned).    So I will try to answer your question from a more general perspective.

>  How many nodes do you think would perform the best? Is it problem dependent?

Yes, it depends on the problem, and also what you want to accomplish with distributed MIP.   If the problem takes a long time because it generates a huge number of nodes that solve fairly quickly (e.g. many of the yellow MIPLIB problems that can eventually be solved to optimality but no commercial solver has finished them off within an hour), then you probably want to use a lot of workers.    On the other hand, if you want to run different MIP strategies concurrently to try to get better results (e.g. a couple of runs that focus only on improving the best integer, and a couple others that only focus on the best node), then as few as two workers might suffice.  

>  Is there a good number too,so  beyond that the performance for distributed MIP will go down?

I think the same load balancing issues that can potentially hinder performance for CPLEX's parallel MIP on a single machine apply for distributed MIP as well.

Originally posted by: yanzhiping

Regarding the branching priorities, I have another modeling question.

in the planning problem, we also consider EV charging facility investment, like each year how many MW capacity should be invested in order to meet the charging load from electric vehicles.  so the investment capacity is a continuous variable. besides, each year, the invested capacity should meet the hourly EV charging and discharging load also. so the model becomes

P_inv(yr)< Pmax;

P_inv(yr)>=P_charge(yr,hour) +P_discharge(yr,hour) >=Pload(yr,hour) ;

since at each hour, the charging and discharging cannot happen at the same time, so we introduce the binary variables

X_charge(yr,hour) +X_discharge(yr,hour) <=1

at this point, the MIP may branch on both X_charge and X_discharge no matter whether the EV is invested or not.

Do you think we should introduce another binary variable to indicate whether the EV is invested or not each year, so the investment constraint becomes

P_inv(yr)< X_inv(yr)*Pmax;

In this way, we can consider the branching  priority strategy on X_inv(yr).

Do you think it is a good way to improve the performance of the MIP problem?

Thanks,

Ping

Originally posted by: yanzhiping

Thanks PaulRubin  for the simple but effective solution to fix this issue.