A Declarative Modeling Framework that Integrates Solution Methods

Constraint programming offers modeling features and solution methods that are unavailable in mathematical programming but are often flexible and efficient for scheduling and other combinatorial problems. Yet mathematical programming is well suited to declarative modeling languages and is more efficient for some important problem classes. This raises this issue as to whether the two approaches can be combined in a declarative modeling framework. This paper proposes a general declarative modeling system in which the conditional structure of the constraints shows how to integrate any “checker” and any special-purpose “solver”. In particular this integrates constraint programming and optimization methods, because the checker can consist of constraint propagation methods, and the solver can be a linear or nonlinear programming routine.     

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.     

The min-Knapsack problem with compactness constraints and applications in statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper, we introduce an extension of the min-Knapsack problem with additional “compactness constraints” (mKPC), stating that selected items cannot lie too far apart. This extension has applications in statistics, including in algorithms for change-point detection in time series. We propose three solution methods for the mKPC. The first two methods use the same Mixed-Integer Programming (MIP) formulation but with two different approaches: passing the complete model with a quadratic number of constraints to a black-box MIP solver or dynamically separating the constraints using a branch-and-cut algorithm. Numerical experiments highlight the advantages of this dynamic separation. The third approach is a dynamic programming labelling algorithm. Finally, we focus on the particular case of the unit-cost mKPC (1c-mKPC), which has a specific interpretation in the context of the statistical applications mentioned above. We prove that the 1c-mKPC is solvable in polynomial time with a different ad-hoc dynamic programming algorithm. Experimental results show that this algorithm vastly outperforms both generic approaches for the mKPC and a simple greedy heuristic from the literature.     

Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph Partitioning

Performance-driven physical layout design is becoming increasingly important for both high speed integrated circuits and printed circuit boards. This paper studies the problem of assigning wire segments into two layers so as to minimize the number of vias, while taking into account performance constraints such as layer preference and circuit timing. We show that using the Elmore delay model, three timing problems in synchronous digital circuits—the long path problem, the short path problem and the time skew problem—can be formulated as a set of linear inequalities. We use the model of signed hypergraph to represent two-layer routings and formulate the performance-driven optimum layer assignment problem as the path-constrained maximum balance problem in a signed hypergraph. Two solution methods are developed and implemented. First, an integer linear programming formulation is derived for finding exact solutions. Second, a local-search heuristic for hypergraph partitioning is extended to cope with path-inequality constraints. Experimental results on a set of layer-assignment benchmarks demonstrated that the path-constrained local-search heuristic achieves optimum or near-optimum solutions with several orders of magnitude faster than the integer linear programming approach.     

A MIP-based framework and its application on a lot sizing problem with setup carryover

In this paper we present a framework to tackle mixed integer programming problems based upon a “constrained” black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to the original MIP formulation. Such corridors, or neighborhoods, are then explored, possibly to optimality, with a standard MIP solver. An iterative approach in the spirit of a hill climbing scheme is thus used to explore subportions of the solution space. While the exploration of the corridor relies on a standard MIP solver, the way in which such corridors are built around the incumbent solutions is influenced by a set of factors, such as the distance metric adopted, or the type of method used to explore the neighborhood. The proposed framework has been tested on a challenging variation of the lot sizing problem, the multi-level lot sizing problem with setups and carryovers. When tested on 1920 benchmark instances of such problem, the algorithm was able to solve to near optimality every instance of the benchmark library and, on the most challenging instances, was able to find high quality solutions very early in the search process. The algorithm was effective, in terms of solution quality as well as computational time, when compared with a commercial MIP solver and the best algorithm from the literature.     

DrAmpl: a meta solver for optimization problem analysis

Optimization problems modeled in the AMPL modeling language (Fourer et al., in AMPL: a modeling language for mathematical programming, 2002) may be examined by a set of tools found in the AMPL Solver Library (Gay, in Hooking your solver to AMPL, 1997). DrAmpl is a meta solver which, by use of the AMPL Solver Library, dissects such optimization problems, obtains statistics on their data, is able to symbolically prove or numerically disprove convexity of the functions involved and provides aid in the decision for an appropriate solver. A problem is associated with a number of relevant solvers available on the NEOS Server for Optimization (Czyzyk et al., in IEEE J Comput Sci Eng 5:68–75, 1998) by means of a relational database. We describe the need for such a tool, the design of DrAmpl and some of its consequences, and keep in mind that a similar tool could be developed for other algebraic modeling languages.     

Heuristic solution approaches for the maximum minsum dispersion problem

The Maximum Minsum Dispersion Problem (Max-Minsum DP) is a strongly NP-Hard problem that belongs to the family of equitable dispersion problems. When dealing with dispersion, the operations research literature has focused on optimizing efficiency-based objectives while neglecting, for the most part, measures of equity. The most common efficiency-based functions are the sum of the inter-element distances or the minimum inter-element distance. Equitable dispersion problems, on the other hand, attempt to address the balance between efficiency and equity when selecting a subset of elements from a larger set. The objective of the Max-Minsum DP is to maximize the minimum aggregate dispersion among the chosen elements. We develop tabu search and GRASP solution procedures for this problem and compare them against the best in the literature. We also apply LocalSolver, a commercially available black-box optimizer, to compare our results. Our computational experiments show that we are able to establish new benchmarks in the solution of the Max-Minsum DP.     

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.     

Proximity search for 0-1 mixed-integer convex programming

In this paper we investigate the effects of replacing the objective function of a 0-1 mixed-integer convex program (MIP) with a “proximity” one, with the aim of using a black-box solver as a refinement heuristic. Our starting observation is that enumerative MIP methods naturally tend to explore a neighborhood around the solution of a relaxation. A better heuristic performance can however be expected by searching a neighborhood of an integer solution—a result that we obtain by just modifying the objective function of the problem at hand. The relationship of this approach with primal integer methods is also addressed. Promising computational results on different proof-of-concept implementations are presented, suggesting that proximity search can be quite effective in quickly refining a given feasible solution. This is particularly true when a sequence of similar MIPs has to be solved as, e.g., in a column-generation setting.     

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.     

Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

A black-box scatter search for optimization problems with integer variables

The goal of this work is the development of a black-box solver based on the scatter search methodology. In particular, we seek a solver capable of obtaining high quality outcomes to optimization problems for which solutions are represented as a vector of integer values. We refer to these problems as integer optimization problems. We assume that the decision variables are bounded and that there may be constraints that require that the black-box evaluator is called in order to know whether they are satisfied. Problems of this type are common in operational research areas of applications such as telecommunications, project management, engineering design and the like.Our experimental testing includes 171 instances within four classes of problems taken from the literature. The experiments compare the performance of the proposed method with both the best context-specific procedures designed for each class of problem as well as context-independent commercial software. The experiments show that the proposed solution method competes well against commercial software and that can be competitive with specialized procedures in some problem classes.     

A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature.     

A fix-and-optimize matheuristic for university timetabling

University course timetabling covers the task of assigning rooms and time periods to courses while ensuring a minimum violation of soft constraints that define the quality of the timetable. These soft constraints can have attributes that make it difficult for mixed-integer programming solvers to find good solutions fast enough to be used in a practical setting. Therefore, metaheuristics have dominated this area despite the fact that mixed-integer programming solvers have improved tremendously over the last decade. This paper presents a matheuristic where the MIP-solver is guided to find good feasible solutions faster. This makes the matheuristic applicable in practical settings, where mixed-integer programming solvers do not perform well. To the best of our knowledge this is the first matheuristic presented for the University Course Timetabling problem. The matheuristic works as a large neighborhood search where the MIP solver is used to explore a part of the solution space in each iteration. The matheuristic uses problem specific knowledge to fix a number of variables and create smaller problems for the solver to work on, and thereby iteratively improves the solution. Thus we are able to solve very large instances and retrieve good solutions within reasonable time limits. The presented framework is easily extendable due to the flexibility of modeling with MIPs; new constraints and objectives can be added without the need to alter the algorithm itself. At the same time, the matheuristic will benefit from future improvements of MIP solvers. The matheuristic is benchmarked on instances from the literature and the 2nd International Timetabling Competition (ITC2007). Our algorithm gives better solutions than running a state-of-the-art MIP solver directly on the model, especially on larger and more constrained instances. Compared to the winner of ITC2007, the matheuristic performs better. However, the most recent state-of-the-art metaheuristics outperform the matheuristic.     

A mixed integer programming formulation for the 1-maximin problem

In this paper, I present a mixed integer programming (MIP) formulation for the 1-maximin problem with rectilinear distance. The problem mainly appears in facility location while trying to locate an undesirable facility. The rectilinear distance is quite commonly used in the location literature. Our numerical experiments show that one can solve reasonably large location problems using a standard MIP solver. We also provide a linear programming formulation that helps find an upper bound on the objective function value of the 1-maximin problem with any norm when extreme points of the feasible region are known. We discuss various extension alternatives for the MIP formulation.     

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.     

Parallel multi-frontal solver for p adaptive finite element modeling of multi-physics computational problems

The paper presents a parallel direct solver for multi-physics problems. The solver is dedicated for solving problems resulting from adaptive finite element method computations. The concept of finite element is actually replaced by the concept of the node. The computational mesh consists of several nodes, related to element vertices, edges, faces and interiors. The ordering of unknowns in the solver is performed on the level of nodes. The concept of the node can be efficiently utilized in order to recognize unknowns that can be eliminated at a given node of the elimination tree. The solver is tested on the exemplary three-dimensional multi-physics problem involving the computations of the linear acoustics coupled with linear elasticity. The three-dimensional tetrahedral mesh generation and the solver algorithm are modeled by using graph grammar formalism. The execution time and the memory usage of the solver are compared with the MUMPS solver.     

Integer programming to schedule a hierarchical workforce with variable demands

We consider a hierarchical workforce in which a higher qualified worker can substitute for a lower qualified one, but not vice versa. Daily labor requirements within a week may vary, but each worker must receive n off-days in the week. This problem has been considered by Hung (R. Hung, Eur. J. Oper. Res. 78(1) (1994) 49–57), who discusses a necessary and sufficient condition for a labor mix to be feasible and presents a simple one-pass method that frequently gives the least cost labor mix. We show in this paper that the integer programming approach is well suited for solving this problem: the definition of the integer programming model is simple, its implementation is immediate by using, for example, the Mathematical programming language (MPL) and the integer programming solver XA, the computation times are low (generally a few seconds on a small microcomputer) and finally the powerful of the integer programming approach allows us to extend the model in two interesting directions.     

Tightening concise linear reformulations of 0-1 cubic programs

A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach.     

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.