Originally posted by: algowiz

I'm solving a mixed integer model with lots of binary variables but an objective function that is the sum of continuous (floating point) variables). The latter have values that can differ a great deal in magnitude, some very close to 0, others fairly large. Ideally, the sum should be computed by adding the small values first and then the larger ones. Is there any way to let the optimizer know that the terms of the sum should be sorted by increasing magnitude before the sum is computed? This does not appear to be happening automatically. If I add constraints that either should not affect the solution or should increase its value (this is a minimization problem), the value of the objective sometimes decreases (it should stay the same or increase). Thanks. 

As far as I know, there is no way to force CPLEX to add the small values first. There are a number of other things you can try.

First, when the objective value decreases after adding a constraint, is the solution the same (same values for all variables) or different? If different, are the gaps in both cases below the threshold for declaring optimality? It's possible that the added constraint led CPLEX to a different path through the search tree, culminating in a different solution. Since CPLEX considers any solution meeting certain convergence criteria "optimal", it could legitimately be the case that the first and second solutions both meet the convergence criteria, and it is just happenstance which you get.

Assuming the decrease in the objective value is too large to excuse, you might try turning on the numerical emphasis parameter. This causes CPLEX to be more finicky in general when doing floating point arithmetic. You might also collect kappa statistics and check the number of unstable or suspicious bases to see if the model has general stability issues.

You can also try tightening the various epsilon parameters (EpsInt, EpsRhs) if you think that either the first or second solution is actually not feasible.

Originally posted by: algowiz

Thanks. These suggestions will likely prove useful in the future. The mystery of the decreasing objective has been solved: I inspected some of the situations where this occurred and found that at least one of the two runs aborted due to a time out (using a one hour limit). I appear to be getting a lot of time outs when minimizing the semi-continuous objective s, but when I keep constraints the same and minimize a related integer objective i or I add a constraint on the value of i and minimize s, the solver produces an optimum solution within the time limit (often within seconds). I've tried various suggested strategies - driving toward feasibility, aggressively pursuing cuts, etc. - to no avail. There are much smaller instances where the value of s is very sensitive to the constraint on i and the difference in constrained and unconstrained minima for s is slight. Suggestions would be appreciated. Almost all of my work up to now has involved minimizing sums of binary variables with all variables binary. And time outs have only rarely occurred on problem instances of this size (10K - 40K constraints).

I have observed, on some problem instances in a different domain, that CPLEX can be very sensitive to the order in which variables and constraints appear in the input file with runtimes ranging from less than a second to one-hour time out on the same problem instance with rows or columns permuted. I have yet to try these permutations here.

I don't know how CPLEX deals with semicontinuous variables internally, but it's like the way CPLEX handles indicator constraints, it could be an internal choice between "big M" constraints and branching decisions. If it's using the "big M" approach, tight upper bounds on the semicontinuous variables may help.

There are a number of reasons why the order of rows and columns could make a difference, but one thing to look at is inherent symmetry in the model (which will slow down improvement in the best bound). If your model has significant symmetry, there are several possible remedies. You could perhaps reformulate to get rid of the symmetry. If not, you might be able to add constraints that would eliminate some of the symmetry. (As one simple example, in a bin packing problem with lots of identical bins, you can specify that free space be nonincreasing with respect to the bin indices.) All else failing, there is a parameter that controls how much effort CPLEX spends coping with symmetry. Cranking that up might help.

Originally posted by: algowiz

Great. This is all very helpful. I now have several ideas I can try out.