(Mixed) Integer Linear Programming

Scheduling optimization of a real flexible job shop including side constraints regarding maintenance, fixtures, and night shifts

  • Torgny Almgren
  • Michael Patriksson
  • Ann-Brith Strömberg
  • Karin Thörnblad
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Scheduling Tags , , , , ,

    We present a generic iterative scheduling procedure for the scheduling of a real flexible job shop, the so-called multitask cell at GKN Aerospace Engine Systems in Sweden. A time-indexed formulation of the problem is presented including side constraints regarding preventive maintenance, fixture availability, and unmanned night shifts. This paper continues the work in Thörnblad et … Read more

    A competitive iterative procedure using a time-indexed model for solving flexible job shop scheduling problems

  • Torgny Almgren
  • Michael Patriksson
  • Ann-Brith Strömberg
  • Karin Thörnblad
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Scheduling Tags , , , , , ,

    We investigate the efficiency of a discretization procedure utilizing a time-indexed mathematical optimization model for finding accurate solutions to flexible job shop scheduling problems considering objectives comprising the makespan and the tardiness of jobs, respectively. The time-indexed model is used to find solutions to these problems by iteratively employing time steps of decreasing length. The … Read more

    Improving the LP bound of a MILP by dual concurrent branching and the relationship to cut generation methods

  • H. Georg Büsching
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags ,

    In this paper branching for attacking MILP is investigated. Under certain circumstances branches can be done concurrently. By introducing a new calculus it is shown there are restrictions for dual values. As a second result of this study a new class of cuts for MILP is found, which are defined by those values. This class … Read more

    A fix-and-relax heuristic for controlled tabular adjustment

  • Daniel Baena
  • Jordi Castro
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering

    Controlled tabular adjustment (CTA) is an emerging protection technique for tabular data protection. CTA formulates a mixed integer linear programming problem, which is tough for tables of moderate size. Finding a feasible initial solution may even be a challenging task for large instances. On the other hand, end users of tabular data protection techniques give … Read more

    Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems

  • Amir Ardestani-Jaafari
  • Erick Delage
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Robust Optimization Tags , , , , , ,

    Robust optimization is a methodology that has gained a lot of attention in the recent years. This is mainly due to the simplicity of the modeling process and ease of resolution even for large scale models. Unfortunately, the second property is usually lost when the cost function that needs to be robustified is not concave … Read more

    Using diversification, communication and parallelism to solve mixed-integer linear programs

  • Shabbir Ahmed
  • Rodolfo Carvajal
  • Kevin C Furman
  • George L. Nemhauser
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , , , ,

    Performance variability of modern mixed-integer programming solvers and possible ways of exploiting this phenomenon present an interesting opportunity in the development of algorithms to solve mixed-integer linear programs (MILPs). We propose a framework using multiple branch-and-bound trees to solve MILPs while allowing them to share information in a parallel execution. We present computational results on … Read more

    A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    Research on due date oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work … Read more

    Acceleration and Stabilization Techniques for Column Generation Applied to Capacitated Resource Management Problems

  • Alper Uygur
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling Tags , , ,

    This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column … Read more

    Locally Ideal Formulations for Piecewise Linear Functions with Indicator Variables

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering

    In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context. CitationTechnical Report #1788, Computer Sciences Department, University of Wisconsin-Madison.ArticleDownload … Read more

    On the Transportation Problem with Market Choice

  • Pelin Damci-Kurt
  • Santanu S. Dey
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , ,

    We study a variant of the classical transportation problem in which suppliers with limited capacities have a choice of which demands (markets) to satisfy. We refer to this problem as the transportation problem with market choice (TPMC). While the classical transportation problem is known to be strongly polynomial-time solvable, we show that its market choice … Read more