Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

Test-Based Variable Selection via Cross-Validation

Abstract

Test-based variable selection algorithms in regression often are based on sequential comparison of test statistics to cutoff values. A predetermined a level typically is used to determine the cutoffs based on an assumed probability distribution for the test statistic. For example, backward elimination or forward stepwise involve comparisons of test statistics to prespecified t or F cutoffs in Gaussian linear regression, while a likelihood ratio. Wald, or score statistic, is typically used with standard normal or chi square cutoffs in nonlinear settings. Although such algorithms enjoy widespread use, their statistical properties are not well understood, either theoretically or empirically. Two inherent problems with these methods are that (1) as in classical hypothesis testing, the value of α is arbitrary, while (2) unlike hypothesis testing, there is no simple analog of type I error rate corresponding to application of the entire algorithm to a data set. In this article we propose a new method, backward elimination via cross-validation (BECV), for test-based variable selection in regression. It is implemented by first finding the empirical p value α*, which minimizes a cross-validation estimate of squared prediction error, then selecting the model by running backward elimination on the entire data set using α* as the nominal p value for each test. We present results of an extensive computer simulation to evaluate BECV and compare its performance to standard backward elimination and forward stepwise selection.     

Variable Selection in Regression via Repeated Data Splitting

Abstract

A new algorithm—backward elimination via repeated data splitting (BERDS)—is proposed for variable selection in regression. Initially, the data are partitioned into two sets {E, V}, and an exhaustive backward elimination (BE) is performed in E. For each p value cutoff α used in BE, the corresponding fitted model from E is validated in V by computing the sum of squared deviations of observed from predicted values. This is repeated m times, and the α minimizing the sum of the m sums of squares is used as the cutoff in a final BE on the entire data set. BERDS is a modification of the algorithm BECV proposed by Thall, Simon, and Grier (1992). An extensive simulation study shows that, compared to BECV, BERDS has a smaller model error and higher probabilities of excluding noise variables, of selecting each of several uncorrelated true predictors, and of selecting exactly one of two or three highly correlated true predictors. BERDS is also superior to standard BE with cutoffs .05 or .10, and this superiority increases with the number of noise variables in the data and the degree of correlation among true predictors. An application is provided for illustration.     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation

Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.     

Determining and Depicting Relationships Among Components in High-Dimensional Variable Selection

Many modern treatments of high-dimensional datasets involve reducing the initial collection of features to a much smaller set, from which a predictive model may be built. However, strong relationships between the remaining variables can limit the parsimony or even the predictive performance of such a model. We propose a semi-automatic approach using generalized correlation to detect and quantify these relationships, as well as exploring ways to represent this information graphically. The method can detect both symmetric and asymmetric relationships, as well as nonlinear patterns. Its utility is demonstrated on a range of real and simulated datasets. Supplemental material for performing the real-data analyses in this article is available online.     

一类投资项目评估与选择问题的数学模型

章给出在模糊环境下求解带有平衡条件的投资项目评估与选择问题的数学模型，用模糊来描述决策人对项目的主观评价以及多个评价因素的综合，用模糊整数规划模型描述了各种不同门类利益间的平均。     

多种分布下选择后变量显著性分析及其在CEPS数据中的应用

在使用变量选择方法选出模型后,如何评价模型中变量系数的显著性是统计学重点关注的前沿问题之一.文章从适应性Lasso变量选择方法的选择结果出发,在考虑实践中误差分布多样性的前提下,基于选择事件构造了模型保留变量系数的条件检验统计量,并给出了该统计量的一致收敛性质的证明过程.模拟研究显示,在多种误差分布下所提方法均可进一步优化变量选择结果,有较强的实用价值.应用此方法对CEPS学生数据进行了实证分析,最终选取了学生认知能力等10个变量作为影响中学生成绩的主要因素,为相关研究提供了有益的参考.     

Combined MCDA–IP Approach for Project Selection in the Electricity Market

The European policy target of substantially increasing the share of renewable energy in electricity generation, in combination with national subsidization support schemes, has strongly motivated private investors towards this business sector. In Greece, this interest is particularly apparent in the case of wind energy exploitation, due to a favourable legislative framework and the important wind potential available in several Greek regions. In such endowed regions, a very high number of applications were submitted to the competent authority, most of which compete for the same most attractive (windy) sites. The selection among these applications is a multicriteria problem that has been solved with the support of a Decision-Aid tool combining the multicriteria classification method ELECTRE-TRI with Integer Linear Programming. The developed approach takes into account both, the performances of the applications to the evaluation criteria, as well as a number of technical and policy constraints.     

A note on “A new local and global optimization method for mixed integer quadratic programming problems” by G.Q. Li et al.

In this comment, we preset a minor mistake in typing which is made in “A new local and global optimization method for mixed integer quadratic programming problems” by G.Q. Li et al.     

Checking solvability of systems of interval linear equations and inequalities via mixed integer programming

This paper deals with the problems of checking strong solvability and feasibility of linear interval equations, checking weak solvability of linear interval equations and inequalities, and finding control solutions of linear interval equations. These problems are known to be NP$\mathit{NP}$-hard. We use some recently developed characterizations in combination with classical arguments to show that these problems can be equivalently stated as optimization tasks and provide the corresponding linear mixed 0–1 programming formulations.     

Global solution of optimization problems with signomial parts

In this paper a new approach for the global solution of nonconvex MINLP (Mixed Integer NonLinear Programming) problems that contain signomial (generalized geometric) expressions is proposed and illustrated. By applying different variable transformation techniques and a discretization scheme a lower bounding convex MINLP problem can be derived. The convexified MINLP problem can be solved with standard methods. The key element in this approach is that all transformations are applied termwise. In this way all convex parts of the problem are left unaffected by the transformations. The method is illustrated by four example problems.     

A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem

This paper presents a preprocessing procedure for the 0–1 multidimensional knapsack problem. First, a non-increasing sequence of upper bounds is generated by solving LP-relaxations. Then, a non-decreasing sequence of lower bounds is built using dynamic programming. The comparison of the two sequences allows either to prove that the best feasible solution obtained is optimal, or to fix a subset of variables to their optimal values. In addition, a heuristic solution is obtained. Computational experiments with a set of large-scale instances show the efficiency of our reduction scheme. Particularly, it is shown that our approach allows to reduce the CPU time of a leading commercial software.     

Decomposition and Linearization for 0-1 Quadratic Programming

This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.     

Integrated design and operation of remnant inventory supply chains under uncertainty

We consider the simultaneous design and operation of remnant inventory supply chains. Remnant inventory is generated when demand for various lengths of a product may be satisfied by existing inventory, or by cutting a large piece into smaller pieces. We formulate our problem as a two-stage stochastic mixed-integer program. In solving our stochastic program, we enhance the standard L-shaped method in two ways. Our computational experiments demonstrate that these enhancements are effective, dramatically reducing the solution time for large instances.     

Harvest planning in the Brazilian sugar cane industry via mixed integer programming

This work addresses harvest planning problems that arise in the production of sugar and alcohol from sugar cane in Brazil. The planning is performed for two planning horizons, tactical and operational planning, such that the total sugar content in the harvested cane is maximized. The tactical planning comprises the entire harvest season that averages seven months. The operational planning considers a horizon from seven to thirty days. Both problems are solved by mixed integer programming. The tactical planning is well handled. The model for the operational planning extends the one for the tactical planning and is presented in detail. Valid inequalities are introduced and three techniques are proposed to speed up finding quality solutions. These include pre-processing by grouping and filtering the distance matrix between fields, hot starting with construction heuristic solutions, and dividing and sequentially solving the resulting MIP program. Experiments are run over a set of real world and artificial instances. A case study illustrates the benefits of the proposed planning.     

Reducing the number of variables in integer quadratic programming problem

In this paper, a new variable reduction technique is presented for general integer quadratic programming problem (GP), under which some variables of (GP) can be fixed at zero without sacrificing optimality. A sufficient condition and a necessary condition for the identification of dominated terms are provided. By comparing the given data of the problem and the upper bound of the variables, if they meet certain conditions, some variables can be fixed at zero. We report a computational study to demonstrate the efficacy of the proposed technique in solving general integer quadratic programming problems. Furthermore, we discuss separable integer quadratic programming problems in a simpler and clearer form.     

A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs

We study a conditional logic approach for tightening the continuous relaxation of a mixed 0-1 linear program. The procedure first constructs quadratic inequalities by computing pairwise products of constraints, and then surrogates modified such inequalities to produce valid linear restrictions. Strength is achieved by adjusting the coefficients on the quadratic restrictions. The approach is a unifying framework for published coefficient adjustment methods, and generalizes the process of sequential lifting. We give illustrative examples and discuss various extensions, including the use of more complex conditional logic constructs that compute and surrogate polynomial expressions, and the application to general integer programs. Partially supported by NSF grant #DMI-0423415 and ONR grant #N00014-97-1-0784.     

A new method to solve the fully connected Reserve Network Design Problem

In selecting sites for conservation purposes connectivity of habitat is important for allowing species to move freely within a protected area. The aim of the Reserve Network Design Problem is to choose a network of contiguous sites which maximises some conservation objective subject to various constraints. The problem has been solved using both heuristic and exact methods. Heuristic methods can handle much larger problems than exact methods but cannot guarantee an optimal solution. Improvements in both computer power and optimisation algorithms have increased the attractiveness of exact methods. The aim of this work is to formulate an improved algorithm for solving the Reserve Network Design Problem.