Greetings everyone. This is my first time posting a question so if it is not clear please let me know so I can learn and make improvements.
I am working on a variant of deterministic multi-stage no-wait hybrid flow shop scheduling problem. I am considering using the primal-dual method to derive an approximation algorithm for the problem. Following the principle of the primal-dual method, I formulate the problem as a linear program. The formulated primal has about 10 constraint sets. Now I want to derive the dual of the LP relaxation, which I can theoretically do but I'm not sure anymore if this is the right way, because I would obtain 10 types of dual variables. In all the papers I have seen so far in the literature, which use the primal-dual method for approximation, there are only one or two types of dual variables, so 10 seems too much.
Option 1: I have seen in the works in the links below that we can use Lagrangian Relaxation to kind of "transfer" a primal complicating constraint to the objective function and thus reduce the number of dual variable types. In that case, how to determine the complicating constraints and their number. Theoretically, I can choose as many as I want but evaluating all options would be tedious. Are there any practical suggestions from your experience?
Option 2: Or maybe I should find a more compact formulation (for the primal) altogether.
I hope my description is clear. Any thoughts or advice on how I can proceed from here and on how to effectively use the primal-dual method for approximation algorithms, in general, would be much appreciated.
https://drum.lib.umd.edu/bitstream/handle/1903/7387/umi-umd-4803.pdf?sequence=1&isAllowed=y
https://idp.springer.com/authorize/casa?redirect_uri=https://link.springer.com/content/pdf/10.1007/s101070100262.pdf&casa_token=d0XPIbjxJ4IAAAAA:fQ99Ilmr2zvGOMHXPfU5ObRLpAHKG8Iaw3r8Gd5bQ_0CIZEg8m-Ec-nrK7BUEjS_V4eeyZaZq3OVLjd7fw
- Badges
- Science topic
- Similar topics
- Computer Science
- Computer Communications (Networks)
- Internet