Difficulty with explicit big-M relaxation

[sean]

Hi Johan,

I am coding the logic for a big-M relaxation of the attached problem I wrote. Basically I have switched dynamics of an electric vehicle (EV) traversing a connected graph. The total distance traveled and battery energy remaining are the dynamics. These have time-invariant box constraints. The logic for switching these two are the same. The EV can traverse any edge whose weight is greater than zero ( relaxed to >= 1). A binary selection variable and the edge matrix form the foundation for what edges an EV can take at a given node. The current test objective function is to maximize the distance traveled in the time horizon.

The problem is feasible when the edge selection ("con") is not included. When it is included it becomes infeasible. I have checked the edge selection logic and it seems tight but obviously it is not. The error could also be in one of the other constraints that divides the feasible space in such a way that it only appears when intersected with the "con" hyperplane.

Any recommendations on how to visualize this in a useful way? Plotting with binary variables seems tricky. Using polyhedron and projection seem to have a pretty large computation time in this problem. The current plot of constraints does not have any physical intuition to me.

As always, I appreciate your help!

Sean

[Johan Löfberg]

Way too messy to easily see some bug.

Perhaps you could model the logics using high-level operators (implies) instead and let YALMIP take care of the big-M modelling, to see that your logics actually are correct.

[Johan Löfberg]

and to debug the problematic constraints, add slacks on them, and then minimize the slacks, to see if it is some specific constraint which introduces the problem

Cannot run your code with con added though, as idx is undefined

[sean]

I had shied away from using implies as some of the implications were not obvious to me, but I just got it running with it and was able to identify my bugs.

Thanks Johan!

[Johan Löfberg]

Great to hear!

[sean]

Unfortunately found some weird behavior.

It appears that what I thought was the causal statement on line 94 actually changes the value of one of the variables. Namely .99*eps_var is resulting in the value of eps_var being changed even though it should evolve under the dynamics of lines 93 or 96. Should the implication here be switched?

[Johan Löfberg]

To get any answer there you would have to clean up and simplify the file and remove everything which isn't central to the question and the spotted behavior, and mark very clearly what is considered wrong and how it is seen to be wrong. the code is too complex now

Also, my recommendation when you have models like this is to clearly specify the N disjunctive behavior you have (seem to be three dynamic cases). Introduce 1 binary for every case, and then use implies(case(i), everything that holds in this case) + [sum(cases) == 1], instead of doing things like implies(this and that, this) + implies(these things but not this, these things) + .... It cleans up the code typically, and leads to simpler big-M models