Undesired binary values & high computational time

[nourelden-gaafar]

I'm using hourly constraints of the form x <= M z (where x is continuous, z is binary, and M is a large constant) to enforce that z=1 when x>0, and z=0 or 1 when x=0. Ideally, z should be 0 when x=0 to reduce costs, but many cases (hours) still have z=1. Is there a way to minimize this effect? (This effect is even more pronounced when CPLEX is used).

Additionally, with constraints like x >= m z (where m is a small positive value, e.g., 0.0001), many x values end up exactly at m, adding noise to the solution. Is there a way to avoid this?

Finally, I’m working with 26,280 binary variables (3 for each of 8,760 hours). Despite optimizing bounds, solving takes up to 3 hours in some cases. Are there CBC options to speed up integer solution times?

[jhmgoossens]

To be honest, this sounds more like an issue with your model formulation than a software issue with CBC. This item might be better of under Discussion than as an Issue.

Your problem is a Minimization (of cost), right?

z should be 0 when x=0 to reduce costs, but many cases (hours) still have z=1. Is there a way to minimize this effect? (This effect is even more pronounced when CPLEX is used).

Maybe do these z variables have zero cost or negative cost in the objective function? As a result, the solver 'believes' there is no cost of setting z=1 and what you observe is the result. Are you sure z has positive cost in the objective?

with constraints like x >= m z (where m is a small positive value, e.g., 0.0001), many x values end up exactly at m

If you don't want such solutions to be 'feasible', then either add constraints that cut off these solutions, or ensure such solutions are very costly in the objective. So, if you DONT want solutions with z=1 and x = 0.0001, then you could increase m (such that x=0 or at least x>=m for a larger m) or increase the cost of z in the objective (such that z=1 is even more costly in your Minimization problem). Are you sure z has positive cost in the objective? (same as first point).

Despite optimizing bounds, solving takes up to 3 hours in some cases.

With "optimizing bounds" do you mean choosing good values for the various M (as small as possible) and m (as large as possible)? There are plenty of web sites that discuss the problems with Big-M constraints in mixed-integer programming, notably on the LP relaxations, which directly impact the performance. Have a look there for tips how to reformulate.

Does this help?

[nourelden-gaafar]

Your problem is a Minimization (of cost), right?

Yes, it's.

Maybe do these z variables have zero cost or negative cost in the objective function? As a result, the solver 'believes' there is no cost of setting z=1 and what you observe is the result. Are you sure z has positive cost in the objective?

The z variables indicate whether energy storage is being charged, discharged, or has a positive state of charge. Whenever any z variable equals 1, losses occur (constraints), causing the storage to withdraw more electricity from the grid (constraints), which incurs costs (objective). So yes, z indirectly contributes to positive costs in the objective.

If you don't want such solutions to be 'feasible', then either add constraints that cut off these solutions, or ensure such solutions are very costly in the objective. So, if you DONT want solutions with z=1 and x = 0.0001, then you could increase m (such that x=0 or at least x>=m for a larger m) or increase the cost of z in the objective (such that z=1 is even more costly in your Minimization problem). Are you sure z has positive cost in the objective? (same as first point).

Is there a way to simply add constraints that cut off these if-based solutions or ensure that they are very costly in the objective? That would be very helpful. I tried to influence the z=1 values by adding additional penalties. However, this also affects hours when z is intentionally set to 1 (for actual charging, discharging, etc.). Accordingly, I added marginal penalties for z=1 but still see instances where z=1 and x=0.0001.

Regarding increasing the value of m (e.g., using m=200 kWh instead of 0.0001 kWh), I also tried that but found similar hours where x=m (in this case, x=200 kWh) in an undesired way. This approach worsens the model since it not only introduces unintended losses when z=1, but also undesirably increases the electricity drawn from the grid to 200 kWh instead of 0.0001 kWh, creating additional unwanted costs.

The attached screenshots from Model Building in Mathematical Programming (Wiley) clarify this issue and recommend using either x >= m z constraints (though m is unnecessarily forced in both CBC and CPLEX) or only using x <= M z constraints, arguing that the undesired solution (z=1, x=0)—which happens less frequently in CBC than in CPLEX—will still yield lower overall costs. However, I am wondering if there is a way to further minimize or eliminate these cases altogether.

With "optimizing bounds" do you mean choosing good values for the various M (as small as possible) and m (as large as possible)? There are plenty of web sites that discuss [the problems with Big-M constraints] in mixed-integer programming, notably on the LP relaxations, which directly impact the performance. Have a look there for tips how to reformulate.

Yes, that's eactIy what I meant! I’ve applied these principles from the mentioned book, which, along with other tweaks, reduced computational time from infinite to a range of minutes or hours. I’m wondering if there are further options or heuristics in CBC that could speed things up.

Many thanks for your help! :)

[nourelden-gaafar]

Hi,
any further clue or help?

[jhmgoossens]

Double-check your model and implementation. Create a small instance of your problem that exhibits this undesired behavior and then check why such a solution is considered optimal while you believe you can easily improve it.

Whenever any z variable equals 1, losses occur (constraints), causing the storage to withdraw more electricity from the grid (constraints), which incurs costs (objective). So yes, z indirectly contributes to positive costs in the objective.
the undesired solution (z=1, x=0) [..] will still yield lower overall costs

Do I understand correctly that according to you a solution like "z=1, x=0" cannot be optimal because "z=0, x=0" has a lower objective function value? If that is a correct understanding, then your model run cannot (should not) return such a solution with "z=1, x=0" as Optimal. So, if your model run does return such a "z=1, x=0" solution as Optimal, then there is something wrong in your model and/or your implementation--or there is a bug in the solver. Does that make sense?
But since you're getting similar results with different solvers, I put my money on a problem with your model or implementation.

You can debug your model / implementation in many ways, but one way is to take the "z=1, x=0" solution and take the objective function value. Now fix the values to be "z=0, x=0", now is that a feasible solution? And what is the objective function value of that solution? Is it indeed lower?

still see instances where z=1 and x=0.0001

Maybe you have constraints that unintentionally force x to be > 0? Are these constraints intentional? If you force these particular x=0, then is that model solution still feasible? If it is not feasible in the model, then look for the constraint that forces this. If the solution with x=0 is feasible, then check why "z=1, x=0.0001" apparently has a better (lower) objective function value than "z=1, x=0".

Regarding increasing the value of m (e.g., using m=200 kWh instead of 0.0001 kWh), I also tried that but found similar hours where x=m (in this case, x=200 kWh) in an undesired way.

Undesired way, what does that mean? These are constraint like 'x >= m z'. The value of m in such a constraint typically has a real-world meaning--not something you play with to see what works. Why do you need these constraints, unless you're trying to impose some (high) lower bound m <= x if x > 0? If your lower bound (m) is near zero, then why add these constraints if anyway 'x >=0'? These constraints are necessary only if you're trying to enforce "either x=0 or m <= x" (x is zero or at least m) for some m >> 0. If you use m at 0.0001 then you only add a lot of unnecessary constraints that slow down the solving and might cause precision issues.

Good luck.