Hello,

I recently tried employing lagrangean decomposition (LD) with the intention to use the solution as a warm-start to solve a MIP. What baffled me was that though the LB (i.e., the soln from LD) was much stronger than the LP-relaxation, I stumbled upon a
non-trivial solution (i.e., all variables are 0). This somehow seems obvious from the structure of the sub-problems. I was just wondering if there could be fixes of any sort to atleast get a trivial solution.

I'll briefly sketch the decomposition here. Please note that I've put up a minimal version of the problem (i.e., I've omitted the indices and summations here that may make the problem look more tedious).

Original problem

min x + y
x=1
Ax<= b
Cy<=d
x = f
x\in{0,1}
y\in{0,1}

So, my subproblems take the form:
SP1:
min x + \lambda * (x-1) - \pi * x
Ax<= b
x\in{0,1}

SP2:
min y + \pi * y
Cy<=d
y\in{0,1}

Lagrangean Dual:
max z
z <= (x-1) * \lambda + (y - x) * \pi
z, \lambda, \pi \in \mathbb{R}

\lambda, \pi are my (free) dual variables as the dualised constraints were equalities.

So, the solution methodology that I adopted was the cutting plane method. At each iteration, I add inequalities z <= (x-1) * \lambda + (y - x) * \pi to the Lagrangean Dual after solving the subproblems.

From the looks of it, there is no constraint in any of the subproblems to enforce x -> 1 or f -> 1. So, despite getting an optimal solution to the lagrangean dual, these variables were set to 0 (and it was the multipliers \lambda, \pi that contributed to
the optimal value of the dual).

Is there a possibility to fix the decomposition methodology that I've adopted here?

TIA

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

I think you may have reversed "trivial" and "nontrivial". In any case, it is normal for LD solutions to violate some of the relaxed constraints for some values of the multipliers. You are not required to relax all constraints, though, so perhaps you
could leave the violated constraints as constraints without making the subproblems too difficult to solve?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

The constraints to be dualised were chosen such that the problem decomposes into 'x' and 'y' subproblems. The very first constraint looked like (\sum{i\in I}x^{t}_{i} = 1 \forall t\in T). So, by choosing to decompose this as well, I have an x sub problem
for every i\in I. This is the constraint that forces an item to be packed in exactly one knapsack (i). Without this, the variables in the x-subproblem always take zero.

Maybe I must try a different choice of constraints in this case but then again, if I were to dualise Ax<= b and Cy<=d instead, the lagrangean solution will only be as good as the LP relaxation.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

I don't have a lot of experience using LD, but I believe that in the majority of my attempts the best solution to the LD problem was not a feasible solution to the original MIP. One possibility that comes to mind is monitoring the solutions to the inner (
relaxed primal) problem and keeping track of the best feasible solution (if any) encountered. It won't necessarily correspond to the best dual (multiplier) solution, but maybe it will make a decent starting solution for the MIP. Another possibility would
be to take the infeasible primal solution corresponding to the best dual solution and trying to get a decent feasible solution from it by some sort of local repair heuristic.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Thanks a lot for the suggestions Dr. Rubin. I shall try out the first one. I was indeed trying to do this "take the infeasible primal solution corresponding to the best dual solution and trying to get a decent feasible solution from it by some sort of
local repair heuristic". Sadly, the infeasible primal solution is just 0s. Not a single binary variable takes a 1 in my case. So, this certainly doesn't seem like a good starting point for a local repair heuristic.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)