Cover and Pack Inequalities for (Mixed) Integer Programming

We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the 0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to give a unified presentation of the inequalities based on covers and packs and highlight the connections among them. The focus of the paper is on recent research on the use of superadditive functions for the analysis of knapsack polyhedra. We also present some new results on integer knapsacks. In particular, we give an integer version of the cover inequalities and describe a necessary and sufficient facet condition for them. This condition generalizes the well-known facet condition of minimality of covers for 0-1 knapsacks. The author is supported, in part, by NSF Grants 0070127 and 0218265.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.     

一般整数规划中有效不等式的同步升维

有效不等式在整数规划的定界研究中具有重要的意义.研究了一般整数规划问题的有效不等式的升维方法,引入超加性函数给出同步升维的条件,并给出有效不等式的同步升维的具体方法,算例表明本文提出的方法是有效的.     

Incremental and encoding formulations for Mixed Integer Programming

The standard way to represent a choice between n$n$ alternatives in Mixed Integer Programming is through n$n$ binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones.     

混合整数二次规划问题的全局最优性条件

本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解.     

Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

Local protein threading by Mixed Integer Programming

During the last decade, significant progress has been made in solving the Protein Threading Problem (PTP). However, all previous approaches to PTP only perform global sequence-structure alignment. This obvious limitation is in clear contrast with the “world of sequences”, where local sequence-sequence alignments are widely used to find functionally important regions in families of proteins. This paper presents a novel approach to PTP which allows to align a part of a protein structure onto a protein sequence in order to detect local similarities. We show experimentally that such local sequence-structure alignments improve the quality of the prediction. Our approach is based on Mixed Integer Programming (MIP) which has been shown to be very successful in this domain. We describe five MIP models for local sequence-structure alignments, compare and analyze their performances by using ILOG CPLEX 10 solver on a benchmark of proteins.     

A Novel Mixed Integer Linear Programming Model for Clustering Relational Networks

Integer programming models for clustering have applications in diverse fields addressing many problems such as market segmentation and location of facilities. Integer programming models are flexible in expressing objectives subject to some special constraints of the clustering problem. They are also important for guiding clustering algorithms that are capable of handling high-dimensional data. Here, we present a novel mixed integer linear programming model especially for clustering relational networks, which have important applications in social sciences and bioinformatics. Our model is applied to several social network data sets to demonstrate its ability to detect natural network structures.     

混合整数规划求解多联票据印刷过程中的生产调度问题

多联票据的印刷过程包括排版、单联印刷和多联配页与装订三个过程。该过程是柔性的流水生产线与装配混合的生产系统。本文研究了该系统中的票据印刷生产调度问题,目标是最小化所有产品的最大完成时间（Makespan）。该问题到目前为止还没有人研究,本文首先建立了该问题的混合整数规划模型,然后提出了该模型的求解方法,并给出了该问题的下界。最后的量化示例和算例试验表明本文的模型是有效的。     

Deleting Outliers in Robust Regression with Mixed Integer Programming

In robust regression we often have to decide how many are the unusual observations, which should be removed from the sample in order to obtain better fitting for the rest of the observations. Generally, we use the basic principle of LTS, which is to fit the majority of the data, identifying as outliers those points that cause the biggest damage to the robust fit. However, in the LTS regression method the choice of default values for high break down-point affects seriously the efficiency of the estimator. In the proposed approach we introduce penalty cost for discarding an outlier, consequently, the best fit for the majority of the data is obtained by discarding only catastrophic observations. This penalty cost is based on robust design weights and high break down-point residual scale taken from the LTS estimator. The robust estimation is obtained by solving a convex quadratic mixed integer programming problem, where in the objective function the sum of the squared residuals and penalties for discarding observations is minimized. The proposed mathematical programming formula is suitable for small-sample data. Moreover, we conduct a simulation study to compare other robust estimators with our approach in terms of their efficiency and robustness.     

Integrating nonlinear branch-and-bound and outer approximation for convex Mixed Integer Nonlinear Programming

In this paper, we present a new hybrid algorithm for convex Mixed Integer Nonlinear Programming (MINLP). The proposed hybrid algorithm is an improved version of the classical nonlinear branch-and-bound (BB) procedure, where the enhancements are obtained with the application of the outer approximation algorithm on some nodes of the enumeration tree. The two methods are combined in such a way that each one collaborates to the convergence of the other. Computational experiments with benchmark instances of the MINLP problem show the good performance of the proposed algorithm, which is compared to the outer approximation algorithm, the nonlinear BB algorithm and the hybrid algorithm implemented in the solver Bonmin.     

On General Mixed Quasivariational Inequalities

In this paper, we suggest and analyze several iterative methods for solving general mixed quasivariational inequalities by using the technique of updating the solution and the auxiliary principle. It is shown that the convergence of these methods requires either the pseudomonotonicity or the partially relaxed strong monotonicity of the operator. Proofs of convergence is very simple. Our new methods differ from the existing methods for solving various classes of variational inequalities and related optimization problems. Various special cases are also discussed.     

On General Mixed Variational Inequalities

In this paper, we introduce and consider a new class of mixed variational inequalities, which is called the general mixed variational inequality. Using the resolvent operator technique, we establish the equivalence between the general mixed variational inequalities and the fixed-point problems as well as resolvent equations. We use this alternative equivalent formulation to suggest and analyze some iterative methods for solving the general mixed variational inequalities. We study the convergence criteria of the suggested iterative methods under suitable conditions. Using the resolvent operator technique, we also consider the resolvent dynamical systems associated with the general mixed variational inequalities. We show that the trajectory of the dynamical system converges globally exponentially to the unique solution of the general mixed variational inequalities. Our methods of proofs are very simple as compared with others’ techniques. Results proved in this paper may be viewed as a refinement and important generalizations of the previous known results.     

Valid Inequalities for the Lasdon-Terjung Production Model

We consider a very simple integer program involving production of a single item and start-up costs for the standard machines first studied by Lasdon and Terjung. Solving directly as an integer program leads to prohibitively large branch and bound trees. Here, we show how using a simple family of valid inequalities and a heuristic procedure to choose one of these inequalities as a cut, it is possible to reduce substantially the size of the tree, and in several cases to eliminate the need for branch and bound. The valid inequalities used are all simple Gomory cuts. However, they are derived from the initial problem formulation rather than from the optimal linear programming tableau.     

0-1非线性混合整数规划的罚函数解法

本文中我们对一类0-1非线性混合整数规划的解法进行了探讨,通过罚函数把有约束问题化为相应的无约束问题,我们证明了可通过求解一个无约束非线性规划问题得到原问题的ε近似极小解,数值试验表明算法是有效的.     

Mixed Integer Programming to Schedule a Single-Shift Workforce under Annualized Hours

Nowadays flexibility is a strategic concept for firms. Indeed workload has to follow, as close as possible, the development of demand throughout the year. However, firms cannot engage and dismiss employees according to production requirements. Thus, workforce scheduling becomes a delicate task. In this paper, four mixed integer programming models are developed to solve the workforce schedule problem for a single-shift. The annualized hour scenario is considered with respect to a set of Swiss legal constrains. Furthermore, the minimal required workforce is guaranteed and it is assumed that each employee is able to perform each task within the team. All employees are full-time workers.     

Logical Processing for Integer Programming

This paper reviews tools which have great potential for reducing the difficulty of solving IP (and also MIP) problems, if well implemented in solvers. Recent experiments with Branch and Bound solvers, in connection with “Short Start Features”, have shown that implementations need and can still be improved. Concepts which are likely to be specially important for (0,1) MIP are pointed out.     

A Mixed Integer Linear Programming model for simultaneous design and scheduling of flowshop plants

Models representing batch plants, especially flowshop facilities where all the products require the same processing sequence, have received much attention in the last decades. In particular, plant design and production scheduling have been addressed as disconnected problems due to the tremendous combinatory complexity associated to their simultaneous optimization. This paper develops a model for both design and scheduling of flowshop batch plants considering mixed product campaign and parallel unit duplication. Thus, a realistic formulation is attained, where industrial and commercial aspects are jointly taken into account. The proposed approach is formulated as a Mixed Integer Linear Programming model that determines the number of units per stages, unit and batch sizes and batch sequencing in each unit in order to fulfill the demand requirements at minimum investment cost. A set of novel constraints is proposed where the number of batches of each product in the campaign is an optimization variable. The approach performance is evaluated through several numerical examples.     

Hyperspheric Integer Programming

This paper develops an efficient method for finding the optimal solution to linear mathematical programs on 0–1 variables. It is shown that the lattice (0–1) points satisfying some linear constraint of dimension n can equally be represented by those lying in a hypersphere of the same dimension. The lattice points satisfying two linear constraints can be represented by a hypersphere which contains the intersection of the hyperspheres of the two constraints. The method for finding the optimal solution consists of enumerating lattice points which are close to the center of the hypersphere corresponding to the constraints. As soon as a better value of the objective function has been found, than some lower bound, we find a new hypersphere which contains the lattice points of the constraints at which the objective function remains higher than the best known value. We continue in this manner until we have at some stage enumerated all lattice points within a given hypersphere and found none which give a better value.