An effective branch-and-bound algorithm for convex quadratic integer programming

We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problems with box constraints. The main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.     

Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

We consider two (0, 1)-linear programming formulations of the graph (vertex-) coloring problem, in which variables are associated with stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in which constraints express that two stable sets cannot have a common vertex, and large stable sets are preferred in the objective function. We identify facets with small coefficients for the polytopes associated with both formulations. We show by computational experiments that both formulations are about equally efficient when used in a branch-and-price algorithm. Next we propose some preprocessing, and show that it can substantially speed up the algorithm, if it is applied at each node of the enumeration tree. Finally we describe a cutting plane procedure for the set covering formulation, which often reduces the size of the enumeration tree.     

A decomposed branch-and-price procedure for integrating demand planning in personnel staffing problems

The personnel staffing problem calculates the required workforce size and is determined by constructing a baseline personnel roster that assigns personnel members to duties in order to cover certain staffing requirements. In this research, we incorporate the planning of the duty demand in the staff scheduling problem in order to lower the staffing costs. More specifically, the demand originates from a project scheduling problem with discrete time/resource trade-offs, which embodies additional flexibility as activities can be executed in different modes. In order to tackle this integrated problem, we propose a decomposed branch-and-price procedure. A tight lower and upper bound are calculated using a problem formulation that models the project scheduling constraints and the time-related resource scheduling constraints implicitly in the decision variables. Based upon these bounds, the strategic problem is decomposed into multiple tactical subproblems with a fixed workforce size and an optimal solution is searched for each subproblem via branch-and-price. Fixing the workforce size in a subproblem facilitates the definition of resource capacity cuts, which limit the set of eligible project schedules, decreasing the size of the branching tree. In addition, in order to find the optimal integer solution, we propose a specific search strategy based upon the lower bound and dedicated rules to branch upon the workload generated by a project schedule. The computational results show that applying the proposed search space decomposition and the inclusion of resource capacity cuts lead to a well-performing procedure outperforming different other heuristic and exact methodologies.     

SICOpt: Solution Approach for Nonlinear Integer Stochastic Programming Problems

We propose a novel solution approach for the class of two-stage nonlinear integer stochastic programming models. These problems are characterized by large scale dimensions, as the number of constraints and variables depend on the number of realizations (scenarios) used to capture the underlying distributions of the random data. In addition, the integrality constraints on the decision variables make the solution process even much more difficult preventing the application of general purpose solvers. The proposed solution approach integrates the branch-and-bound framework with the interior point method. The main advantage of this choice is the effective exploitation of the specific structure exhibited by the different subproblems at each node of the search tree. A specifically designed warm start procedure and an early branching technique improve the overall efficiency. Our contribution is well founded from a theoretical point of view and is characterized by good computational efficiency, without any loss in terms of effectiveness. Some preliminary numerical results, obtained by solving a challenging real-life problem, prove the robustness and the efficiency of the proposed approach.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

THE NESTED TOTAL LEAST SQUARES PROBLEM:FORMULATION,SOLUTIONS AND PERTURBATION ANALYSIS

In this paper, we propose the nested totoal least squatres problem (NTLS), which is an extension of the equality constrained least squares problem (LSE). The formulation of the NTLS problem is given and the solution set of the NTLS problem is obtained. The least squares residuals and the minimal norm correction matrices of the NTLS solution are provided and a perturbation analysis of the NTLS solutions is given.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

Experimental Results on Using General Disjunctions in Branch-and-Bound for General-Integer Linear Programs

Typical implementations of branch-and-bound for integer linear programs choose to branch on single variables. In this paper we explore the use of general disjunctions for branching when solving linear programs with general-integer variables. We give computational results that show that the size of the enumeration tree can be greatly reduced by branching on such disjunctions rather than on single variables.     

An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

A projected semismooth Newton method for problems of calibrating least squares covariance matrix

In this paper we propose a projected semismooth Newton method to solve the problem of calibrating least squares covariance matrix with equality and inequality constraints. The method is globally and quadratically convergent with proper assumptions. The numerical results show that the proposed method is efficient and comparable with existing methods.     

A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints

The paper deals with a problem motivated by survivability issues in multilayer IP-over-WDM telecommunication networks. Given a set of traffic demands for which we know a survivable routing in the IP layer, our purpose is to look for the corresponding survivable topology in the WDM layer. The problem amounts to Multiple Steiner TSPs with order constraints. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We also present new valid inequalities and discuss their facial aspect. Based on this, we devise a Branch-and-cut algorithm and present preliminary computational results.     

Algorithms for the computation of functionals defined on the solution of a discrete ill-posed problem

We study a linear, discrete ill-posed problem, by which we mean a very ill-conditioned linear least squares problem. In particular we consider the case when one is primarily interested in computing a functional defined on the solution rather than the solution itself. In order to alleviate the ill-conditioning we require the norm of the solution to be smaller than a given constant. Thus we are lead to minimizing a linear functional subject to two quadratic constraints. We study existence and uniqueness for this problem and show that it is essentially equivalent to a least squares problem with a linear and a quadratic constraint, which is easier to handle computationally. Efficient algorithms are suggested for this problem.     

A fast algorithm for the rectilinear distance location problem

In this paper, we consider the rectilinear distance location problem with box constraints (RDLPBC) and we show that RDLPBC can be reduced to the rectilinear distance location problem (RDLP). A necessary and sufficient condition of optimality is provided for RDLP. A fast algorithm is presented for finding the optimal solution set of RDLP. Global convergence of the method is proved by a necessary and sufficient condition. The new proposed method is provably more efficient in finding the optimal solution set. Computational experiments highlight the magnitude of the theoretical efficiency.     

A New Formulation for Spanning Trees

Spanning trees are fundamental structures in graph theory. Furthermore, computing them is a central part in many relevant algorithms, used in either practical or theoretical applications. The classical Minimum Spanning Tree problem is solvable in polynomial time but almost all of its variants are NP-Hard. In this paper, a novel polynomial size mixed integer linear programming formulation is introduced for spanning trees. This formulation is based on a new characterization we propose for acyclic graphs. Preliminary computational results show that this formulation is capable of solving small instances of the diameter constrained minimum spanning tree problem. It should be possible to strengthen the formulation to tackle larger instances of that problem. Additionally, our spanning tree formulation may prove to be a more effective model for some related applications.     

四元数矩阵方程(AXB,CXD)=(E,F)的最小范数最小二乘Hermitian解

提出了研究四元数矩阵方程(AXB, CXD)=(E, F)的最小范数最小二乘Hermitian解的一个有效方法.首先应用四元数矩阵的实表示矩阵以及实表示矩阵的特殊结构,把四元数矩阵方程转化为相应的实矩阵方程,然后求出四元数矩阵方程(AXB, CXD)=(E, F)的最小二乘Hermitian解集,进而得到其最小范数最小二乘Hermitian解.所得到的结果只涉及实矩阵,相应的算法只涉及实运算,因此非常有效.最后的两个数值例子也说明了这一点.