I have tried to implement a toy problem (MIP) from the literature using Lagrangian Relaxation with the subgradient method, I implemented it correctly and I got the upper bound which is updated at each iteration, however, for the lower bound (original problem), I optimized it to using a solver inside the algorithm, but in the literature, it has been mentioned that we can make use of relaxed problem solution to find a lower bound (maximization problem), most of them they refer to a heuristic to find such lower bound because in most cases the solution of relaxed problem will be infeasible to the original one, but I did not figure it out, do I have to optimize the lower bound using the solution from LR and solver or just plug the solution of the relaxed problem into the original problem ( in this case it will not work, as I have tried it before).
4
-
1$\begingroup$ Related question: or.stackexchange.com/questions/5426/… $\endgroup$– fontanfCommented Aug 14, 2023 at 16:19
-
$\begingroup$ @fontanf Thank you for redirecting me to that link, it was useful but most of the literature takes the LR algorithm as a lower and upper bound as one algorithm, although without finding the upper bound we will not know how far are we from the optimal solution. $\endgroup$– ABDECommented Aug 15, 2023 at 11:34
-
$\begingroup$ Sorry, I don't understand your comment. For a maximization problem, LR directly provides an upper bound. The solution of the LR is in general infeasible. To get a feasible solution (lower bound), another algorithm is needed, such as branch-and-bound $\endgroup$– fontanfCommented Aug 16, 2023 at 7:24
-
$\begingroup$ Sorry, I was talking in general which is typically for minimization problems, my comment should be "finding a lower bound ( original problem) ..." which is related to my question. $\endgroup$– ABDECommented Aug 16, 2023 at 9:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The relaxed constraints will typically be violated, but the rest of the constraints will be satisfied. To get a feasible solution to the original problem, you need to modify the relaxed solution somehow to satisfy all the constraints. Such a "repair" heuristic is usually problem-specific. For example, Section 10.4 of Wolsey's Integer Programming describes a greedy heuristic when the original problem is set covering and all covering constraints are relaxed: ignore the rows that are already covered by the relaxed solution, and greedily change some variables from $0$ to $1$ to cover the rest.
-
$\begingroup$ Thank you for your explanation and the book reference you provided, I think the book highlighted at the end of section 10.4 the confusion that I found in the literature, basically for problem-related to SCND with MILP problems, usually the upper bound is found by using information solution of the relaxed problem, i.e fixing some optimal decision variable and solve the original problem which may provide an upper bound with less CPU time for large scale problem, if the problem is small then solving the original problem directly would not be cumbersome. $\endgroup$– ABDECommented Aug 15, 2023 at 11:30