Comparing constraint programming and mathematical programming approaches to discrete optimisation—the change problem

This paper is aimed at researchers and practitioners in Operational Research who are interested in the new field of Constraint Programming/Constraint Logic Programming. Due to differing terminology and problem representation they might have found it difficult to access the field. The paper focuses on discrete optimisation problems. The first part lists frequently used terms in Constraint Programming (CP), contrasting them with their counterparts in Mathematical Programming (MP). The second part explains some of the most important concepts and techniques in more detail by comparing the CP and MP implementations of a small example problem, the ‘Change Problem’. It includes an overview of the respective results. In conclusion a more generalised comparison of CP and MP techniques is given.     

Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

一个修正的SQP方法-滤子方法

序列二次规划方法（SQP）是解决非线性规划问题最有效的算法之一，但是当QP子问题不可行时算法可能会失败．而且线搜索中的罚参数的选择通常比较困难．在文献[1]中，SQP方法得到了修正，使得QP子问题可行．在本文中，我们利用滤子技术避免了罚函数的使用同时提出了带线搜索的滤子方法，最终保证了SQP方法总是可行的，而且得到了方法的全局收敛性．     

Converging algorithm for a class of BMI applied on state-dependent stabilization of switched systems

In this paper, a design of a stabilizing state-dependent switching law is presented. First, it is based on a new reformulation of this control problem into a class of BMI (Bilinear Matrix Inequality) problem. The originality of this reformulation is that it will be used, in a second part, by an algorithm dedicated to solve this class of BMI without loss of generality. The construction of this algorithm is then specified, and the proof of its convergence is given for the two-subsystem case. The last part of the work consists in presenting the problem for a polytopic switching system, and how the previous algorithm can be extended. The proposed scheme is illustrated by an academical example.     

Exact number of limit cycles for a family of rigid systems

For a given family of planar differential equations it is a very difficult problem to determine an upper bound for the number of its limit cycles. Even when this upper bound is one it is not always an easy problem to distinguish between the case of zero and one limit cycle. This note mainly deals with this second problem for a family of systems with a homogeneous nonlinear part. While the condition that allows us to separate the existence and the nonexistence of limit cycles can be described, it is very intricate.

     

An improved decomposition-based heuristic to design a water distribution network for an irrigation system

In this paper the authors address a pressurized water distribution network design problem for irrigation purposes. Two mixed binary nonlinear programming models are proposed for this NP-hard problem. Furthermore, a heuristic algorithm is presented for the problem, which considers a decomposition sequential scheme, based on linearization of the second model, coupled with constructive and local search procedures designed to achieve improved feasible solutions. To evaluate the robustness of the method we tested it on several instances generated from a real application. The best solutions obtained are finally compared with solutions provided by standard software. These computational experiments enable the authors to conclude that the decomposition sequential heuristic is a good approach to this difficult real problem.     

利用散射波的叠加重建声波散射区域

本文研究了声波散射区域的重建，给上散射波的叠加重建散射区域的一个方法，该方法利用散射波的叠加，将声波障碍反散射这个非一不适定问题分两步处理，第一步求解一个第一类线性积分方程。第二步求解一个非线性最优化问题，我们证明了该方法的收敛性。     

A projected newton method forl p norm location problems

This paper is concerned with the numerical solution of continuous minisum multifacility location problems involving thel _p norm, where 1<p<x. This class of problems is potentially difficult to solve because the objective function is not everywhere diflerentiable. After developing conditions that characterize the minimum of the problems under consideration, a second-order algorithm is presented. This algorithm is based on the solution of a finite sequence of linearly constrained subproblems. Descent directions for these subproblems are obtained by projecting the Newton direction onto the corresponding constraint manifold. Univariate minimization is achieved via a specialized linesearch which recognizes the possibility of first derivative discontinuity (and second derivative unboundedness) at points along the search direction. The algorithm, motivated by earlier works of Calamai and Conn, and related to methods recently described by Overton and Dax, is shown to possess both global and quadratic convergence properties. Degeneracy can complicate the numerical solution of the subproblems. This degeneracy is identified, and a method for handling it is outlined. An implementation of the algorithm, that exploits the intrinsic structure of the location problem formulation, is then described along with a discussion of numerical results. The research was supported in part by Natural Sciences and Engineering Research Council of Canada grants A-5671 and A-8639 and by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38. This paper was typeset using software developed at Bell Laboratories and the University of California at Berkeley.     

Splineapproximationen von beliebigem Defekt zur numerischen Lösung gewöhnlicher Differentialgleichungen. Teil I

Summary In 1967, F.R. Loscalzo und T.D. Talbot presented a procedure for obtaining polynomial spline approximations of defect one for solutions of the initial value problem for first order ordinary differential equations. This method is generalized and investigated for spline approximations of arbitrary defect. The results are analogous to those of the defect one. In the first part of this paper the divergence problem is treated. The convergent procedures are investigated in a following second part of this paper.

     

From Brahmagupta to Euler: on the formula for the area of a cyclic quadrilateral

A formula for the area of a cyclic quadrilateral in terms of its sides was first stated without proof by the early seventh-century Indian mathematician Brahmagupta. As early as the late tenth century, the Persian mathematician al-Shannī provided a proof of the Indian's claim. In this paper I discuss al-Shannī's derivation and compare it with two other derivations. The first of these is by the Kerala mathematician and astronomer Jye??hadeva (sixteenth century), while the second is a forgotten proof by the Dutch mathematical practitioner Abraham de Graaf that was published in 1706. I conclude with a discussion of Euler's much better known derivation of 1748.     

A finite element approach to the position problems in open-loop variable geometry trusses

The present paper looks at some kinematic and static-equilibrium problems that arise with variable-geometry trusses (VGTs). The first part of the paper looks at the use of active controls in the correction of static deformations, the second part at the position problems. The separation between deformable- and rigid-body displacements makes it possible to consider separately the corrections in each component of the structure. VGTs are considered as open-loop linkages with redundant rigid-body degrees of freedom. Owing to this redundancy, possible solutions to the inverse problem are in general infinite, for which reason it is necessary to use some optimization criteria. To tackle the problem an optimization procedure with constraints is developed for the purpose of minimizing the displacements of the actuators. Suitable use of the constraints allows us to solve the direct position problem using the same optimization procedure.     

A note ‘On a single machine-scheduling problem with separated position and resource effects’

This note concerns the paper [Janiak A, Kovalyov MY, Lichtenstein M. On a single machine-scheduling problem with separated position and resource effects. Optimization; 2013. doi:10.1080/02331934.2013.804077], which presents an analysis, a counterexample and a pseudocode related with our proof of optimality for a resource allocation algorithm given in [Rudek A, Rudek R. A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models. Comput. Math. Appl. 2011;62:1870–1878]. We show that the discussed analysis is based only on one part of our proof omitting its integral second part, which is the source of misunderstanding. The considered counterexample is applied for an algorithm, which was not the method presented in our paper, whereas our algorithm provides the correct result for the mentioned counterexample. The provided pseudocode of the resource allocation algorithm, which is presented as the correct method, is a pseudocode of the algorithm described in our paper. Therefore, we show that the results presented in our paper are correct.     

On unique determination of domains in Euclidean spaces

The paper is devoted to two new directions in developing the classical geometric subjects related to studying the problem of unique determination of closed convex surfaces by their intrinsic metrics. The first of these directions is the study of unique determination of domains (i.e., open connected sets) in Euclidean spaces by relative metrics of the boundaries of these domains. It appeared about 25–30 years ago and was developed owing to the efforts of Russian scientists. The first part of the paper (Secs. 3–7) contains an overview of the results referring to this direction. The foundations of the second direction are presented in the second part of the paper, i.e., in Sec. 8, for the first time. This direction is closely related with the first one and consists of studying the problem of unique determination of conformal type. The main result of the section is the theorem on the unique determination of bounded convex domains by relative conformal moduli of their boundary conductors. __________ Translated from Sovremennaya Matematika. Fundamental’nye Napravleniya (Contemporary Mathematics. Fundamental Directions), Vol. 22, Geometry, 2007.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.     

Multi-Item Single-Level Capacitated Dynamic Lot-Sizing Heuristics: A General Review

The multi-item single-level capacitated lot-sizing problem consists of scheduling N different items over a horizon of T periods. The objective is to minimize the sum of set-up and inventory-holding costs over the horizon, subject to a capacity restriction in each period. Different heuristic approaches have been suggested to solve this difficult mathematical problem. So far, only a few limited attempts have been made to analyse and compare these approaches. The paper can be divided into two main parts. The first part shows that current heuristics can be classified in two different categories: single-resource heuristics, which are special-purpose methods, and mathematical-programming-based heuristics, which can usually deal with more general problem environments. The second part is devoted to an extensive computational review. The general idea is to find relationships between the performance of the heuristic and the computational burden involved in finding the solution. Based on these computational results, suggestions can be given with respect to the usefulness of the various heuristics in different industrial settings.     

On the dispersion of multivariate median

The estimation of the asymptotic variance of sample median based on a random sample of univariate observations has been extensively studied in the literature. The appearance of a local object like the density function of the observations in this asymptotic variance makes its estimation a difficult task, and there are several complex technical problems associated with it. This paper explores the problem of estimating the dispersion matrix of the multivariateL ₁ median. Though it is absolutely against common intuition, this problem turns out to be technically much simpler. We exhibit a simple estimate for the large sample dispersion matrix of the multivariateL ₁ median with excellent asymptotic properties, and to construct this estimate, we do not use any of the computationally intensive resampling techniques (e.g. the generalized jackknife, the bootstrap, etc. that have been used and thoroughly investigated by leading statisticians in their attempts to estimate the asymptotic variance of univariate median). However surprising may it sound, our analysis exposes that most of the technical complicacies associated with the estimation of the sampling variation in the median are only characteristics of univariate data, and they disappear as soon as we enter into the realm of multivariate analysis.The research of the second author was partially supported by a Wisconsin Alumni Research Foundation Grant from University of Wisconsin, Madison.     

Military antenna design using simple and competent genetic algorithms

Over the past decade, the Air Force Research Laboratory (AFRL) Antenna Technology Branch at Hanscom AFB has employed the simple genetic algorithm (SGA) as an optimization tool for a wide variety of antenna applications. Over roughly the same period, researchers at the Illinois Genetic Algorithm Laboratory (IlliGAL) at the University of Illinois at Urbana Champaign have developed GA design theory and advanced GA techniques called competent genetic algorithms—GAs that solve hard problems quickly, reliably, and accurately. Recently, under the guidance and direction of the Air Force Office of Scientific Research (AFOSR), the two laboratories have formed a collaboration, the common goal of which is to apply simple, competent, and hybrid GA techniques to challenging antenna problems.This paper is composed of two parts. The first part of this paper summarizes previous research conducted by AFRL at Hanscom for which SGAs were implemented to obtain acceptable solutions to several antenna problems. This research covers diverse areas of interest, including array pattern synthesis, antenna test-bed design, gain enhancement, electrically small single bent wire elements, and wideband antenna elements.The second part of this paper starts by briefly reviewing the design theory and design principles necessary for the invention and implementation of fast, scalable genetic algorithms. A particular procedure, the hierarchical Bayesian optimization algorithm (hBOA) is then briefly outlined, and the remainder of the paper describes collaborative efforts of AFRL and IlliGAL to solve more difficult antenna problems. In particular, recent results of using hBOA to optimize a novel, wideband overlapped subarray system to achieve −35 dB sidelobes over a 20% bandwidth. The problem was sufficiently difficult that acceptable solutions were not obtained using SGAs. The case study demonstrates the utility of using more advanced GA techniques to obtain acceptable solution quality as problem difficulty increases.     

Scoring Unusual Words with Varying Mismatch Errors

Patterns consisting of strings with a bounded number of mismatches are central to coding theory and find multiple applications in text processing and computational biology. In this latter field, the presence of over-represented patterns of this kind has been linked, for instance, to modeling regulatory regions in biosequences. The study and computation of expected number of occurrences and related scores for these patterns is made difficult by the sheer explosion of the roster of candidates that need to be evaluated. In recent work, properties of pattern saturation and score monotonicity have proved capable to mitigate this problem. In such a context, expectation and score monotonicity has been established within the i.i.d. model for all cases of interest except that of a fixed word length with a varying number of mismatches. The present paper completes this investigation by showing that the expected number of occurrences in a textstring for such a word is bi-tonic, that is, behaves as a unimodal function of the number of errors. This extends to this case the time and space savings brought about by discovery algorithms based on pattern saturation. Work Supported in part by the Italian Ministry of University and Research under the Bi-National Project FIRB RBIN04BYZ7, and by the Research Program of Georgia Tech. An extended abstract related to this work was presented at the Dagstuhl Seminar Dagstuhl on “Combinatorial and Algorithmic Foundations of Pattern and Association Discovery”, May 14-19, 2006 [3].     

Computing centre conditions for certain cubic systems

We present necessary and sufficient conditions for a critical point of certain two-dimensional cubic differential systems to be a centre. Extensive use of the computer algebra system REDUCE is involved. The search for necessary and sufficient conditions for a centre has long been of considerable interest in the theory of nonlinear differential equations. It has proved to be a difficult problem, and full conditions are known for very few classes of systems. Such conditions are also required in the investigation of Hilbert's sixteenth problem concerning the number of limit cycles of polynomial systems.     

Modelling resource availability in general hospitals design and implementation of a decision support model

Admission planning in general hospitals means selecting elective patients from a waiting list in order to obtain optimal utilisation of the available beds, nursing staff and operating theatre facilities while taking into account emergency admissions. Also, a wide variety of other factors, often situational and not explicitly stated, play a part in this decision process. As such, it is a complex problem which is difficult to handle for any decision maker. In this paper a statistical model for the prediction of resource availability is presented. The model is first tested on empirical data. On the basis of the model a DSS was designed which is now in daily use in several hospitals. Problems encountered in that implementation process will be stated. The results obtained with the model show that such an approach based on statistical data provides sufficiently accurate results to be useful.