Semidefinite relaxations for lot-sizing and scheduling problems – LotRelax

To deal with the lot-sizing problems investigated within projet LotRelax, we rely on an approach based on mathematical programming. We thus first model the underlying optimization problem and formulate a mathematical program. We then develop solution algorithms that enable us to find an optimal solution of the mathematical program, i.e. an optimal production plan.
Most of the work carried out during the project was related to so-called “deterministic” lot-sizing problems, i.e. problems in which all the input data of the optimization problem (customer demand, production capacity, costs…) are assumed to be perfectly known at the time where the production plan has to be decided upon. We also devoted some time to model and solve “stochastic” lot-sizing problems, in particular problems in which the customer demand is subject to uncertainty.

We first focused on solving deterministic lot-sizing problems. We investigated two main directions: the study of a new solution approach based on the use of a semidefinite relaxation of the problem and the development of a new family of valid inequalities to strengthen the linear relaxation of the problem. This work enabled us to reduce the running time of the algorithms used to solve the mathematical programs modeling the optimization problem: the average computation time needed to obtain the optimal production plan was thus reduced by 30%.
We also proposed a new model for stochastic lot-sizing problems. Its main advantage is that it enables production managers to manage the risk of a stock-out at the planning horizon level, rather than on a period by period basis as is usually done. A new solution approach leading to significantly reduced computation times was also developed.

Future research perspectives meanly deal with the modeling and solving of stochastic lot-sizing problems.

The main scientific results of the project led to the publication of two papers in international journal, five papers in international conferences with proceedings, five communications in international conferences without proceedings. The paper published at the international conference ICORES2013 got the best application paper award.

- Journal papers
C. Gicquel, M. Minoux. Multi-product valid inequalities for the discrete lot-sizing and scheduling problem. Computers & Operations Research, 2015, vol. 54, pp 12-20.
C. Gicquel, M. Minoux, A. Lisser. An evaluation of semidefinite programming based approaches for discrete lot-sizing problems. European Journal of Operational Research, 2014, vol. 137(2), pp 498–507.

- Paper awarded at an international conference with proceedings
C. Gicquel and M. Minoux. New multi-product valid inequalities for a discrete lot-sizing problem. 3rd International Conference on Operations Research and Enterprise Systems. March 2014, Angers, France. Best Application Paper Award.

Fierce competition in today's global market forces industrial companies to better design and manage their supply chain networks. In particular, making the right decisions regarding one of the core supply chain processes, goods production, directly affects the productivity and hence the competitiveness of a company. Industrial production management involves, among others, deciding about which products should be made, when and in which quantity. Despite its rather simple definition, production planning is most often a complex task for industrial managers who can be overwhelmed by the complexity of the problem. This is particularly the case when production planning involves lot-sizing and scheduling decisions. This arises whenever start-up operations such as tool changes are required between production runs of different products on a machine. In this situation, finding the right quantity to produce after a start-up, i.e. the lot size, requires reaching a good trade-off between start-up costs (indicating large lot sizes) and inventory holding costs (indicating small lot sizes) . Lot-sizing and scheduling leads to the formulation of difficult combinatorial optimization problems. A wide variety of solution techniques from the Operations Research field have been proposed to solve them. The scientific challenge here is to develop optimization methods in which the production system is modelled with the required accuracy and which are capable of providing guaranteed optimal or near-optimal production plans within reasonable computation times. In this context, project LotRelax focuses on:
(i) improving the production system representation in the optimization method by taking into account a complicating feature frequently encountered in practice: the presence of sequence-dependent start-up costs and times,
(ii) computing guaranteed optimal or near-optimal production plans by exploiting recent theoretical advances in the mathematical programming field, in particular the latest developments in semidefinite programming. Semidefinite programming can be broadly described as the extension of linear programming from the space of real vectors to the space of symmetric matrices. This rather new area of mathematical programming has witnessed important developments during the last twenty years and has proved successful at solving prominent difficult combinatorial optimization problems. However, as can be seen from recent reviews in the academic literature, there seems to be no previous attempt at using semidefinite relaxations to solve lot-sizing and scheduling problem. The main objective of project LotRelax is thus to develop solution approaches based on semidefinite relaxations to solve several variants of lot-sizing problems involving sequence-dependent start-up costs and times.