Aggregate subgradients in Lagrangean relaxation of integer programming problems. (Polish. English, Russian summaries) Zbl 0657.90068

Kiewiel, Krzysztof; Toczyłowski, Eugeniusz

Zesz. Nauk. Politech. Śląsk., Autom. 84, 119-129 (1986).

This paper presents the use of the subgradient descent method of the first author [“Methods of descent for nondifferentiable optimization”, Lect. Notes Math. 1133 (1985; Zbl 0561.90059)] in Lagrangean relaxation of mixed integer programming problems. The method maximizes the dual function by constructing piecewise linear approximations and solving quadratic programming subproblems. An aggregate solution of the relaxed problem is then computed that satisfies the dualized constraints. Such a solution facilitates finding near-optimal feasible solutions to the original problem. Two production scheduling problems are considered as examples: sequencing of preemptive tasks on parallel machines with set-up times, and a constrained version of the lot size scheduling problem. For these problems the inaccuracy of the feasible solution found by the method converges to zero as the complexity of the problem (number of machines or products) increases.

MSC:

90C10	Integer programming
65K05	Numerical mathematical programming methods
90B35	Deterministic scheduling theory in operations research

Keywords:

subgradient descent; Lagrangean relaxation; dual function; piecewise linear approximations; quadratic programming subproblems; near-optimal feasible solutions; sequencing; preemptive tasks; parallel machines; lot size scheduling

Citations:

Zbl 0561.90059