How to implement an LP Relaxation with Gurobi
AnsweredHello everybody,
I am trying to implement a LPRelaxed Program. In my real program the variables are binaries and all is fine ex: GRBVar var = model.addVar(0.0, 1.0, 0.0, GRB.BINARY, "x"+job.getJobNumber()+","+jobsOnMachine);.
Now I want to implement a LPRelaxation where the variables can be between 0 and 1. I tried this formulation : GRBVar var = model.addVar(0, 1.0, 0, GRB.CONTINUOUS, "x"+job.getJobNumber()+","+jobsOnMachine). But still the values are either 0 or 1 and there is no brocken variable.
So the question is how to do that?.

Hi Musa,
It may very well be that the solution to your problem does not contain any fractional values  LP solutions are extreme in nature. Maybe the constraint matrix is a totally unimodular matrix and so the LP solution for every possible objective is integral.
You should try writing out the LP file to inspect the formulation for possible issues and whether it corresponds to your mathematical model.
Cheers,
Matthias0 
Thank u Matthias,
the Matrix is in fact totally unimodular and the is always a opt solution. That is not the point, I am implementing an algorithm for an OperationalIntervalSchedulingProblem which is done. But I also want to implement and heuristic for very large instances. Since a problem consist of jobs and machines and an interval with jobweight I intend to have an LPBased heuristic. I have implemented two greedy heuristics but I also want a LPBased one. Usually if we neglect the binary variables and let them have a value 0<=x<=1, the LP should also assign part of a jobs to a machine though the job needs to be fully assigned. So even when I do not declare all the variables as binary, or that a job should fully or not be assigned to a machines, I am not getting any brocken jobs, which I should.
cheers and Grüße,
Musa
0 
Hey Musa,
Maybe I don't fully understand the issue here. You should feel lucky to be working with a totallyunimodular matrix so every possible LP solution is integral. This is the "holy grail" of (mixed) integer programming problems and does not require any heuristics  you really just solve an LP and are done.
Also, please consider that LP solutions (at least those coming from the simplex) are extreme solutions in nature so it is not too surprising that there are no fractional solution values  every variable is pushed to either of its bounds.
Cheers,
Matthias0 
Hello Matthias,
I have found the problem, tho the matrix is uni modular but actually there is always a way to implement an lpheuristic. But the problem here are the constraints that as u said push the values to be 0 or 1 and the constraint can not be changed else there will be a wrong solution.
Thanks for your feedback.
Cheers,
Musa
0
Please sign in to leave a comment.
Comments
4 comments