A branch-and-cut procedure for the Udine Course Timetabling problem

A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem.     

Adjoint Estimation from a Direct Multiple Shooting Method

To solve the multipoint boundary-value problem (MPBVP) associated with a constrained optimal control problem, one needs a good guess not only for the state but also for the costate variables. A direct multiple shooting method is described, which yields approximations of the optimal state and control histories. The Kuhn–Tucker conditions for the optimal parametric control are rewritten using adjoint variables. From this representation, estimates for the adjoint variables at the multiple shooting nodes are derived. The estimates are proved to be consistent, in the sense that they converge toward the MPBVP solution if the parametrization is refined. An optimal aircraft maneuver demonstrates the transition from the direct to the indirect method.     

Allocation of dependent divisional resources

A resource allocation problem is considered with resources that are dependent in the sense that an allocation to an activity requires the application of several resources, except for certain activities which are divisional in the sense that an allocation to such an activity requires the use of only a single resource. Return and cost functions are assumed to be continuous and increasing, and the allocation variables are continuous. Conditions are given for the replacement of the continuous problem by an associated problem with discrete variables and a single constraint, and to a given degree of accuracy. The associated problem can be efficiently solved by dynamic programming. Certain divisional resource allocation problems with discrete variables and several linear constraints are shown to be equivalent to a discrete problem with a single constraint. A numerical example is given.     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.     

A heuristic algorithm for a chance constrained stochastic program

A chance constrained stochastic program is considered that arises from an application to college enrollments and in which the objective function is the expectation of a linear function of the random variables. When these random variables are independent and normally distributed with mean and variance that are linear in the decision variables, the deterministic equivalent of the problem is a nonconvex nonlinear knapsack problem. The optimal solution to this problem is characterized and a greedy-type heuristic algorithm that exploits this structure is employed. Computational results show that the algorithm performs well, especially when the normal random variables are approximations of binomial random variables.     

运筹学中若干线性目标规划和线性规划的人工智能-代数解法

运筹学中的线性目标规划和线性规划问题一直分别采用修正单纯形法和单纯形法求解.当变量稍多时计算还是有些繁琐、费时,最近作者通过研究发现,可应用人工智能-代数方法求得这两类问题的解,而且具有相当广泛的适用性.若干例题说明,本法的结果和传统方法的结果由于传统算法在计算中发生的错误,除少数例外大都是一致的.本文的一个 重要目的是希望和广大读者一起研究该方法是否具有通用性.     

An ideal column algorithm for integer programs with special ordered sets of variables

One of the most frequently occurring integer programming structures is the one which has special ordered sets of variables included in multiple choice constraints. For problems with this structure a set of ideal columns are defined from the linear programming relaxation of the integer program and a reduced integer program is formed by keeping only those columns within a specified distance from the ideal column. Conditions are established which guarantee when the optimal solution to the reduced problem is als optimal for the original problem. When these conditions are not satisfied, bounds on the optimal solution value are provided. Ideal columns are also used to establish weights for the special ordered set variables. This procedure has been implemented through a control program written by the authors for MPSX/370-MIP/370. Computational results are given.     

Multi-objective optimization over convex disjunctive feasible sets using reference points

In this paper we consider the Multiple Objective Optimization Problem (MOOP), where concave functions are to be maximized over a feasible set represented as a union of compact convex sets. To solve this problem we consider two auxiliary scalar optimization problems which use reference points. The first one contains only continuous variables, it has higher dimensionality, however it is convex. The second scalar problem is a mixed integer programming problem. The solutions of both scalar problems determine nondominated points. Some other properties of these problems are also discussed.     

A Method for Studying Singular Integral Equations

We examine a singular integral equation of the first kind on a bounded open set of an n-dimensional space. Open subsets with a common (contact) (n — 1)-dimensional piecewise smooth part of boundaries are selected. The underdetermined case is treated in which the unknown part of the integrand depends on 2n independent variables whereas a given integral depends only on n variables. In this situation we pose the problem of finding the contact part of the boundaries and prove unique solvability of the problem.     

Multiple Neutral Data Fitting

A method is proposed for estimating the relationship between a number of variables; this differs from regression where the emphasis is on predicting one of the variables. Regression assumes that only one of the variables has error or natural variability, whereas our technique does not make this assumption; instead, it treats all variables in the same way and produces models which are units invariant – this is important for ensuring physically meaningful relationships. It is thus superior to orthogonal regression in that it does not suffer from being scale-dependent. We show that the solution to the estimation problem is a unique and global optimum. For two variables the method has appeared under different names in various disciplines, with two Nobel laureates having published work on it.     

Solving air traffic conflict problems via local continuous optimization

This paper first introduces an original trajectory model using B-splines and a new semi-infinite programming formulation of the separation constraint involved in air traffic conflict problems. A new continuous optimization formulation of the tactical conflict-resolution problem is then proposed. It involves very few optimization variables in that one needs only one optimization variable to determine each aircraft trajectory. Encouraging numerical experiments show that this approach is viable on realistic test problems. Not only does one not need to rely on the traditional, discretized, combinatorial optimization approaches to this problem, but, moreover, local continuous optimization methods, which require relatively fewer iterations and thereby fewer costly function evaluations, are shown to improve the performance of the overall global optimization of this non-convex problem.     

Bayesian Sparse Group Selection

This article proposes a Bayesian approach for the sparse group selection problem in the regression model. In this problem, the variables are partitioned into different groups. It is assumed that only a small number of groups are active for explaining the response variable, and it is further assumed that within each active group only a small number of variables are active. We adopt a Bayesian hierarchical formulation, where each candidate group is associated with a binary variable indicating whether the group is active or not. Within each group, each candidate variable is also associated with a binary indicator, too. Thus, the sparse group selection problem can be solved by sampling from the posterior distribution of the two layers of indicator variables. We adopt a group-wise Gibbs sampler for posterior sampling. We demonstrate the proposed method by simulation studies as well as real examples. The simulation results show that the proposed method performs better than the sparse group Lasso in terms of selecting the active groups as well as identifying the active variables within the selected groups. Supplementary materials for this article are available online.     

The 0–1 knapsack problem with multiple choice constraints

In this paper we consider the 0–1 knapsack problem with multiple choice constraints appended. Such a problem may arise in a capital budgeting context where only one project may be selected from a particular group of projects. Thus the problem is to choose one project from each group such that the budgetary constraint is satisfied and the maximum return is realized. We formulate two branch and bound algorithms which use two different relaxations as the primary bounding relaxations. In addition, theoretical results are given for a simple reduction in the number of variables in the problem.     

A two-machine flow shop scheduling problem with controllable job processing times

The paper deals with a two-machine flow shop scheduling problem in which both the sequence of jobs and their processing times are decision variables. It is assumed that the cost of performing a job is a linear function of its processing time, and the schedule cost to be minimized is the total processing cost plus maximum completion time cost. In is shown that the decision form of this problem is NP-complete, even when the processing times on one machine only are controllable and all the processing cost units are identical. Two heuristic methods for solving the problem are proposed and their worst-case analysis is presented.     

A polyhedral study of the cardinality constrained knapsack problem

 A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems. Received: March 13, 2003 Published online: April 10, 2003 Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut     

Multiple-Load Truss Topology and Sizing Optimization: Some Properties of Minimax Compliance

This paper considers the mathematical properties of discrete or discretized mechanical structures under multiple loadings which are optimal w.r.t. maximal stiffness. We state a topology and/or sizing problem of maximum stiffness design in terms of element volumes and displacements. Multiple loads are handled by minimizing the maximum of compliance of all load cases, i.e., minimizing the maximal sum of displacements along an applied force. Generally, the problem considered may contain constraints on the design variables. This optimization problem is first reformulated in terms of only design variables. Elastic equilibrium is hidden in potential energy terms. It is shown that this transformed objective function is convex and continuous, including infinite values. We deduce that maximum stiffness structures are dependent continuously on the bounds of the element volumes as parameters. Consequently, solutions to sizing problems with small positive lower bounds on the design variables can be considered as good approximations of solutions to topology problems with zero lower bounds. This justifies heuristic approaches such as the well-known stress-rationing method for solving truss topology problems.     

A new sequential space-filling sampling strategy for elementary effects-based screening method

To predict or control the response of a complicated numerical model which involves a large number of input variables but is mainly affected by only a part of variables, it is necessary to screening those active variables. This paper proposes a new space-filling sampling strategy, which is used to screening the parameters based on the Morris’ elementary effect method. The beginning points of sampling trajectories are selected by using the maximin principle of Latin Hypercube Sampling method. The remaining points of trajectories are determined by using the one-factor-at-a-time design. Being different from other sampling strategies to determine the sequence of factors randomly in one-factor-at-a-time design, the proposed method formulates the sequence of factors by a deterministic algorithm, which sequentially maximizes the Euclidean distance among sampling trajectories. A new efficient algorithm is proposed to transform the distance maximization problem to a coordinate sorting problem, which saves computational cost much. After the elementary effects are computed using the sampling points, a detailed criterion is presented to select the active factors. Two mathematic examples and an engineering problem are used to validate the proposed sampling method, which demonstrates the priority in computational efficiency, space-filling performance, and screening efficiency.     

Two-stage stochastic linear programs with incomplete information on uncertainty

Two-stage stochastic linear programming is a classical model in operations research. The usual approach to this model requires detailed information on distribution of the random variables involved. In this paper, we only assume the availability of the first and second moments information of the random variables. By using duality of semi-infinite programming and adopting a linear decision rule, we show that a deterministic equivalence of the two-stage problem can be reformulated as a second-order cone optimization problem. Preliminary numerical experiments are presented to demonstrate the computational advantage of this approach.     

Farmland appraisal based on the analytic network process

This paper presents an application of the Analytic Network Process (ANP) to farmland appraisal. The purpose of this new methodology is to solve some of the drawbacks found in comparative and capitalisation methods, called classical appraisal methods, which cannot deal with contexts where only partial information is available and/or qualitative variables are used. The ANP is a method based on the Multiple Criteria Decision Analysis (MCDA). Previous works have already applied other MCDA techniques to the appraisal context, such as the Analytic Hierarchy Process (AHP), however they have not been able to handle all the complexities of many real world appraisal problems. The ANP provides a more accurate approach for modelling complex environment because it allows the general study of the quantitative and qualitative explanatory variables of the price and the incorporation of feedback and interdependence relationships among variables. The new proposed methodology has been applied to a case study of a farm located in Valencia (Spain) in order to demonstrate its goodness. Both quantitative and qualitative variables, such as the age of the trees, productivity or water quality, have been considered to assess the market value of the farm. Six farms from the same region have been selected as reference assets. The appraisal problem has been solved in three different ways in order to study the influence of each model on the value of the problem farm. In this study it has been proved that the more information is incorporated into the model, the higher accuracy of the solution. From the results of this work we can conclude that the approach proposed stands out as a good alternative to current farmland appraisal approaches, as it has proven to be useful when data are only partially available, qualitative variables are used and influences among the explanatory variables are present.