Linear programming relaxation

Linear programming relaxation refers to the process of solving the associated linear programming problem of an integer or mixed integer programming problem, where the discrete variables are allowed to take continuous values, in order to obtain an optimal fractional solution. This method is used to obtain a bound on the optimal objective function value of the original problem, and the fractional solution is then rounded to a feasible integer solution with a bounded error.From: Operations Research and Management Science Handbook [2019], Handbook of SCHEDULING [2004], Electric Power System Applications of Optimization [2019]

Introduction

View Chapter

Purchase Book

Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004

Joseph Y.-T. Leung

A number of approximation algorithms for scheduling problems have been developed that are based on linear programming. The basic idea is to formulate the scheduling problem as an integer programming problem, solve the underlying linear programming relaxation to obtain an optimal fractional solution, and then round the fractional solution to a feasible integer solution in such a way that the error can be bounded. Chapter 16 describes this technique as applied to the problem of minimizing the total weighted completion time on unrelated machines.

Stochastic customer order scheduling with setup times to minimize expected cycle time

View Article

Journal Information

Published in International Journal of Production Research, 2018

Yaping Zhao, Xiaoyun Xu, Haidong Li, Yanni Liu

All simulations are coded using MATLAB R2012a, and implemented on a computer with 3.6GHz CPU and 16.0GByte RAM memory. To obtain the lower bound, attempts are made to solve the MIP in Theorem 4 by CPLEX Linear Optimizer version 12.0. When setup times are considered, since solving a mixed integer programme is NP-hard in general, it is difficult to obtain the optimal solution in a reasonable amount of time. Therefore, for large-scale problems, the associated linear programming relaxation of MIP is utilized instead. This allows a solution to be acquired quickly but at the cost of a worse lower bound. When setup times are not considered, type sequences actually have no effect on the objective value, and the MIP can be reduced to a linear programme with as the decision variable.

Linear programming relaxation

Explore chapters and articles related to this topic

Introduction

Stochastic customer order scheduling with setup times to minimize expected cycle time