A strong flow-based formulation for the shortest path problem in digraphs with negative cycles

In this paper, we are interested in the shortest path problem between two specified vertices in digraphs containing negative cycles. We study two integer linear formulations and their linear relaxations. A first formulation, close in spirit to a classical formulation of the traveling salesman problem, requires an exponential number of constraints. We study a second formulation that requires a polynomial number of constraints and, as confirmed by computational experiments, its linear relaxation is significantly sharper. From the second formulation we propose a family of linear relaxations with fewer variables than the classical linear one.     

Binary partitioning, perceptual grouping, and restoration with semidefinite programming

We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer vision and apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints. The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convex programming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwise interactions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range of problems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along with extensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiority of our approach to relaxations based on spectral graph theory and prove performance bounds.     

Calculating the best dual bound for problems with multiple Lagrangian relaxations

There are often many ways in which a given problem can be relaxed in a Lagrangian fashion. It is not obvious a priori, which relaxation produces the best bound. Moreover, a bound may appear to be the best for a certain data set, while being among the worst for another problem instance. We consider here an optimization problem over the set of Lagrangian relaxations with the objective to indicate the relaxation producing the best dual bound. An iterative technique to solve this problem is proposed based on constraints generation scheme. The approach is illustrated by a computational study for a class of the two-stage capacitated facility location problem.     

Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem

This paper addresses the multicommodity capacitated fixed-charge network design problem with nonbifurcated flows and hop constraints. We present and compare mathematical programming formulations for this problem and we study different relaxations: Lagrangean relaxations, linear programming relaxations, and partial relaxations of the integrality constraints. In particular, we show that the Lagrangean bound obtained by relaxing the flow conservation equations is tighter than the linear programming relaxation bound. We present computational results on a large set of randomly generated instances.     

Efficient and accurate image based camera registration

A technique for efficient and accurate camera registration based on stereo image analysis is presented. Initially, few correspondences are estimated with high accuracy using a probabilistic relaxation technique. Accuracy is achieved by considering the continuous approximations of selected image areas using second order polynomials and a relaxation rule defined according to the likelihood that estimates obey stereoscopic constraints. The extrinsic camera parameters are then obtained using a novel efficient and robust approach derived from the classic eight point algorithm. Efficiency is achieved by solving a parametric linear optimization problem rather than a nonlinear one as more conventional methods attempt to do. Robustness is obtained by applying two novel strategies: normalization of the initial data via a simple but efficient diagonal scaling approach, and regularization of the underlying linear parametric optimization problem using meaningful constraints. The performance of the presented methods is assessed in several computer experiments using natural video data.     

Formulations and relaxations for a multi-echelon capacitated location–distribution problem

We consider a multi-echelon location–distribution problem arising from an actual application in fast delivery service. We present and compare two formulations for this problem: an arc-based model and a path-based model. We show that the linear programming (LP) relaxation of the path-based model provides a better bound than the LP relaxation of the arc-based model. We also compare the so-called binary relaxations of the models, which are obtained by relaxing the integrality constraints for the general integer variables, but not for the 0–1 variables. We show that the binary relaxations of the two models always provide the same bound, but that the path-based binary relaxation appears preferable from a computational point of view, since it can be reformulated as an equivalent simple plant location problem (SPLP), for which several efficient algorithms exist. We also show that the LP relaxation of this SPLP reformulation provides a better bound than the LP relaxation of the path-based model.     

Cyclic preference scheduling of nurses using a Lagrangian-based heuristic

This paper addresses the problem of developing cyclic schedules for nurses while taking into account the quality of individual rosters. In this context, quality is gauged by the absence of certain undesirable shift patterns. The problem is formulated as an integer program (IP) and then decomposed using Lagrangian relaxation. Two approaches were explored, the first based on the relaxation of the preference constraints and the second based on the relaxation of the demand constraints. A theoretical examination of the first approach indicated that it was not likely to yield good bounds. The second approach showed more promise and was subsequently used to develop a solution methodology that combined subgradient optimization, the bundle method, heuristics, and variable fixing. After the Lagrangian dual problem was solved, though, there was no obvious way to perform branch and bound when a duality gap existed between the lower bound and the best objective function value provided by an IP-based feasibility heuristic. This led to the introduction of a variable fixing scheme to speed convergence. The full algorithm was tested on data provided by a medium-size U.S. hospital. Computational results showed that in most cases, problem instances with up to 100 nurses and 20 rotational profiles could be solved to near-optimality in less than 20 min.     

Using relaxations to improve search in distributed constraint optimisation

Densely connected distributed constraint optimisation problems (DisCOP) can be difficult to solve optimally, but finding good lower bounds on constraint costs can help to speed up search. We show how good lower bounds can be found by solving relaxed problems obtained by removing inter-agent constraints. We present modifications to the Adopt DisCOP algorithm that allow an arbitrary number of relaxations to be performed prior to solving the original problem. We identify useful relaxations based on the solving structure used by Adopt, and demonstrate that when these relaxations are incorporated as part of the search it can lead to significant performance improvements. In particular, where agents have significant local constraint costs, we achieve over an order of magnitude reduction in messages exchanged between agents. Finally, we identify cases where such relaxation techniques produce less consistent benefits.     

Increasing Constraint Propagation by Redundant Modeling: an Experience Report

This paper describes our experience with a simple modeling and programming approach for increasing the amount of constraint propagation in the constraint solving process. The idea, although similar to redundant constraints, is based on the concept of redundant modeling. We introduce the notions of CSP model and model redundancy, and show how mutually redundant models can be combined and connected using channeling constraints. The combined model contains the mutually redundant models as sub-models. Channeling constraints allow the sub-models to cooperate during constraint solving by propagating constraints freely amongst the sub-models. This extra level of pruning and propagation activities becomes the source of execution speedup. real-life nurse rostering system. We perform two case studies to evaluate the effectiveness and efficiency of our method. The first case study is based on the simple and well-known n-queens problem, while the second case study applies our method in the design and construction of a real-life nurse rostering system. Experimental results provide empirical evidence in line with our prediction.     

An exact solution for vehicle routing problems with semi-hard resource constraints

This paper presents an exact solution procedure for a vehicle routing problem with semi-hard resource constraints where each resource requirement can be relaxed to a pre-fixed extent at a predefined cost. This model is particularly useful for a supply chain coordination when a given number of vehicles cannot feasibly serve all the customers without relaxing some constraints.It is different from VRP with soft time windows in that the violation is restricted to a certain upper bound, the penalty cost is flat, and the number of relaxations allowed has an upper bound.We develop an exact approach to solve the problem. We use the branch cut and price procedure to solve the problem modeling the pricing problem as an elementary shortest path problem with semi hard resource constraints. The modeling of the subproblem provides a tight lower bound to reduce the computation time. We solve this subproblem using a label setting algorithm, in which we form the labels in a compact way to facilitate incorporation of the resources requirement relaxation information into it, develop extension rules that generate labels with possible relaxations, and develop dominance criteria that reduce the computation time. The lower bound is improved by applying the subset-row inequalities.     

Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound

We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization.     

Adaptive segmentation of noisy and textured images

An image segmentation algorithm is described which is based on the integration of signal model parameter estimates and maximum a posteriori labelling. The parameter estimation is based on either a maximum likelihood-based method for a quadric signal model or a maximum pseudo-likelihood based method for a Gauss-Markov signal model. The first case is applicable to standard grey-level image segmentation as well as segmentation of shaded 3D surfaces, while the second case is applicable to texture segmentation. A key aspect of the algorithm is the incorporation of a coarse to fine processing strategy which limits the search for the optimum labelling at any one resolution to a subset of labellings which are consistent with the optimum labelling at the previous coarser resolution. Consistency is in terms of a prior label model which specifies the conditional probability of a given label in terms of the labelling at the previous level of resolution. It is shown how such an approach leads to a simple relaxation procedure based on local pyramid node computations. An extension of the algorithm is also described which performs accurate inter-region boundary placement using a step-wise refinement procedure based on a simple adaptive filter. The problem of automatic determination of the number of regions is also addressed. It is shown how a simple agglomerative clustering idea, again based on pyramid node computations, can effectively solve this problem.     

An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.     

Scheduling of manufacturing systems using the Lagrangian relaxationtechnique

The practical solutions for three manufacturing scheduling problems are examined. As each problem is formulated, constraints are added or modified to reflect increasing real world complexity. The first problem considers scheduling single-operation jobs on identical machines. The second problem is concerned with scheduling multiple-operation jobs with simple fork/join precedence constraints on identical machines. The third problem is the job shop problem in which multiple-operation jobs with general precedence constraints are scheduled on multiple machine types Langrangian relaxation is used to decompose each of the scheduling problems into job- or operation-level subproblems. The subproblems are easier to solve than the original problem and have intuitive appeal. This technique results in algorithms which generate near-optimal schedules efficiently, while giving a lower bound on the optimal cost. In resolving the scheduling problem from one time instant to the next, the Lagrange multipliers from the last schedule can be used to initialize the multipliers, further reducing the computation time     

Energy-efficient joint path-following for attitude-fixed space manipulators with bounds on completion time and motor voltage/current

This paper investigates the minimum-energy joint path-following problem for space manipulators whose base attitude is stabilized by reaction wheels. In the problem, manipulator joint path is specified for rest-to-rest motion and constraints are imposed as the upper bound on both motion completion time and the voltage/current limits of DC motors in manipulator joints and reaction wheels. We suggest a simple two-stage algorithm to address this problem. The algorithm first tries to find a global optimal solution by solving a relaxed convex problem. If the convex relaxation is not successful, then the algorithm solves subproblems iteratively to find a suboptimal solution. Since both problems are formulated as second-order cone programming (SOCP) form, they can be solved efficiently using dedicated SOCP solvers. The effectiveness of the proposed method is verified by numerical experiments.     

New control allocation algorithms in fixed point framework for overactuated systems with actuator saturation

In this paper, two control allocation algorithms have been proposed for overactuated systems. The algorithms are developed by formulating constrained control allocation problem into an equivalent fixed point framework. The first algorithm follows sequential solving method while the other one involves a zero finding technique by the Newton method. In order to consider limiting constraints, the saturation function has been taken into account that leads to a nonsmooth zero finding problem and the proposed method guarantees superlinear convergence. The second algorithm is easy to implement and faster than the algorithm developed based on the sequential solving technique. To demonstrate the effectiveness of the proposed algorithms, a detail simulation study has been carried out, in which one example considers both the actuator rate and amplitude constraints.     

One-dimensional relaxations and LP bounds for orthogonal packing

We consider the feasibility problem in d -dimensional orthogonal packing ( d 2), called the Orthogonal Packing Problem (OPP): given a set of d -dimensional rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. We review two kinds of one-dimensional (1D) relaxations of OPP. The first kind is non-preemptive cumulative-resource scheduling, equivalently 1D contiguous stock cutting. The second kind is simple (preemptive) 1D stock cutting. In three and more dimensions we distinguish the so-called bar and slice preemptive relaxations of OPP. We review some models of these problems and compare the strength of their LP relaxations with regard to a certain OPP instance, theoretically and numerically. Both the theory and computational results in 2D and 3D show the advantage of the bar relaxation. We also compare the LP bounds with the commonly used volume bounds from dual-feasible functions. Moreover, we test the so-called probing (temporary fixing) of intersection variables of OPP with the aim to strengthen the relaxations.     

Tight Relaxation of Quadratic Matching

Establishing point correspondences between shapes is extremely challenging as it involves both finding sets of semantically persistent feature points, as well as their combinatorial matching. We focus on the latter and consider the Quadratic Assignment Matching (QAM) model. We suggest a novel convex relaxation for this NP‐hard problem that builds upon a rank‐one reformulation of the problem in a higher dimension, followed by relaxation into a semidefinite program (SDP). Our method is shown to be a certain hybrid of the popular spectral and doubly‐stochastic relaxations of QAM and in particular we prove that it is tighter than both. Experimental evaluation shows that the proposed relaxation is extremely tight: in the majority of our experiments it achieved the certified global optimum solution for the problem, while other relaxations tend to produce sub‐optimal solutions. This, however, comes at the price of solving an SDP in a higher dimension. Our approach is further generalized to the problem of Consistent Collection Matching (CCM), where we solve the QAM on a collection of shapes while simultaneously incorporating a global consistency constraint. Lastly, we demonstrate an application to metric learning of collections of shapes.     

Scheduling to maximize customer satisfaction: A project for the shad valley program

This paper describes a project that was done for the Shad Valley Program, where it was required to assign students to seminars so as to maximize the satisfaction of the students with their assignments. We begin by describing the problem, its inputs and constraints. Two models are proposed to determine optimal assignments. The first model is based on the Capacitated Transportation Problem and a network formulation is proposed to solve it. The second model is a two phase model whose first phase involves solving a Bottleneck Capacitated Transportation Problem and the second phase solving a Capacitated Transportation Problem. A simple search algorithm is proposed that solves the second model. Implementation of these models is described and the results obtained are discussed. Extensions to the two models are also proposed.     

Recursive central rounding for mixed integer programs

We introduce a new rounding heuristic for mixed integer programs. Starting from a fractional solution, the new approach is based on recursively fixing a subset of the discrete variables while using the analytic center to re-center the remaining ones. The proposed rounding approach can be used independently or integrated with other heuristics. We demonstrate both setups by first using the proposed approach to round the optimal solution of the linear programming relaxation. We then integrate the proposed rounding heuristic with the feasibility pump by replacing the original simple rounding function of the feasibility pump. We conduct computational testing on mixed integer problems from MIPLIB and CORAL and on mixed integer quadratic problems from MIQPLIB. The proposed algorithm is computationally efficient and provides good quality feasible solutions.