LocalSolver 1.x: a black-box local-search solver for 0-1 programming

This paper introduces LocalSolver 1.x, a black-box local-search solver for general 0-1 programming. This software allows OR practitioners to focus on the modeling of the problem using a simple formalism, and then to defer its actual resolution to a solver based on efficient and reliable local-search techniques. Started in 2007, the goal of the LocalSolver project is to offer a model-and-run approach to combinatorial optimization problems which are out of reach of existing black-box tree-search solvers (integer or constraint programming). Having outlined the modeling formalism and the main technical features behind LocalSolver, its effectiveness is demonstrated through an extensive computational study. The version 1.1 of LocalSolver can be freely downloaded at and used for educational, research, or commercial purposes.     

Interactions between nonlinear programming and modeling systems

Modeling systems are very important for bringing mathematical programming software to nonexpert users, but few nonlinear programming algorithms are today linked to a modeling system. The paper discussed the advantages of linking modeling systems with nonlinear programming. Traditional algorithms can be linked using black-box function and derivatives evaluation routines for local optimization. Methods for generating this information are discussed. More sophisticated algorithms can get access to almost any type of information: interval evaluations and constraint restructuring for detailed preprocessing, second order information for sequential quadratic programming and interior point methods, and monotonicity and convex relaxations for global optimization. Some of the sophisticated information is available today; the rest can be generated on demand.     

A MIQCP formulation for B-spline constraints

This paper presents a mixed-integer quadratically constrained programming (MIQCP) formulation for B-spline constraints. The formulation can be used to obtain an exact MIQCP reformulation of any spline-constrained optimization problem problem, provided that the polynomial spline functions are continuous. This reformulation allows practitioners to use a general-purpose MIQCP solver, instead of a special-purpose spline solver, when solving B-spline constrained problems. B-splines are a powerful and widely used modeling tool, previously restricted from optimization due to lack of solver support. This contribution may encourage practitioners to use B-splines to model constraint functions. However, as the numerical study suggests, there is still a large gap between the solve times of the general-purpose solvers using the proposed formulation, and the special-purpose spline solver CENSO, the latter being significantly lower.     

A clone-based graphical modeler and mathematical model generator for optimal production planning in process industries

This paper outlines a visually interactive graphical modeling approach for process type production systems, with hidden generation of complex optimization models for production planning. The proposed system lets the users build a graphical model of the production system with one-to-one clones of its production units through its interactive visual interface, accepts production-specific data for its components, and finally, internally generates and solves its mathematical programming model without any interaction from the user. This “clone-based” modeling approach allows the continued use of optimization models with minimal mathematical programming understanding, as generation of mathematical model by clones is hidden and automatic, therefore maintenance-free: Updating graphical production system models is enough for renewing internal optimization models. The concept is demonstrated in this paper with a linear programming prototype developed for a petroleum refinery.     

A line search filter algorithm with inexact step computations for equality constrained optimization

In this paper, a new line search filter algorithm for equality constrained optimization is presented. The approach belongs to the class of inexact Newton-like methods. It can also be regarded as an inexact version of generic sequential quadratic programming (SQP) methods. The trial step is obtained by truncatedly solving the primal-dual system based on any robust and efficient linear system solver. Practical termination tests for the linear system solver are established to ensure global convergence. Preliminary numerical results demonstrate the approach is potentially useful.     

Constraint propagation,relational arithmetic in AI systems and mathematical programs

This paper explores the interrelationships between methods developed in mathematical programming to discover the structure of constraint (feasibility) sets and constraint propagation over networks used by some AI systems to perform inferences about quantities. It is shown that some constraint set problems in mathematical programming are equivalent to inferencing problems for constraint networks with interval labels. This makes the inference and query capabilities associated with AI systems that use logic programming, directly accessible to mathematical programming systems. On the other hand, traditional and newer methods which mathematical programming uses to obtain information about its associated feasibility set can be used to determine the propagation of constraints in a network of nodes of an AI system. When viewed from this point of view, AI problems can access additional mathematical programming analytical tools including new ways to incorporate qualitative data into constraint sets via interval and fuzzy arithmetic.This work was partially supported by the Industrial Consortium to Develop an Intelligent Mathematical Programming System — Amoco Oil Company, General Research Corporation, Ketron Management Science, Shell Oil Company, MathPro, and US West Advanced Technologies.     

An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming

This paper is concerned with nonlinear, semidefinite, and second-order cone programs. A general algorithm, which includes sequential quadratic programming and sequential quadratically constrained quadratic programming methods, is presented for solving these problems. In the particular case of standard nonlinear programs, the algorithm can be interpreted as a prox-regularization of the Solodov sequential quadratically constrained quadratic programming method presented in Mathematics of Operations Research (2004). For such type of methods, the main cost of computation amounts to solve a linear cone program for which efficient solvers are available. Usually, “global convergence results” for these methods require, as for the Solodov method, the boundedness of the primal sequence generated by the algorithm. The other purpose of this paper is to establish global convergence results without boundedness assumptions on any of the iterative sequences built by the algorithm.     

Is bilevel programming a special case of a mathematical program with complementarity constraints?

Bilevel programming problems are often reformulated using the Karush–Kuhn–Tucker conditions for the lower level problem resulting in a mathematical program with complementarity constraints(MPCC). Clearly, both problems are closely related. But the answer to the question posed is “No” even in the case when the lower level programming problem is a parametric convex optimization problem. This is not obvious and concerns local optimal solutions. We show that global optimal solutions of the MPCC correspond to global optimal solutions of the bilevel problem provided the lower-level problem satisfies the Slater’s constraint qualification. We also show by examples that this correspondence can fail if the Slater’s constraint qualification fails to hold at lower-level. When we consider the local solutions, the relationship between the bilevel problem and its corresponding MPCC is more complicated. We also demonstrate the issues relating to a local minimum through examples.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

A ring-mesh topology design problem for optical transport networks

This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method.     

Subspace-stabilized sequential quadratic programming

The stabilized sequential quadratic programming (SQP) method has nice local convergence properties: it possesses local superlinear convergence under very mild assumptions not including any constraint qualifications. However, any attempts to globalize convergence of this method indispensably face some principal difficulties concerned with intrinsic deficiencies of the steps produced by it when relatively far from solutions; specifically, it has a tendency to produce long sequences of short steps before entering the region where its superlinear convergence shows up. In this paper, we propose a modification of the stabilized SQP method, possessing better “semi-local” behavior, and hence, more suitable for the development of practical realizations. The key features of the new method are identification of the so-called degeneracy subspace and dual stabilization along this subspace only; thus the name “subspace-stabilized SQP”. We consider two versions of this method, their local convergence properties, as well as a practical procedure for approximation of the degeneracy subspace. Even though we do not consider here any specific algorithms with theoretically justified global convergence properties, subspace-stabilized SQP can be a relevant substitute for the stabilized SQP in such algorithms using the latter at the “local phase”. Some numerical results demonstrate that stabilization along the degeneracy subspace is indeed crucially important for success of dual stabilization methods.     

多变量、多约束连续或离散的非线性规划的一个通用算法

利用目标函数对约束函数关于设计变量的一阶微分或差分之比,给出了一个求解非线性规划的通用算法．不论变量和约束有多少,也不论变量是连续的还是离散的,这一算法都比较有效,尤其对离散非线性规划更有效．该方法是一种搜索法,勿需解任何数学方程,只需要计算函数值以及函数对变量的偏微分或差分值．许多数值例题和运筹学中一些经典问题,如1) 一、二维的背包问题;2) 一、二维资源分配问题;3) 复合系统工作可靠性问题;4) 机器负荷问题等,经用此法求解验证均较传统方法更有效和可靠．该方法的主要优点是:1) 不受问题的规模限制;2) 只要在可行域（集）内存在目标函数和约束函数及其一阶导数或差分的值,肯定可以搜索到最优的解,没有不收敛和不稳定的问题．     

Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently

Logic programming languages, such asProlog, allow a declarative specification of Constraint Satisfaction Problems (CSPs), freeing the user from specifying more or less complex control directives. However, the price to pay for such flexibility is a loss of efficiency, which makes Logic Programming inadequate to solve CSPs of even moderate size and complexity. To extend the range of applicability of logic programming, several improvements have been proposed. The use of heuristics is one such improvement. Although this usually forces the user to specify some form of control (thus abandoning the pure declarative nature of a logic program), these specifications can be made declarative by making use of some appropriate meta-predicates. Another extension to logic programming that improves its efficiency, is the active use of constraints, as done in the various formulations of constraint logic programming languages. In particular, the use of finite domains is quite adequate to implement look-ahead schemes to efficiently solve several types of CSPs. In this paper, we discuss the complementary nature of heuristics and look-ahead schemes and present a constraint logic programming framework that integrates both these techniques. Results obtained with a time-tabling problem executed on a prototype that implements such a framework are presented, and show that significant efficiency improvements can be achieved when compared with the separate use of the two techniques.     

SCIP: solving constraint integer programs

Constraint integer programming (CIP) is a novel paradigm which integrates constraint programming (CP), mixed integer programming (MIP), and satisfiability (SAT) modeling and solving techniques. In this paper we discuss the software framework and solver SCIP (Solving Constraint Integer Programs), which is free for academic and non-commercial use and can be downloaded in source code. This paper gives an overview of the main design concepts of SCIP and how it can be used to solve constraint integer programs. To illustrate the performance and flexibility of SCIP, we apply it to two different problem classes. First, we consider mixed integer programming and show by computational experiments that SCIP is almost competitive to specialized commercial MIP solvers, even though SCIP supports the more general constraint integer programming paradigm. We develop new ingredients that improve current MIP solving technology. As a second application, we employ SCIP to solve chip design verification problems as they arise in the logic design of integrated circuits. This application goes far beyond traditional MIP solving, as it includes several highly non-linear constraints, which can be handled nicely within the constraint integer programming framework. We show anecdotally how the different solving techniques from MIP, CP, and SAT work together inside SCIP to deal with such constraint classes. Finally, experimental results show that our approach outperforms current state-of-the-art techniques for proving the validity of properties on circuits containing arithmetic.      

Quasistatic evolution in non-associative plasticity revisited

The mathematical treatment of evolutionary non-associative elasto-plasticity is still in its infancy. In particular, all existence results thus far rely on a spatially mollified stress admissibility constraint. Further, the evolution is formulated in a rescaled time from which it is very difficult to infer any useful information on the “real” time evolution. We propose a causal spatio-temporal mollification of the stress admissibility constraint that, while no more far-fetched than a purely spatial one, produces a more elegant and complete evolution for such models, and this in the “real” time variable.     

A new constraint test-case generator and the importance of hybrid optimizers

In the past decade, significant progress has been made in understanding problem complexity of discrete constraint problems. In contrast, little similar work has been done for constraint problems in the continuous domain. In this paper, we study the complexity of typical methods for non-linear constraint problems and present hybrid solvers with improved performance. To facilitate the empirical study, we propose a new test-case generator for generating non-linear constraint satisfaction problems (CSPs) and constrained optimization problems (COPs). The optimization methods tested include a sequential quadratic programming (SQP) method, a penalty method with a fixed penalty function, a penalty method with a sequence of penalty functions, and an augmented Lagrangian method. For hybrid solvers, we focus on the form that combines two or more optimization methods in sequence. In the experiments, we apply these methods to solve a series of continuous constraint problems with increasing constraint-to-variable ratios. The test problems include artificial benchmark problems from the test-case generator and problems derived from controlling a hyper-redundant modular manipulator. We obtain novel results on complexity phase transition phenomena of the various methods. Specifically, for constraint satisfaction problems, the SQP method is the best on weakly constrained problems, whereas the augmented Lagrangian method is the best on highly constrained ones. Although the static penalty method performs poorly by itself, by combining it with the SQP method, we show a hybrid solver that is significantly better than any of the individual methods on problems with moderate to large constraint-to-variable ratios. For constrained optimization problems, the hybrid solver obtains much better solutions than SQP, while spending comparable amount of time. In addition, the hybrid solver is flexible and can achieve good results on time-bounded applications by setting parameters according to the time limits.     

Combining metaheuristics with mathematical programming, constraint programming and machine learning

During the last years, interest on hybrid metaheuristics has risen considerably in the field of optimization and machine learning. The best results found for many optimization problems in science and industry are obtained by hybrid optimization algorithms. Combinations of optimization tools such as metaheuristics, mathematical programming, constraint programming and machine learning, have provided very efficient optimization algorithms. Four different types of combinations are considered in this paper: (i) Combining metaheuristics with complementary metaheuristics. (ii) Combining metaheuristics with exact methods from mathematical programming approaches which are mostly used in the operations research community. (iii) Combining metaheuristics with constraint programming approaches developed in the artificial intelligence community. (iv) Combining metaheuristics with machine learning and data mining techniques.     

Efficient Management of Multiple Sets to Extract Complex Structures from Mathematical Programs

Most of the applied models written with an algebraic modeling language involve simultaneously several dimensions such as materials, location, time or uncertainty. The information about dimensions available in the algebraic formulation is usually sufficient to retrieve different block structures from mathematical programs. These structured problems can then be solved by adequate solution techniques. To illustrate this idea we focus on stochastic programming problems with recourse. Taking into account both time and uncertainty dimensions of these problems, we are able to retrieve different customized structures in their constraint matrices. We applied the Structure Exploiting Tool to retrieve the structure from models built with the GAMS modeling language. The underlying mathematical programs are solved with the decomposition algorithm that applies interior point methods. The optimization algorithm is run in a sequential and in a parallel computing environment.     

Enhancing set constraint solvers with lexicographic bounds

Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems, such as bin-packing, set partitioning, circuit and combinatorial design. In this paper we present and evaluate a new means towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems with a particular attention to the challenging symmetrical set problems often cast as Combinatorial Design Problems (CDPs). While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality restrictions applied to the variable, and allow for active symmetry breaking using ordering constraints. Our contribution includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical evaluation on benchmark CDPs.     

Differential inclusions and Young measures involving prescribed Jacobians

In elasticity theory, one naturally requires that the Jacobian determinant of the deformation is positive or even a-priori prescribed (e.g. for incompressibility). However, such strongly non-linear and non-convex constraints are difficult to deal with in mathematical models. This short note, which is based on joint work with K. Koumatos and E. Wiedemann, presents various recent results on how this constraint can be manipulated in subcritical Sobolev spaces, where the integrability exponent is less than the dimension. In particular, we give a characterization theorem for Young measures under this side constraint. This is in the spirit of the celebrated Kinderlehrer–Pedregal Theorem and based on convex integration and “geometry” in matrix space. Finally, applications to approximation in Sobolev spaces and to the failure of lower semicontinuity for certain integral functionals with “realistic” growth conditions are given. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)