Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Standing waves as an explanation for generic stationary correlation patterns in noninvasive EEG of focal onset seizures.

Cerebral electrical activity is highly nonstationary because the brain reacts to ever changing external stimuli and continuously monitors internal control circuits. However, a large amount of energy is spent to maintain remarkably stationary activity patterns and functional inter-relations between different brain regions. Here we examine linear EEG correlations in the peri-ictal transition of focal onset seizures, which are typically understood to be manifestations of dramatically changing inter-relations. Contrary to expectations we find stable correlation patterns with a high similarity across different patients and different frequency bands. This skeleton of spatial correlations may be interpreted as a signature of standing waves of electrical brain activity constituting a dynamical ground state. Such a state could promote the formation of spatiotemporal neuronal assemblies and may be important for the integration of information stemming from different local circuits of the functional brain network.

Non-linear gain - look-up table based approach for modeling a family of DC to DC converters based on transient response analysis

The purpose of this work is to propose a structure for simulating power systems using behavioral models of nonlinear DC to DC converters implemented through a look-up table of gains. This structure is specially designed for converters whose output impedance depends on the load current level, e.g. quasi-resonant converters. The proposed model is a generic one whose parameters can be obtained by direct measuring the transient response at different operating points. It also includes optional functionalities for modeling converters with current limitation and current sharing in paralleling characteristics. The pusposed structured also allows including aditional characteristics of the DC to DC converter as the efficency as a function of the input voltage and the output current or overvoltage and undervoltage protections. In addition, this proposed model is valid for overdamped and underdamped situations.

An example of Learning based on competences: Use of Maxima in Linear Algebra for Engineers

This paper analyzes the role of Computer Algebra Systems (CAS) in a model of learning based on competences. The proposal is an e-learning model Linear Algebra course for Engineering, which includes the use of a CAS (Maxima) and focuses on problem solving. A reference model has been taken from the Spanish Open University. The proper use of CAS is defined as an indicator of the generic ompetence: Use of Technology. Additionally, we show that using CAS could help to enhance the following generic competences: Self Learning, Planning and Organization, Communication and Writing, Mathematical and Technical Writing, Information Management and Critical Thinking.

A generic, hard transition to chaos

A hard-in-amplitude transition to chaos in a class of dissipative flows of broad applicability is presented. For positive values of a parameter F, no matter how small, a fully developed chaotic attractor exists within some domain of additional parameters, whereas no chaotic behavior exists for F < 0. As F is made positive, an unstable fixed point reaches an invariant plane to enter a phase half-space of physical solutions; the ghosts of a line of fixed points and a rich heteroclinic structure existing at F = 0 make the limits t --* +oc, F ~ +0 non-commuting, and allow an exact description of the chaotic flow. The formal structure of flows that exhibit the transition is determined. A subclass of such flows (coupled oscillators in near-resonance at any 2 : q frequency ratio, with F representing linear excitation of the first oscillator) is fully analysed

Linear Sparse Differential Resultant Formulas

Let P be a system of n linear nonhomogeneous ordinary differential polynomials in a set U of n-1 differential indeterminates. Differential resultant formulas are presented to eliminate the differential indeterminates in U from P. These formulas are determinants of coefficient matrices of appropriate sets of derivatives of the differential polynomials in P, or in a linear perturbation Pe of P. In particular, the formula dfres(P) is the determinant of a matrix M(P) having no zero columns if the system P is ``super essential". As an application, if the system PP is sparse generic, such formulas can be used to compute the differential resultant dres(PP) introduced by Li, Gao and Yuan.

Differential resultants of super essential systems of linear OD-polynomials

The sparse differential resultant dres(P) of an overdetermined system P of generic nonhomogeneous ordinary differential polynomials, was formally defined recently by Li, Gao and Yuan (2011). In this note, a differential resultant formula dfres(P) is defined and proved to be nonzero for linear "super essential" systems. In the linear case, dres(P) is proved to be equal, up to a nonzero constant, to dfres(P*) for the supper essential subsystem P* of P.

Modeling hybridoma cell metabolism using a generic genome-scale metabolic model of Mus musculus

The reconstructed cellular metabolic network of Mus musculus, based on annotated genomic data, pathway databases, and currently available biochemical and physiological information, is presented. Although incomplete, it represents the first attempt to collect and characterize the metabolic network of a mammalian cell on the basis of genomic data. The reaction network is generic in nature and attempts to capture the carbon, energy, and nitrogen metabolism of the cell. The metabolic reactions were compartmentalized between the cytosol and the mitochondria, including transport reactions between the compartments and the extracellular medium. The reaction list consists of 872 internal metabolites involved in a total of 1220 reactions, whereof 473 relate to known open reading frames. Initial in silico analysis of the reconstructed model is presented.

Generic Technique to Generate Large Branched DNA Complexes

The inherent self-recognition properties of DNA have led to its use as a scaffold for various nanotechnology self-assembly applications, with macromolecular complexes, metallic and semiconducting nanoparticles, proteins, inter alia, being assembled onto a designed DNA scaffold. Such structures may typically comprise a number of DNA molecules organized into macromolecules. Many studies have used synthetic methods to produce the constituent DNA molecules, but this typically constrains the molecules to be no longer than around 100 base pairs (30 nm). However, applications that require larger self-assembling DNA complexes, several tens of nanometers or more, need to be generated by other techniques. Here, we present a generic technique to generate large linear, branched, and/or circular DNA macromolecular complexes. The effectiveness of this technique is demonstrated here by the use of Lambda Bacteriophage DNA as a template to generate single- and double-branched DNA structures approximately 120 nm in size.

A fuzzy AHP based integer linear programming model for the multi-criteria transshipment problem

Purpose – The purpose of this research is to develop a holistic approach to maximize the customer service level while minimizing the logistics cost by using an integrated multiple criteria decision making (MCDM) method for the contemporary transshipment problem. Unlike the prevalent optimization techniques, this paper proposes an integrated approach which considers both quantitative and qualitative factors in order to maximize the benefits of service deliverers and customers under uncertain environments. Design/methodology/approach – This paper proposes a fuzzy-based integer linear programming model, based on the existing literature and validated with an example case. The model integrates the developed fuzzy modification of the analytic hierarchy process (FAHP), and solves the multi-criteria transshipment problem. Findings – This paper provides several novel insights about how to transform a company from a cost-based model to a service-dominated model by using an integrated MCDM method. It suggests that the contemporary customer-driven supply chain remains and increases its competitiveness from two aspects: optimizing the cost and providing the best service simultaneously. Research limitations/implications – This research used one illustrative industry case to exemplify the developed method. Considering the generalization of the research findings and the complexity of the transshipment service network, more cases across multiple industries are necessary to further enhance the validity of the research output. Practical implications – The paper includes implications for the evaluation and selection of transshipment service suppliers, the construction of optimal transshipment network as well as managing the network. Originality/value – The major advantages of this generic approach are that both quantitative and qualitative factors under fuzzy environment are considered simultaneously and also the viewpoints of service deliverers and customers are focused. Therefore, it is believed that it is useful and applicable for the transshipment service network design.

POSITIVE FILTERED P_N METHOD FOR LINEAR TRANSPORT EQUATIONS AND THE ASSOCIATED OPTIMIZATION ALGORITHM

We propose a positive, accurate moment closure for linear kinetic transport equations based on a filtered spherical harmonic (FP_N) expansion in the angular variable. The FP_N moment equations are accurate approximations to linear kinetic equations, but they are known to suffer from the occurrence of unphysical, negative particle concentrations. The new positive filtered P_N (FP_N+) closure is developed to address this issue. The FP_N+ closure approximates the kinetic distribution by a spherical harmonic expansion that is non-negative on a finite, predetermined set of quadrature points. With an appropriate numerical PDE solver, the FP_N+ closure generates particle concentrations that are guaranteed to be non-negative. Under an additional, mild regularity assumption, we prove that as the moment order tends to infinity, the FP_N+ approximation converges, in the L2 sense, at the same rate as the FP_N approximation; numerical tests suggest that this assumption may not be necessary. By numerical experiments on the challenging line source benchmark problem, we confirm that the FP_N+ method indeed produces accurate and non-negative solutions. To apply the FP_N+ closure on problems at large temporal-spatial scales, we develop a positive asymptotic preserving (AP) numerical PDE solver. We prove that the propose AP scheme maintains stability and accuracy with standard mesh sizes at large temporal-spatial scales, while, for generic numerical schemes, excessive refinements on temporal-spatial meshes are required. We also show that the proposed scheme preserves positivity of the particle concentration, under some time step restriction. Numerical results confirm that the proposed AP scheme is capable for solving linear transport equations at large temporal-spatial scales, for which a generic scheme could fail. Constrained optimization problems are involved in the formulation of the FP_N+ closure to enforce non-negativity of the FP_N+ approximation on the set of quadrature points. These optimization problems can be written as strictly convex quadratic programs (CQPs) with a large number of inequality constraints. To efficiently solve the CQPs, we propose a constraint-reduced variant of a Mehrotra-predictor-corrector algorithm, with a novel constraint selection rule. We prove that, under appropriate assumptions, the proposed optimization algorithm converges globally to the solution at a locally q-quadratic rate. We test the algorithm on randomly generated problems, and the numerical results indicate that the combination of the proposed algorithm and the constraint selection rule outperforms other compared constraint-reduced algorithms, especially for problems with many more inequality constraints than variables.