Can a set of DWB cuts that recover z_D also handily derive an optimal dual solution?

[WalterMadelim]

Hi, @rchen234 . Nice to see you again. I've read your work "recovering DW bounds by DWB cuts" on operations research, which is a fantastically well-written paper from my point of view.

First, I have some dubiety while reading your E-companion, which was downloaded from INFORMS:

• In Algorithm 1, I think the block consisting of line 17 - 21 should be shifted down by one line. (am I right ?)
• In Example 2, I think that the RHS of the second ≥ constraint should be 12, not negative.

And more importantly, I have 1 conjecture inside the scope of this paper.

• The main idea of the paper, to put it in a nutshell, as far as I'm concerned, is to use a set of DWB cuts to replace the implicit linear constraints indicated by $x_{I(j)} \in conv(Q^j), j \in J$, in eq(2), such that the resulting explicit LP has an optimal value equal to $z_D$.
• From the dual side, $z_D$ can also be derived by specifying some (suppose we can specify the optimal) dual variables in the upper level, then after solving the lower level MIP's, we can also derive $z_D$.
• Suppose now we already have a set of DWB cuts that already recovers $z_D$ in the primal side, then the primal side is an explicit LP, thus we can handily get the dual vector $\hat \beta$ from, e.g., Gurobi.
• The conclusion is that, $\hat \beta$ is one of the optimal dual solutions. (See the picture below for concreteness)
• At least, this conjecture holds for Example 2. See the picture below.
• But I can't prove this. Might you?

Finally, I have a comment on the EC.2 part in the E-companion (or, say, sharing an experience). I think other than $||\cdot||_2$, $||\cdot||_1$ is another (sometimes better) choice. What's your opinion? Do you have some reasons for prefering the QP regularization formulation (EC.4)? Take an example, I adopted algorithm 2 to solve a dual problem of a multistage MSLot problem, where we have 10000 blocks.

When $||\cdot||_1$ is used as objective, the gap can converge (≤ 0.01%):

┌ Info: ▶ level_ite = 2
│   ObjBound = 1.0975483801195571
│   ObjValue = 0.9045941936731429
└   rel_gap = 0.21330469264114515
┌ Info: ▶ level_ite = 3
│   ObjBound = 1.0975483801195571
│   ObjValue = 0.9045941936731429
└   rel_gap = 0.21330469264114515
.
┌ Info: ▶ level_ite = 11
│   ObjBound = 0.9687856207961784
│   ObjValue = 0.9687420902832842
└   rel_gap = 4.493508987666265e-5
[ Info: 😊 dual problem convergent

While keeping all other settings the same, just change to $||\cdot||_2$, the numerical issue occurs:

┌ Info: ▶ level_ite = 2
│   ObjBound = 1.0975483801195571
│   ObjValue = 0.9045941936731429
└   rel_gap = 0.21330469264114515
┌ Info: ▶ level_ite = 3
│   ObjBound = 1.0975483801195571
│   ObjValue = 0.9045941936731429
└   rel_gap = 0.21330469264114515
┌ Info: ▶ level_ite = 4
│   ObjBound = 1.0975483801195571
│   ObjValue = 0.9045941936731429
└   rel_gap = 0.21330469264114515
┌ Info: ▶ level_ite = 5
│   ObjBound = 0.9898702204571557
│   ObjValue = 0.9045941936731429
└   rel_gap = 0.09426992499006201
ERROR: LoadError: in regularization problem, terminating with NUMERICAL_ERROR. # ❌
Stacktrace:
 [1] error(s::String)
   @ Base .\error.jl:35
 [2] top-level scope
   @ K:\order1\src\a.jl:260
 [3] include(fname::String)
   @ Base.MainInclude .\client.jl:478
 [4] top-level scope
   @ REPL[1]:1

The solver is Gurobi 10.0.2. It seems that the QP algorithm is less stable, and sometimes only asserts "Locally Solved". code and details here

PS Was James Luedtke your mentor? The MSLot problem comes from one of his work also published in Operatioins Research, 2022.

[rchen234]

Hi @WalterMadelim , good to see you! Thank you again for your interest in our paper! You are right about the two typos in the e-companion. Regarding your conjecture (the first one), I think it is true if we have exactly one cut per block (see below). I think it should be true if you have multiple cuts per block as well. Ted Ralphs also asked me the reverse question: if we solve the Lagrangian dual problem to optimality, can we recover an optimal (fractional) solution for the primal formulation of the $z_D$ problem (the one defined by convex hulls)? This is also true assuming that we have all the dual solutions that can verify the optimality of an optimal dual solution (having UB=LB in Algorithm 2 for example). The reason why we use 2-norm is because 2-norm is used in the orginal paper of the level method https://link.springer.com/article/10.1007/BF01585555 (although we are using a multi-cut variant). They show strong bounds when the convex optimization problem is bounded. I think 1-norm can also converge while you may not have similar theoretical guarantees. But everything might work in practice! So you can probably use whatever Lagrangian dual method that works the best for your application. And it is definitely true that QPs are not as stable as LPs. I also observed similar issues when optimizing 2-norms. Yes, Jim was my advisor for my PhD. Happy to see how my current work can be related to his work :)

[WalterMadelim]

Thanks for your answers. I insist that you are an expert in the field of MIP. I was just a bit confused before reading your DWB paper, whenever I encountered circumstances in which fellow researchers refers to very old papers when they need a regularized method to solve a convex dual program. For example, in the paper I mentioned at the end of my last comment, abbreviated as LDDR MSMIP, the author mentioned Ruszczyński A (1986), Kiwiel KC (1995). And the regularized method you mentioned in your DWB paper and SIP-LAG paper (which you gives the hyperlink) is also published in 1995, nearly 3 decades ago. It seems as if there were no more new developments in this field since then. But since the algorithm 2 works in practice, I'm content currently. 👍

[rchen234]

If no other structures are known, I believe these methods (like the level method) are the best you can do in theory for worst case analysis. That's I think why there were no more new developments since then.

[WalterMadelim]

Yes, I think that the level method that you recommended is applicable. By the way, I've just finished the experiment (the MSLot) that I mentioned in the previous comment. It's another line of research in the field of MSMIP, compared to the scenario tree approach represented by SDDP. It is policie-based which sounds more practical: in practice: we may encounter circumstances that the realized uncertainty is not representable by discrete scenario trees.

In the paper LDDR, we firstly solve a dual program, where the level method could be adopted. Then we need to solve 2-stage SIP's, where your SIP-LAG paper consists in. These two parts are both SAA problems. (I remember that you also have a paper on the SAA problem, to name one) (code)

If you have further ideas in this field, just let me know. (But I think that there is already many, ;-)) Of course I'm looking forward to see more outcomes from yours in the future.