A norm-relaxed method of feasible directions for finely discretized problems from semi-infinite programming

In this paper, a class of finely discretized Semi-Infinite Programming (SIP) problems is discussed. Combining the idea of the norm-relaxed Method of Feasible Directions (MFD) and the technique of updating discretization index set, we present a new algorithm for solving the Discretized Semi-Infinite (DSI) problems from SIP. At each iteration, the iteration point is feasible for the discretized problem and an improved search direction is computed by solving only one direction finding subproblem, i.e., a quadratic program, and some appropriate constraints are chosen to reduce the computational cost. A high-order correction direction can be obtained by solving another quadratic programming subproblem with only equality constraints. Under weak conditions such as Mangasarian–Fromovitz Constraint Qualification (MFCQ), the proposed algorithm possesses weak global convergence. Moreover, the superlinear convergence is obtained under Linearly Independent Constraint Qualification (LICQ) and other assumptions. In the end, some elementary numerical experiments are reported.     

Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics

Constraint Programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems. We introduce a Constraint Programming model for vehicle routing, and a system for integrating Constraint Programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.     

Augmented self-concordant barriers and nonlinear optimization problems with finite complexity

In this paper we study special barrier functions for convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center of the augmented barrier, a problem that has some interesting applications. We show that for some special classes of quadratic forms and some convex cones, the computation of the analytic center requires an amount of operations independent of the particular data set. We argue that these problems form a class that is endowed with a property which we call finite polynomial complexity. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Ministers Office, Science Policy Programming.This author acknowledges the support of the grant 1214-057093-99 of the Swiss National Science Foundation.     

Decision diagrams for solving traveling salesman problems with pickup and delivery in real time

The Traveling Salesman Problem with Pickup and Delivery seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width Decision Diagrams in a branch-and-bound with and without Assignment Problem inference duals as a primal heuristic for finding good solutions within strict time budgets. We show these diagrams can be more effective than similarly structured hybrid Constraint Programming techniques for real-time decision making.     

Existence, uniqueness, and convergence of the regularized primal-dual central path

In a recent work [J. Castro, J. Cuesta, Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming, in press (doi:10.1007/s10107-010-0341-2)] the authors improved one of the most efficient interior-point approaches for some classes of block-angular problems. This was achieved by adding a quadratic regularization to the logarithmic barrier. This regularized barrier was shown to be self-concordant, thus fitting the general structural optimization interior-point framework. In practice, however, most codes implement primal-dual path-following algorithms. This short paper shows that the primal-dual regularized central path is well defined, i.e., it exists, it is unique, and it converges to a strictly complementary primal-dual solution.     

Comparing constraint programming and mathematical programming approaches to discrete optimisation—the change problem

This paper is aimed at researchers and practitioners in Operational Research who are interested in the new field of Constraint Programming/Constraint Logic Programming. Due to differing terminology and problem representation they might have found it difficult to access the field. The paper focuses on discrete optimisation problems. The first part lists frequently used terms in Constraint Programming (CP), contrasting them with their counterparts in Mathematical Programming (MP). The second part explains some of the most important concepts and techniques in more detail by comparing the CP and MP implementations of a small example problem, the ‘Change Problem’. It includes an overview of the respective results. In conclusion a more generalised comparison of CP and MP techniques is given.     

Analysis of a smoothing method for symmetric conic linear programming

This paper proposes a smoothing method for symmetric conic linear programming (SCLP). We first characterize the central path conditions for SCLP problems with the help of Chen-Harker-Kanzow-Smale smoothing function. A smoothing-type algorithm is constructed based on this characterization and the global convergence and locally quadratic convergence for the proposed algorithm are demonstrated.     

A General Approach to the Physician Rostering Problem

This paper presents a hybridization of a Constraint Programming (CP) model and search techniques with Local Search (LS) and some ideas borrowed from Genetic Algorithms (GA). The context is the physician rostering problem, whose instances can vary greatly and for which almost no general tool has been developed. It is hoped that the combination of the three techniques will lead to an algorithm that has sufficient flexibility to solve most instances with a small amount of customization. To achieve this goal we also introduce Generic constraints: these constraints are used to model several types of ergonomic constraints that are found amongst physician rostering problems.     

A Goal Programming model of the reference point method

Real-life decision problems are usually so complex they cannot be modeled with a single objective function, thus creating a need for clear and efficient techniques of handling multiple criteria to support the decision process. The most commonly used technique is Goal Programming. It is clear and appealing, but in the case of multiobjective optimization problems strongly criticized due to its noncompliance with the efficiency (Pareto-optimality) principle. On the other hand, the reference point method, although using similar control parameters as Goal Programming, always generates efficient solutions. In this paper, we show how the reference point method can be modeled within the Goal Programming methodology. It allows us to simplify implementations of the reference point method as well as shows how Goal Programming with relaxation of some traditional assumptions can be extended to a multiobjective optimization technique meeting the efficiency principle.     

Feasibility pump 2.0

Finding a feasible solution of a given mixed-integer programming (MIP) model is a very important ${\mathcal{NP}}$ -complete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a diving-like procedure based on rounding and constraint propagation—a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowing-down the method and with a significantly better quality of the feasible solutions found.     

On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems

Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditioned iterative techniques to solve the KKT system arising at each iteration of a Potential Reduction method for convex Quadratic Programming. We consider the augmented system approach and analyze the behaviour of the Constraint Preconditioner with the Conjugate Gradient algorithm. Comparisons with a direct solution of the augmented system and with MOSEK show the effectiveness of the iterative approach on large-scale sparse problems. Work partially supported by the Italian MIUR FIRB Project Large Scale Nonlinear Optimization, grant no. RBNE01WBBB.     

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.     

Cane Railway Scheduling via Constraint Logic Programming: Labelling Order and Constraints in a Real-Life Application

In Australia, cane transport is the largest unit cost in the manufacturing of raw sugar, making up around 35% of the total manufacturing costs. Producing efficient schedules for the cane railways can result in significant cost savings. This paper presents a study using Constraint Logic Programming (CLP) to solve the cane transport scheduling problem. Tailored heuristic labelling order and constraints strategies are proposed and encouraging results of application to several test problems and one real-life case are presented. The preliminary results demonstrate that CLP can be used as an effective tool for solving the cane transport scheduling problem, with a potential decrease in development costs of the scheduling system. It can also be used as an efficient tool for rescheduling tasks which the existing cane transport scheduling system cannot perform well.     

Constraint Programming-based Column Generation

This paper surveys recent applications and advances of the Constraint Programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by Constraint Programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using Constraint Programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the Constraint Programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.     

Solving scheduling problems from high-level models

This is the summary of the author??s PhD thesis supervised by Yves Deville and Pascal Van Hentenryck, and defended on 25 May 2010?at the Université catholique de Louvain in Louvain-la-Neuve. The thesis is written in English and is available from the author, or downloadable from http://becool.info.ucl.ac.be/files2/thesis-monette.pdf. This work is about the gap between high-level modelling of scheduling problems and its efficient resolution. We propose to automatically classify models of scheduling problems, and to apply an appropriate search algorithm. Thanks to the strong separation between model and search, we propose also a simple way to create hybrid algorithms. A second part of the thesis deals with Constraint Programming approaches for two scheduling problems: The one-machine non-preemptive problem and the Just-In-Time Job-Shop problem. All parts are accompanied by experimental results showing their practicality.     

An extended algorithm for separated continuous linear programs

Separated continuous linear programs (SCLP) are a class of continuous linear programs which, among other things, can serve as a useful model for dynamic network problems where storage is permitted at the nodes. Recent work on SCLP has produced a detailed duality theory, conditions under which an optimal solution exists with a finite number of breakpoints, a purification algorithm, as well as a convergent algorithm for solving SCLP under certain assumptions on the problem data. This paper combines much of this work to develop a possible approach for solving a wider range of SCLP problems, namely those with fairly general costs. The techniques required to implement the algorithm are no more than standard (finite-dimensional) linear programming and line searching, and the resulting algorithm is simplex-like in nature. We conclude the paper with the numerical results obtained by using a simple implementation of the algorithm to solve a small problem. Received: May 1994 / Accepted: March 2002?Published online June 25, 2002     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

Searching for Mutually Orthogonal Latin Squares via integer and constraint programming

This paper applies algorithms integrating Integer Programming (IP) and Constraint Programming (CP) to the Mutually Orthogonal Latin Squares (MOLS) problem. We investigate the behaviour of these algorithms against traditional IP and CP schemes. Computational results are obtained with respect to various aspects of the algorithms, using instances of the 2 MOLS and 3 MOLS problems. The benefits of integrating IP with CP on this feasibility problem are clearly exhibited, especially in large problem instances.     

Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach

In this paper, we introduce a new variant of the Vehicle Routing Problem (VRP), namely the Two-Stage Vehicle Routing Problem with Arc Time Windows (TS_VRP_ATWs) which generally emerges from both military and civilian transportation. The TS_VRP_ATW is defined as finding the vehicle routes in such a way that each arc of the routes is available only during a predefined time interval with the objective of overall cost minimization. We propose a Mixed Integer Programming (MIP) formulation and a heuristic approach based on Memetic Algorithm (MA) to solve the TS_VRP_ATW. The qualities of both solution approaches are measured by using the test problems in the literature. Experimental results show that the proposed MIP formulation provides the optimal solutions for the test problems with 25 and 50 nodes, and some test problems with 100 nodes. Results also show that the proposed MA is promising quality solutions in a short computation time.     

Existence and duality theory for separated continuous linear programs

This paper surveys the recent developments in the theoretical study of separated continuous linear programs (SCLP). This problem serves as a useful model for various dynamic network problems where storage is permitted at the nodes. We demonstrate this by modelling some hypothetical problems of water distribution, transportation and telecommunications. The theoretical developments we present for SCLP fall into two main topics. The first of these is the existence of optimal solutions of various forms. These results culminate in one guaranteeing the existence of a piecewise analytic optimal solution, that is, having a finite number of breakpoints. The second topic we discuss is duality. Under this heading we develop a theory that closely resembles that for finite-dimensional linear programming. For instance, we define complementary slackness and give conditions under which there exist complementary slack primal and dual optimal solutions. Throughout the paper we observe that the main theorems are sufficiently general to include any reasonable practical problems