Line: 1 to 1  

 
Changed:  
< <  L(inear) P(rogramming) Relaxation  
> >  Linear Programming Relaxation  
Changed:  
< <  The Linear Programming (LP) relaxation is the same as the integer programme, except we "relax" the integer variables to allow them to take fractional values. The integer programme's feasible region lies within the feasible region of the LP relaxation (at points where the integer variables have integer values). Therefore the integer restrictions cause the optimal objective function value to be worse in the integer programme as compared to the LP relaxation. However, if a solution $x$ of the LP relaxation has integer values for the integer variables, then $x$ also solves the integer programme. In some cases, if the solution values for the integer variables are large, then rounding the LP relaxation solution may give a good solution to the integer programme. However, you need to make sure that the rounded solution is not infeasible! For some classes of problem the LP relaxation gives naturally integer solutions:
In AMPL, the LP relaxation may be solved simply by turning on the {\tt relax_integrality} option: \begin{verbatim}
 
> >  The Linear Programming (LP) relaxation is the same as the original integer programme, except we "relax" the integer variables to allow them to take fractional values. The integer programme's feasible region lies within the feasible region of the LP relaxation (at points where the integer variables have integer values). Therefore the integer restrictions cause the optimal objective function value to be worse in the integer programme as compared to the LP relaxation. However, if a solution of the LP relaxation has integer values for the integer variables, then also solves the integer programme. In some cases, if the solution values for the integer variables are large, then rounding the LP relaxation solution may give a good solution to the integer programme. However, you need to make sure that the rounded solution is not infeasible!
For some classes of problem the LP relaxation gives naturally integer solutions:
In some mathematical programming software, the integer restrictions may be easily realxed and the software will solve the LP relaxation instead. For example, in AMPL the LP relaxation may be solved simply by turning on the option relax_integrality 1;Turning it off: option relax_integrality 0;means that the integer programme will be solved again.  
 MichaelOSullivan  23 Apr 2008 \ No newline at end of file  
Added:  
> > 

Line: 1 to 1  

Added:  
> > 
L(inear) P(rogramming) Relaxation
The Linear Programming (LP) relaxation is the same as the integer programme, except we "relax" the integer variables to allow them to take fractional values. The integer programme's feasible region lies within the feasible region of the LP relaxation (at points where the integer variables have integer values). Therefore the integer restrictions cause the optimal objective function value to be worse in the integer programme as compared to the LP relaxation. However, if a solution $x$ of the LP relaxation has integer values for the integer variables, then $x$ also solves the integer programme. In some cases, if the solution values for the integer variables are large, then rounding the LP relaxation solution may give a good solution to the integer programme. However, you need to make sure that the rounded solution is not infeasible!
In AMPL, the LP relaxation may be solved simply by turning on the {\tt relax_integrality} option: \begin{verbatim}
 MichaelOSullivan  23 Apr 2008 