this is easy, just look at your traditional formulation

max cx

st Ax = c

Temitayo Bankole I am afraid that this procedure only works for LP problems, while I am dealing with the MILP problem, job-shop scheduling.

oh sure , the duality only exists for LPs, you have to change your problem to an LP to get the dual

Dorsa Abdolhamidi

Temitayo Bankole

I appreciate your time and answers. Is there any way to convert MILP to LP by adding some constraints? I mean, I do not want the problem's relaxation. I do need my integer variables to be an integer in the solution.

Dorsa Abdolhamidi , some LP problems have "guaranteed" integer solutions since all the vertices of their feasible sets have integer coordinates. But it cannot be done in general case. If you mean adding some linear constraints to provide integer solution, it will not work.

In fact you can add constraints providing integer values to each variable x_i. But they are of the form sin(pi*x_i)=0. Not linear of course...

Dear Dorsa Abdolhamidi, although I deviate a bit from your specific question, I recommend you check the link that I copied at the end. It is the product of a degree work on sequencing. There Daniel Da Corte makes a very good review of the literature on the subject, which can give you ideas to rethink your problem and arrive at a PPL. I have not continued working on the subject, but you can contact Da Corte, who is enrolled in Research Gate. I hope I have provided some help. Successes in your research.

Best regards,

José Hernández.

The link: http://ares.unimet.edu.ve/sistemas/fpis05/Profesor/Secuenciacion/indexEN.html

Przemysław Kowalik

Thanks for your answer. However, as you mentioned, these constraints make the problem non-linear and are not useful in my case.

José Gilberto Hernández Ramírez

I am grateful for the link and will check the information provided there. They are certainly helpful!

In general, it is NP-hard (or worse) to construct a strong dual for a mixed-integer linear program. The only strong duals that I am aware of are based on superadditive functions. See the early work of Gomory, Burdet, Johnson and Jeroslow, or these papers:

L.A. Wolsey, Integer programming duality: Price functions and sensitivity analysis, Math. Prog. 20 (1981), 173–195.

D. Klabjan (2002) A new subadditive approach to integer programming. In International Conference on Integer Programming and Combinatorial Optimization (pp. 384-400). Springer, Berlin, Heidelberg.

Lasserre, J. B. (2005). Integer programming, duality and superadditive functions. Contemporary Mathematics, 374, 139-150.