We study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given ...
详细信息
We study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to design a set of shelves and a set of compartments on each shelf, and select the items to insert into the compartments. The objective is to maximize the sum of the profits of the selected items. We call our problem the Storage Cabinet Physical Design (SCPD) problem. The SCPD problem combines a two-staged two-dimensional knapsack problem for designing the shelves and compartments with a set of temporal knapsack problems for selecting and assigning items to compartments. We formalize the SCPD problem and formulate it as a maximum cost flow problem in a decision hypergraph with additional linear constraints. To reduce the size of this model, we break symmetries, generalize graph compression techniques and exploit dominance rules for precomputing subproblem solutions. We also present a set of valid inequalities to improve the linear relaxation of the model. We empirically show that solving the arc-flow model with our enhancements outperforms solving a compact mixed integer linear programming formulation of the SCPD problem.
We investigate the problem of designing an optimal annual delivery plan for Liquefied Natural Gas (LNG). This problem requires determining the long-term cargo delivery dates and the assignment of vessels to the cargoe...
详细信息
We investigate the problem of designing an optimal annual delivery plan for Liquefied Natural Gas (LNG). This problem requires determining the long-term cargo delivery dates and the assignment of vessels to the cargoes while accommodating several constraints, including berth availability, liquefaction terminal inventory, planned maintenance, and bunkering requirements. We describe a novel mixed-integer programming formulation that captures important industry requirements and constraints with the objective of minimizing the vessel fleet size. A peculiar property of the proposed formulation is that it includes a polynomial number of variables and constraints and is, in our experience, computationally tractable for large problem instances using a commercial solver. Extensive computational runs demonstrate the efficacy of the proposed model for real instances provided by a major energy company that involve up to 118 cargoes and a 373-day planning horizon. (C) 2016 Elsevier Ltd. All rights reserved.
We present a new integer linear formulation for the problem of minimizing the total completion time on a single parallel-batching machine. The new formulation is strong, in the sense that it delivers a sharp lower bou...
详细信息
We present a new integer linear formulation for the problem of minimizing the total completion time on a single parallel-batching machine. The new formulation is strong, in the sense that it delivers a sharp lower bound, and compact, i.e. polynomial in size, contrasted to recent successful models for the same problem that have exponential size and require to be handled by column generation. The new model is promising: combined with a rounding procedure, it allows to deliver good solutions with small, certified optimality gaps for instances with up to 50 jobs, and we believe it is susceptible of further improvements. Copyright (C) 2022 The Authors.
We present a new integer linear formulation for the problem of minimizing the total completion time on a single parallel-batching machine. The new formulation is strong, in the sense that it delivers a sharp lower bou...
详细信息
We present a new integer linear formulation for the problem of minimizing the total completion time on a single parallel-batching machine. The new formulation is strong, in the sense that it delivers a sharp lower bound, and compact, i.e. polynomial in size, contrasted to recent successful models for the same problem that have exponential size and require to be handled by column generation. The new model is promising: combined with a rounding procedure, it allows to deliver good solutions with small, certified optimality gaps for instances with up to 50 jobs, and we believe it is susceptible of further improvements.
暂无评论