Abstract: We propose an algorithm based on infeasible irreducible subsystems to solve binary linear chance-constrained problems with random technology matrix. By leveraging on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete domain is used to guide us efficiently in the search of solutions. We apply our methodology to individual and joint binary linear chance-constrained problems, demonstrating the ability of our approach to solve those problems. Extensive numerical experiments show that, in some cases, the number of nodes explored by our algorithm is drastically reduced when compared to a commercial solver.

Abstract: We introduce and motivate several variants of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the general problem: a compact one and a stronger formulation with an exponential number of variables and constraints. We propose a branch-cut-and-price approach that exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem: when the number of possible bins available at each period is infinite and when this number is limited to one and time lags are nonnegative. Computational experiments are reported for instances inspired from a real-case application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branch-cutand-price approach, as it outperforms the compact formulation on newly proposed instances and is able to obtain improved lower and upper bounds for literature instances. Summary of Contribution: The paper considers a new variant of the bin packing problem, which is one of the most important problems in operations research. A motivation for introducing this variant is given, as well as a real-life application. We present a novel and original exact branch-cut-and-price algorithm for the problem. We implement this algorithm, and we present the results of extensive computational experiments. The results show a very good performance of our algorithm. We give several research directions that can be followed by subsequent researchers to extend our contribution to more complex and generic problems.

Abstract: The open pit mine production scheduling (OPMPS) problem seeks to determine when, if ever, to extract each notional, three-dimensional block of ore and/or waste in a deposit and what to do with each, e.g., send it to a particular processing plant or to the waste dump. This scheduling model maximizes net present value subject to spatial precedence constraints, and resource capacities. Certain mines use stockpiles for blending different grades of extracted material, storing excess until processing capacity is available, or keeping low-grade ore for possible future processing. Common models assume that material in these stockpiles, or “buckets,” is theoretically immediately mixed and becomes homogeneous. We consider stockpiles as part of our open pit mine scheduling strategy, propose multiple models to solve the OPMPS problem, and compare the solution quality and tractability of these linear-integer and nonlinear-integer models. Numerical experiments show that our proposed models are tractable, and correspond to instances which can be solved in a few seconds up to a few minutes in contrast to previous nonlinear models that fail to solve. (C) 2016 Elsevier B.V. All rights reserved.

Abstract: Underground mine production scheduling determines when, if ever, activities associated with the extraction of ore should be executed. The accumulation of heat in the mine where operators are working is a major concern. At the time of this writing, production scheduling and ventilation decisions are not made in concert. Correspondingly, heat limitations are largely ignored. Our mixed-integer program maximizes net present value subject to constraints on precedence, and mill and extraction capacities with the consideration of heat using thermodynamic principles, while affording the option of activating refrigeration to mitigate heat accumulation. In seconds to hours, depending on the problem size (up to thousands of activities and 900 daily time periods), a corresponding methodology that exploits the mathematical problem structure provides schedules that maintain a safe working environment for mine operators; optimality gaps are no more than 15% and average less than half that for otherwise-intractable instances.

Abstract: In continuous steel casting operations, heats of molten steel are alloyed and refined in ladles, continuously cast and cut into slabs, and hot-rolled into coils. We present a mixed-integer program that produces a daily casting schedule and that is solved using state-of-the-art software for a 100% direct-charge steel mill; two casters concurrently produce slabs, which are rolled into coils at a single hot rolling mill. This model minimizes penalties incurred by violating plant best practices while strictly adhering to safety and logical constraints to manage risk associated with manufacturing incidents. An efficient formulation, combined with variable reduction and cutting planes, expedites solutions for small instances containing hundreds of variables and thousands of constraints by factors of at least two or three (and sometimes even 100); instances an order of magnitude larger along both problem dimensions suggest solutions that reduce costs incurred using plant best practices by as much as 40%.