How to implement an LP Relaxation with Gurobi
AnsweredHello everybody,
I am trying to implement a LP-Relaxed 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 LP-Relaxation 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 uni-modular and the is always a opt solution. That is not the point, I am implementing an algorithm for an Operational-Interval-Scheduling-Problem 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 job-weight I intend to have an LP-Based heuristic. I have implemented two greedy heuristics but I also want a LP-Based 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 totally-unimodular 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 lp-heuristic. 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