A MIP-based framework and its application on a lot sizing problem with setup carryover

Caserta, Marco; Voß, Stefan
April 2013
Journal of Heuristics;Apr2013, Vol. 19 Issue 2, p295
Academic Journal
In this paper we present a framework to tackle mixed integer programming problems based upon a 'constrained' black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to the original MIP formulation. Such corridors, or neighborhoods, are then explored, possibly to optimality, with a standard MIP solver. An iterative approach in the spirit of a hill climbing scheme is thus used to explore subportions of the solution space. While the exploration of the corridor relies on a standard MIP solver, the way in which such corridors are built around the incumbent solutions is influenced by a set of factors, such as the distance metric adopted, or the type of method used to explore the neighborhood. The proposed framework has been tested on a challenging variation of the lot sizing problem, the multi-level lot sizing problem with setups and carryovers. When tested on 1920 benchmark instances of such problem, the algorithm was able to solve to near optimality every instance of the benchmark library and, on the most challenging instances, was able to find high quality solutions very early in the search process. The algorithm was effective, in terms of solution quality as well as computational time, when compared with a commercial MIP solver and the best algorithm from the literature.


Related Articles

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • A Constraint Programming-based Genetic Algorithm (CPGA) for Capacity Output Optimization. Kate Ean Nee Goh; Jeng Feng Chin; Wei Ping Loh; Melissa Chea-Ling Tan // Journal of Industrial Engineering & Management;2014, Vol. 7 Issue 5, p1222 

    Purpose: The manuscript presents an investigation into a constraint programming-based genetic algorithm for capacity output optimization in a back-end semiconductor manufacturing company. Design/methodology/approach: In the first stage, constraint programming defining the relationships between...

  • Shift-and-Propagate. Berthold, Timo; Hendel, Gregor // Journal of Heuristics;Feb2015, Vol. 21 Issue 1, p73 

    In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address...

  • Comparing mathematical and heuristic rules for solving single machine scheduling problem with release and due date constraints. Yong Zhan; Haitao Zhu; Yuguang Zhong // Applied Mechanics & Materials;2014, Issue 635-637, p1707 

    The purpose of this paper is to compare a mixed integer programming(MIP) model, and heuristic rules based on their practical efficiency and the accuracy of results to tackle the minimum lateness single machine scheduling problem with release and due date constraints. Extensive numerical...

  • Dynamic Facility Location with Generalized Modular Capacities. Jena, Sanjay Dominik; Cordeau, Jean-François; Gendron, Bernard // Transportation Science;Aug2015, Vol. 49 Issue 3, p484 

    Location decisions are frequently subject to dynamic aspects such as changes in customer demand. Often, flexibility regarding the geographic location of facilities, as well as their capacities, is the only solution to such issues. Even when demand can be forecast, finding the optimal schedule...

  • Valid Linear Programming Bounds for Exact Mixed-Integer Programming. Steffy, Daniel E.; Wolter, Kati // INFORMS Journal on Computing;Spring2013, Vol. 25 Issue 2, p271 

    Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be...

  • Optimal Cardinality Constrained Portfolio Selection. Jianjun Gao; Duan Li // Operations Research;May/Jun2013, Vol. 61 Issue 3, p745 

    One long-standing challenge in both the optimization and investment communities is to devise an efficient algorithm to select a small number of assets from an asset pool such that a portfolio objective is optimized. This cardinality constrained investment situation naturally arises due to the...

  • A scenario-based mixed integer linear programming model for composite power system expansion planning with greenhouse gas emission controls. Chang, Mei-Shiang // Clean Technologies & Environmental Policy;Aug2014, Vol. 16 Issue 6, p1001 

    In this paper, the influence of uncertain factors in the power supply system is considered by applying scenario-based programming techniques. A multi-period network design model for composite power system expansion planning is formulated as a mixed integer programming model. This model aims to...

  • Uplink Task Scheduling Model and Heuristic Algorithm of Satellite Navigation System. LONG Yunjun; WANG Pei; ZHANG Zhongshan; Chen Yingwu // Advances in Information Sciences & Service Sciences;Sep2012, Vol. 4 Issue 16, p363 

    In order to keep the service availability, continuity, and accuracy of satellite navigation system, the navigation data of the navigation constellation should be updated periodically. Ground facility should be assigned to contact with the satellite to support the navigation data update process....


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics