Exact solutions for the agricultural and the two-dimensional packing problems

Objectives and study method: The objective of this study is to develop exact algorithms that can be used as management tools for the agricultural production planning and to obtain exact solutions for two of the most well known twodimensional packing problems: the strip packing problem and the bin packing problem. For the agricultural production planning problem we propose a new hierarchical scheme of three stages to improve the current agricultural practices. The objective of the first stage is to delineate rectangular and homogeneous management zones into the farmer’s plots considering the physical and chemical soil properties. This is an important task because the soil properties directly affect the agricultural production planning. The methodology for this stage is based on a new method called “Positions and Covering” that first generates all the possible positions in which the plot can be delineated. Then, we use a mathematical model of linear programming to obtain the optimal physical and chemical management zone delineation of the plot. In the second stage the objective is to determine the optimal crop pattern that maximizes the farmer’s profit taken into account the previous management zones delineation. In this case, the crop pattern is affected by both management zones delineation, physical and chemical. A mixed integer linear programming is used to solve this stage. The objective of the last stage is to determine in real-time the amount of water to irrigate in each crop. This stage takes as input the solution of the crop planning stage, the atmospheric conditions (temperature, radiation, etc.), the humidity level in plots, and the physical management zones of plots, just to name a few. This procedure is made in real-time during each irrigation period. A linear programming is used to solve this problem. A breakthrough happen when we realize that we could propose some adaptations of the P&C methodology to obtain optimal solutions for the two-dimensional packing problem and the strip packing. We empirically show that our methodologies are efficient on instances based on real data for both problems: agricultural and two-dimensional packing problems. Contributions and conclusions: The exact algorithms showed in this study can be used in the making-decision support for agricultural planning and twodimensional packing problems. For the agricultural planning problem, we show that the implementation of the new hierarchical approach can improve the farmer profit between 5.27% until 8.21% through the optimization of the natural resources. An important characteristic of this problem is that the soil properties (physical and chemical) and the real-time factors (climate, humidity level, evapotranspiration, etc.) are incorporated. With respect to the two-dimensional packing problems, one of the main contributions of this study is the fact that we have demonstrate that many of the best solutions founded in literature by others approaches (heuristics approaches) are the optimal solutions. This is very important because some of these solutions were up to now not guarantee to be the optimal solutions.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Two-Dimensional Bin Packing Problem with Guillotine Restrictions

This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed. A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective. Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

Effects of potential models on the adsorption of ethane and ethylene on graphitized thermal carbon black. Study of two-dimensional critical temperature and isosteric heat versus loading

Adsorption of ethylene and ethane on graphitized thermal carbon black and in slit pores whose walls are composed of graphene layers is studied in detail to investigate the packing efficiency, the two-dimensional critical temperature, and the variation of the isosteric heat of adsorption with loading and temperature. Here we used a Monte Carlo simulation method with a grand canonical Monte Carlo ensemble. A number of two-center Lennard-Jones (LJ) potential models are investigated to study the impact of the choice of potential models in the description of adsorption behavior. We chose two 2C-LJ potential models in our investigation of the (i) UA-TraPPE-LJ model of Martin and Siepmann (J. Phys. Chem. B 1998,102, 25692577) for ethane and Wick et al. (J. Phys. Chem. B 2000,104, 8008-8016) for ethylene and (ii) AUA4-LJ model of Ungerer et al. (J. Chem. Phys. 2000,112, 5499-5510) for ethane and Bourasseau et al. (J. Chem. Phys. 2003, 118, 3020-3034) for ethylene. These models are used to study the adsorption of ethane and ethylene on graphitized thermal carbon black. It is found that the solid-fluid binary interaction parameter is a function of adsorbate and temperature, and the adsorption isotherms and heat of adsorption are well described by both the UA-TraPPE and AUA models, although the UA-TraPPE model performs slightly better. However, the local distributions predicted by these two models are slightly different. These two models are used to explore the two-dimensional condensation for the graphitized thermal carbon black, and these values are 110 K for ethylene and 120 K for ethane.

Zero- one- and two-dimensional hydrogen-bonded structures in the 1:1 proton-transfer compounds of 4,5-dichlorophthalic acid with the monocyclic heteroaromatic Lewis bases 2-aminopyrimidine, nicotinamide and isonicotinamide

The structures of the anhydrous 1:1 proton-transfer compounds of 4,5-dichlorophthalic acid (DCPA) with the monocyclic heteroaromatic Lewis bases 2-aminopyrimidine, 3-(aminocarboxy) pyridine (nicotinamide) and 4-(aminocarbonyl) pyridine (isonicotinamide), namely 2-aminopyrimidinium 2-carboxy-4,5-dichlorobenzoate C4H6N3+ C8H3Cl2O4- (I), 3-(aminocarbonyl) pyridinium 2-carboxy-4,5-dichlorobenzoate C6H7N2O+ C8H3Cl2O4- (II) and the unusual salt adduct 4-(aminocarbonyl) pyridinium 2-carboxy-4,5-dichlorobenzoate 2-carboxymethyl-4,5-dichlorobenzoic acid (1/1/1) C6H7N2O+ C8H3Cl2O4-.C9H6Cl2O4 (III) have been determined at 130 K. Compound (I) forms discrete centrosymmetric hydrogen-bonded cyclic bis(cation--anion) units having both R2/2(8) and R2/1(4) N-H...O interactions. In compound (II) the primary N-H...O linked cation--anion units are extended into a two-dimensional sheet structure via amide-carboxyl and amide-carbonyl N-H...O interactions. The structure of (III) reveals the presence of an unusual and unexpected self-synthesized methyl monoester of the acid as an adduct molecule giving one-dimensional hydrogen-bonded chains. In all three structures the hydrogen phthalate anions are

Unusual hydrate stabilization in the two-dimensional layered structure of quinacrinium bis(2-carboxy-4,5-dichlorobenzoate) tetrahydrate, a proton-transfer compound of the drug quinacrine

The crystal structure of the hydrated proton-transfer compound of the drug quinacrine [rac-N'-(6-chloro-2-methoxyacridin-9-yl)-N,N-diethylpentane-1,4-diamine] with 4,5-dichlorophthalic acid, C23H32ClN3O2+ . 2(C8H3Cl2O4-).4H2O (I), has been determined at 200 K. The four labile water molecules of solvation form discrete ...O--H...O--H... hydrogen-bonded chains parallel to the quinacrine side chain, the two N--H groups of which act as hydrogen-bond donors for two of the water acceptor molecules. The other water molecules, as well as the acridinium H atom, also form hydrogen bonds with the two anion species and extend the structure into two-dimensional sheets. Between these sheets there are also weak cation--anion and anion--anion pi-pi aromatic ring interactions. This structure represents only the third example of a simple quinacrine derivative for which structural data are available but differs from the other two in that it is unstable in the X-ray beam due to efflorescence, probably associated with the destruction of the unusual four-membered water chain structures.

Numerical schemes and multivariate extrapolation of a two-dimensional anomalous sub-diffusion equation

Anomalous dynamics in complex systems have gained much interest in recent years. In this paper, a two-dimensional anomalous subdiffusion equation (2D-ASDE) is considered. Two numerical methods for solving the 2D-ASDE are presented. Their stability, convergence and solvability are discussed. A new multivariate extrapolation is introduced to improve the accuracy. Finally, numerical examples are given to demonstrate the effectiveness of the schemes and confirm the theoretical analysis.

Modified alternating direction methods for solving a two-dimensional non-continuous seepage flow with fractional derivatives

In this paper, a two-dimensional non-continuous seepage flow with fractional derivatives (2D-NCSF-FD) in uniform media is considered, which has modified the well known Darcy law. Using the relationship between Riemann-Liouville and Grunwald-Letnikov fractional derivatives, two modified alternating direction methods: a modified alternating direction implicit Euler method and a modified Peaceman-Rachford method, are proposed for solving the 2D-NCSF-FD in uniform media. The stability and consistency, thus convergence of the two methods in a bounded domain are discussed. Finally, numerical results are given.

Phenyl-ring disorder in the two-dimensional hydrogen-bonded structure of the 1:1 proton-transfer salt of the diazo-dye precursor 4-(phenyldiazenyl)aniline (aniline yellow) with L-tartaric acid

The structure of the 1:1 proton-transfer compound from the reaction of L-tartaric acid with the azo-dye precursor aniline yellow [4-(phenylazo)aniline], 4-(phenyldiazenyl)anilinium hydrogen 2R,3R-tartrate C12H12N3+ . C4H6O6- has been determined at 200 K. The asymmetric unit of the compound contains two independent phenylazoanilinium cations and two hydrogen L-tartrate anions. The structure is unusual in that all four phenyl rings of both cations have identical 50% rotational disorder. The two hydrogen L-tartrate anions form independent but similar chains through head-to-tail carboxylic O--H...O~carboxyl~ hydrogen bonds [graph set C7] which are then extended into a two-dimensional hydrogen-bonded sheet structure through hydroxyl O--H...O hydrogen-bonding links. The anilinium groups of the phenyldiazenyl cations are incorporated into the sheets and also provide internal hydrogen-bonding extensions while their aromatic tails layer in the structure without significant interaction except for weak \p--\p interactions [minimum ring centroid separation, 3.844(3) \%A]. The hydrogen L-tartrate residues of both anions have the common short intramolecular hydroxyl O--H...O~carboxyl~ hydogen bonds. This work has provided a solution to the unusual disorder problem inherent in the structure of this salt as well as giving another example of the utility of the hydrogen tartrate in the generation of sheet substructures in molecular assembly processes.

A two-Dimensional finite volume method for variable density flow and solute transport through saturated-unsaturated media

Extensive groundwater withdrawal has resulted in a severe seawater intrusion problem in the Gooburrum aquifers at Bundaberg, Queensland, Australia. Better management strategies can be implemented by understanding the seawater intrusion processes in those aquifers. To study the seawater intrusion process in the region, a two-dimensional density-dependent, saturated and unsaturated flow and transport computational model is used. The model consists of a coupled system of two non-linear partial differential equations. The first equation describes the flow of a variable-density fluid, and the second equation describes the transport of dissolved salt. A two-dimensional control volume finite element model is developed for simulating the seawater intrusion into the heterogeneous aquifer system at Gooburrum. The simulation results provide a realistic mechanism by which to study the convoluted transport phenomena evolving in this complex heterogeneous coastal aquifer.

Minimising wave drag for free surface flow past a two-dimensional stern

Free surface flow past a two-dimensional semi-infinite curved plate is considered, with emphasis given to solving for the shape of the resulting wave train that appears downstream on the surface of the fluid. This flow configuration can be interpreted as applying near the stern of a wide blunt ship. For steady flow in a fluid of finite depth, we apply the Wiener-Hopf technique to solve a linearised problem, valid for small perturbations of the uniform stream. Weakly nonlinear results found using a forced KdV equation are also presented, as are numerical solutions to the fully nonlinear problem, computed using a conformal mapping and a boundary integral technique. By considering different families of shapes for the semi-infinite plate, it is shown how the amplitude of the waves can be minimised. For plates that increase in height as a function of the direction of flow, reach a local maximum, and then point slightly downwards at the point at which the free surface detaches, it appears the downstream wavetrain can be eliminated entirely.