Skip to main content

How to implement an LP Relaxation with Gurobi

Answered

Comments

4 comments

  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    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,
    Matthias

    0
  • MG
    Gurobi-versary
    First Comment
    First Question

    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
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    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,
    Matthias

    0
  • MG
    Gurobi-versary
    First Comment
    First Question

    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.