A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Industrial production processes involving both lot-sizing and cutting stock problems are common in many industrial settings. However, they are usually treated in a separate way, which could lead to costly production plans. In this paper, a coupled mathematical model is formulated and a heuristic method based on Lagrangian relaxation is proposed. Computational results prove its effectiveness. (C) 2009 Elsevier B.V. All rights reserved.

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (I the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry`s own practice. (c) 2006 Elsevier Ltd. All rights reserved.

Iterative variable aggregation and disaggregation in IP : an application

This paper, using the Unconstrained Shape Matrix Optimization Problem as a test bed, we investigate various aspects of variable aggregation and disaggregation for a class of integer programs that contains binary expansion. We present theoretical and numerical results, and propose an iterative algorithm for exact solutions.

New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP

In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known D^-_k and D⁺_k inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW ₂ inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.

Minimum span frequency assignment problem on triangular lattices

This paper considers the Minimum Span Frequency Assignment Problem with Interference Graph on Triangular Grid (MSFAP-TG), a special case of the Minimum Span Frequency/Channel Assignment (MSFAP) for cellular systems and optical networks. The MSFAP-TG is interesting in its own right and thus worth studying. In this paper, we propose strong integer programming formulations for the MSFAP-TG and present polyhedral results on these formulations. In solving the MSFAP-TG, we implement these integer programs to obtain exact solutions. We also develop a heuristic for obtaining feasible solutions and upper bounds for the problems. With the use of these upper bounds, and a simple lower bound, the computation time of the exact algorithm can be improved substantially. The heuristic turns out to be quite good in terms of the quality of upper bounds and is extremely efficient in computation time. Last of all, we present new concepts for tackling large scale MSFAP-TGs.

Integrated modelling of cost-effective siting and operation of flow-control infrastructure for river ecosystem conservation

Wetland and floodplain ecosystems along many regulated rivers are highly stressed, primarily due to a lack of environmental flows of appropriate magnitude, frequency, duration, and timing to support ecological functions. In the absence of increased environmental flows, the ecological health of river ecosystems can be enhanced by the operation of existing and new flow-control infrastructure (weirs and regulators) to return more natural environmental flow regimes to specific areas. However, determining the optimal investment and operation strategies over time is a complex task due to several factors including the multiple environmental values attached to wetlands, spatial and temporal heterogeneity and dependencies, nonlinearity, and time-dependent decisions. This makes for a very large number of decision variables over a long planning horizon. The focus of this paper is the development of a nonlinear integer programming model that accommodates these complexities. The mathematical objective aims to return the natural flow regime of key components of river ecosystems in terms of flood timing, flood duration, and interflood period. We applied a 2-stage recursive heuristic using tabu search to solve the model and tested it on the entire South Australian River Murray floodplain. We conclude that modern meta-heuristics can be used to solve the very complex nonlinear problems with spatial and temporal dependencies typical of environmental flow allocation in regulated river ecosystems. The model has been used to inform the investment in, and operation of, flow-control infrastructure in the South Australian River Murray.

The 0-1 Knapsack polytope – a starting point for cryptanalysis of Knapsack ciphers?

The Knapsack Cryptosystem of Merkle and Hellman, 1978, is one of the earliest public-key cryptography schemes. The security of the method relies on the difficulty in solving Subset Sum Problems (also known as Knapsack Problems). In this paper, we first provide a brief history of knapsack-based cryptosystems and their cryptanalysis attacks. Following that, we review the advances in integer programming approaches to 0 − 1 Knapsack Problems, with a focus on the polyhedral studies of the convex hull of the integer set. Last of all, we discuss potential future research directions in applying integer programming in the cryptanalysis of knapsack ciphers.

Optimal VM placement in data centres with architectural and resource constraints

Recent advance in virtualisation technology enables service provisioning in a flexible way by consolidating several virtual machines (VMs) into a single physical machine (PM). The inter-VM communications are inevitable when a group of VMs in a data centre provide services in a collaborative manner. With the increasing demands of such intra-data-centre traffics, it becomes essential to study the VM-to-PM placement such that the aggregated communication cost within a data centre is minimised. Such optimisation problem is proved NP-hard and formulated as an integer programming with quadratic constraints in this paper. Different from existing work, our formulation takes into consideration of data-centre architecture, inter-VM traffic pattern, and resource capacity of PMs. Furthermore, a heuristic algorithm is proposed and its high efficiency is extensively validated.

A Beam Search Method to Solve the Problem of Assignment Cells to Switches in a Cellular Mobile Network

Assigning cells to switches in a cellular mobile network is known as an NP-hard optimization problem. This means that the alternative for the solution of this type of problem is the use of heuristic methods, because they allow the discovery of a good solution in a very satisfactory computational time. This paper proposes a Beam Search method to solve the problem of assignment cell in cellular mobile networks. Some modifications in this algorithm are also presented, which allows its parallel application. Computational results obtained from several tests confirm the effectiveness of this approach and provide good solutions for large scale problems.

Abordagens complementares para problemas de p-medianas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Um modelo de otimização inteira mista e heurísticas relax and fix para a programação da produção de fábricas de refrigerantes de pequeno porte

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Energy balance optimization of sugarcane crop residual biomass

This work presents a mathematical model for helping mills choose sugarcane varieties for planting. It maximizes crop residual biomass energy balance by considering the difference between generated and consumed energy in the process of transferring this biomass from the field to the processing center; it takes into account enterprise demand restrictions and cane planting area. For this full zero-one linear programming techniques were proposed. The model is viable for choosing sugarcane varieties that would benefit sugarcane production and industrial systems, by reducing crop residue and increasing final energy production. (c) 2006 Published by Elsevier Ltd.