Efficient bounds on a branch and bound algorithm for graph colouration

By a proper colouring of a simple graph, we mean an assignment of colours to its vertices with adjacent vertices receiving different colours. Applications of this graph‐theoretic modelling are numerous, especially in the areas of scheduling and timetabling. We shall refer to a proper colouration that uses a smallest possible number of colours as a minimum (proper) colouration. This number for the graph is simply its chromatic number, the determination of which is well known to be a ‘hard’ problem. In this paper, from the computational point of view of actually constructing a colouration, we examine a simple coalescence/expansion procedure that bases on the branch and bound technique improved by efficient bounding conditions. They include various tightened fathoming criteria as well as complete subgraph determination. For the computer implementation, we also look at the issues of branching rules and the decomposition of solution tree. With these efforts, empirical results show that minimum colourations can be constructed for moderate size graphs, with ‘good’ solutions computed for problems of up to about forty vertices.     

Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices

We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.     

An exact method for computing the nadir values in multiple objective linear programming

In this paper we propose a new method to determine the exact nadir (minimum) criterion values over the efficient set in multiple objective linear programming (MOLP). The basic idea of the method is to determine, for each criterion, the region of the weight space associated with the efficient solutions that have a value in that criterion below the minimum already known (by default, the minimum in the payoff table). If this region is empty, the nadir value has been found. Otherwise, a new efficient solution is computed using a weight vector picked from the delimited region and a new iteration is performed. The method is able to find the nadir values in MOLP problems with any number of objective functions, although the computational effort increases significantly with the number of objectives. Computational experiments are described and discussed, comparing two slightly different versions of the method.     

Robust solutions of Linear Programming problems contaminated with uncertain data

Optimal solutions of Linear Programming problems may become severely infeasible if the nominal data is slightly perturbed. We demonstrate this phenomenon by studying 90 LPs from the well-known NETLIB collection. We then apply the Robust Optimization methodology (Ben-Tal and Nemirovski [1–3]; El Ghaoui et al. [5, 6]) to produce “robust” solutions of the above LPs which are in a sense immuned against uncertainty. Surprisingly, for the NETLIB problems these robust solutions nearly lose nothing in optimality. Received: July 1999 / Accepted: May 2000?Published online July 20, 2000     

On Maximizing Discrimination in Multiple Criteria Decision Making

We examine an LP/DEA-based technique for establishing an overall ranking of alternatives that are ranked on multiple criteria, which themselves are ranked. This two-stage process involves one LP in the first stage, and N LPs in the second stage to rank N alternatives. We find that the information from N + 1 LPs can be obtained by solving two LPs. In many cases, the solution of one LP, which can be done by inspection, is almost as informative as the two-stage procedure. We also indicate when the second stage would be redundant. If maximum technical discrimination between the alternatives is sought, we consider how this might be achieved by aggressive cross-evaluation via N LPs. We also show how to identify a subset of the alternatives that would be ranked in the first place under any ordering of the criteria, and thus play an important role in the evaluation procedure.     

Three enhancements for optimization-based bound tightening

Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17–19 % on average. Most importantly, more instances can be solved when using OBBT.     

可靠性网络中费用最小化问题的一种新的分枝定界算法

本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.     

《微积分中值定理间点的关系》注记

微分中值定理的结论是在开区间内至少存在一点使得某个等式成立,不妨把这样的点称为微分点;积分中值定理的结论也是在开区间内至少存在一点使得某个等式成立,不妨把这样的点称为积分点.本文讨论这两类点之间是否有关系,以及关系如何的问题,指出相关文献所提供的若干个结论中,有不只一个存在错误.     

Globally and Superlinearly Convergent QP-Free Algorithm for Nonlinear Constrained Optimization

A new, infeasible QP-free algorithm for nonlinear constrained optimization problems is proposed. The algorithm is based on a continuously differentiable exact penalty function and on active-set strategy. After a finite number of iterations, the algorithm requires only the solution of two linear systems at each iteration. We prove that the algorithm is globally convergent toward the KKT points and that, if the second-order sufficiency condition and the strict complementarity condition hold, then the rate of convergence is superlinear or even quadratic. Moreover, we incorporate two automatic adjustment rules for the choice of the penalty parameter and make use of an approximated direction as derivative of the merit function so that only first-order derivatives of the objective and constraint functions are used.     

The traveling salesman problem: A duality approach

In this study we formulate the dual of the traveling salesman problem, which extends in a natural way the dual problem of Held and Karp to the nonsymmetric case. The dual problem is solved by a subgradient optimization technique. A branch and bound scheme with stepped fathoming is then used to find optimal and suboptimal tours. Computational experience for the algorithm is presented.This author's work was partially supported by NSF Grant #GK-38337.     

Parametric mixed-integer 0–1 linear programming: The general case for a single parameter

Two algorithms for the general case of parametric mixed-integer linear programs (MILPs) are proposed. Parametric MILPs are considered in which a single parameter can simultaneously influence the objective function, the right-hand side and the matrix. The first algorithm is based on branch-and-bound on the integer variables, solving a parametric linear program (LP) at each node. The second algorithm is based on the optimality range of a qualitatively invariant solution, decomposing the parametric optimization problem into a series of regular MILPs, parametric LPs and regular mixed-integer nonlinear programs (MINLPs). The number of subproblems required for a particular instance is equal to the number of critical regions. For the parametric LPs an improvement of the well-known rational simplex algorithm is presented, that requires less consecutive operations on rational functions. Also, an alternative based on predictor–corrector continuation is proposed. Numerical results for a test set are discussed.     

一类凸优化的混合下降算法

邻近点算法(PPA)是一类求解凸优化问题的经典算法, 但往往需要精确求解隐式子问题,于是近似邻近点算法(APPA)在满足一定的近似规则下非精确求解PPA的子问题, 降低了求解难度. 本文利用近似规则的历史信息和随机数扩张预测校正步产生了两个方向, 通过随机数组合两个方向获得了一类凸优化的混合下降算法.在近似规则满足的情况下, 给出了混合下降算法的收敛性证明. 一系列的数值试验表明了混合下降算法的有效性和效率性.     

Selective association rule generation

Mining association rules is a popular and well researched method for discovering interesting relations between variables in large databases. A practical problem is that at medium to low support values often a large number of frequent itemsets and an even larger number of association rules are found in a database. A widely used approach is to gradually increase minimum support and minimum confidence or to filter the found rules using increasingly strict constraints on additional measures of interestingness until the set of rules found is reduced to a manageable size. In this paper we describe a different approach which is based on the idea to first define a set of “interesting” itemsets (e.g., by a mixture of mining and expert knowledge) and then, in a second step to selectively generate rules for only these itemsets. The main advantage of this approach over increasing thresholds or filtering rules is that the number of rules found is significantly reduced while at the same time it is not necessary to increase the support and confidence thresholds which might lead to missing important information in the database.     

Robust optimization – methodology and applications

Robust Optimization (RO) is a modeling methodology, combined with computational tools, to process optimization problems in which the data are uncertain and is only known to belong to some uncertainty set. The paper surveys the main results of RO as applied to uncertain linear, conic quadratic and semidefinite programming. For these cases, computationally tractable robust counterparts of uncertain problems are explicitly obtained, or good approximations of these counterparts are proposed, making RO a useful tool for real-world applications. We discuss some of these applications, specifically: antenna design, truss topology design and stability analysis/synthesis in uncertain dynamic systems. We also describe a case study of 90 LPs from the NETLIB collection. The study reveals that the feasibility properties of the usual solutions of real world LPs can be severely affected by small perturbations of the data and that the RO methodology can be successfully used to overcome this phenomenon. Received: May 24, 2000 / Accepted: September 12, 2001?Published online February 14, 2002     

Stable high-order quadrature rules with equidistant points

Newton-Cotes quadrature rules are based on polynomial interpolation in a set of equidistant points. They are very useful in applications where sampled function values are only available on a regular grid. Yet, these rules rapidly become unstable for high orders. In this paper we review two techniques to construct stable high-order quadrature rules using equidistant quadrature points. The stability follows from the fact that all coefficients are positive. This result can be achieved by allowing the number of quadrature points to be larger than the polynomial order of accuracy. The computed approximations then implicitly correspond to the integral of a least squares approximation of the integrand. We show how the underlying discrete least squares approximation can be optimised for the purpose of numerical integration.     

Bargaining with nonanonymous disagreement: Decomposable rules

We analyze bargaining situations where the agents’ payoffs from disagreement depend on who among them breaks down the negotiations. We model such problems as a superset of the standard domain of Nash (1950). We first show that this domain extension creates a very large number of new rules. In particular, decomposable rules (which are extensions of rules from the Nash domain) constitute a nowhere dense subset of all possible rules. For them, we analyze the process through which “good” properties of rules on the Nash domain extend to ours. We then enquire whether the counterparts of some well-known results on the Nash (1950) domain continue to hold for decomposable rules on our extended domain. We first show that an extension of the Kalai-Smorodinsky bargaining rule uniquely satisfies the Kalai and Smorodinsky (1975) properties. This uniqueness result, however, turns out to be an exception. We characterize the uncountably large classes of decomposable rules that survive the Nash (1950), Kalai (1977), and Thomson (1981) properties.     

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

Bargaining with nonanonymous disagreement: Decomposable rules

We analyze bargaining situations where the agents’ payoffs from disagreement depend on who among them breaks down the negotiations. We model such problems as a superset of the standard domain of Nash (1950). We first show that this domain extension creates a very large number of new rules. In particular, decomposable rules (which are extensions of rules from the Nash domain) constitute a nowhere dense subset of all possible rules. For them, we analyze the process through which “good” properties of rules on the Nash domain extend to ours. We then enquire whether the counterparts of some well-known results on the Nash (1950) domain continue to hold for decomposable rules on our extended domain. We first show that an extension of the Kalai–Smorodinsky bargaining rule uniquely satisfies the Kalai and Smorodinsky (1975) properties. This uniqueness result, however, turns out to be an exception. We characterize the uncountably large classes of decomposable rules that survive the Nash (1950), Kalai (1977), and Thomson (1981) properties.