A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.     

On the resolution and optimization of a system of fuzzy relational equations with sup-T composition

This paper provides a thorough investigation on the resolution of a finite system of fuzzy relational equations with sup-T composition, where T is a continuous triangular norm. When such a system is consistent, although we know that the solution set can be characterized by a maximum solution and finitely many minimal solutions, it is still a challenging task to find all minimal solutions in an efficient manner. Using the representation theorem of continuous triangular norms, we show that the systems of sup-T equations can be divided into two categories depending on the involved triangular norm. When the triangular norm is Archimedean, the minimal solutions correspond one-to-one to the irredundant coverings of a set covering problem. When it is non-Archimedean, they only correspond to a subset of constrained irredundant coverings of a set covering problem. We then show that the problem of minimizing a linear objective function subject to a system of sup-T equations can be reduced into a 0–1 integer programming problem in polynomial time. This work generalizes most, if not all, known results and provides a unified framework to deal with the problem of resolution and optimization of a system of sup-T equations. Further generalizations and related issues are also included for discussion.     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

Integer Optimization on Convex Semialgebraic Sets

Let Y be a convex set in \Re ^k defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld ^O(k4) . For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y ^* . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming. Received August 3, 1998, and in revised form March 22, 1999.     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

New subgradient extragradient methods for solving monotone bilevel equilibrium problems

ABSTRACT

In this paper, we propose new subgradient extragradient methods for finding a solution of a strongly monotone equilibrium problem over the solution set of another monotone equilibrium problem which usually is called monotone bilevel equilibrium problem in Hilbert spaces. The first proposed algorithm is based on the subgradient extragradient method presented by Censor et al. [Censor Y, Gibali A, Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. J Optim Theory Appl. 2011;148:318–335]. The strong convergence of the algorithm is established under monotone assumptions of the cost bifunctions with Lipschitz-type continuous conditions recently presented by Mastroeni in the auxiliary problem principle. We also present a modification of the algorithm for solving an equilibrium problem, where the constraint domain is the common solution set of another equilibrium problem and a fixed point problem. Several fundamental experiments are provided to illustrate the numerical behaviour of the algorithms and to compare with others.     

A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations

be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method. We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise open questions. Received: June 11, 1998     

pth Power Lagrangian Method for Integer Programming

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.     

Multi-objective integer programming: A general approach for generating all non-dominated solutions

In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided.     

Constraint Programming and Hybrid Formulations for Three Life Designs

Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/integer programming methods. We consider three Life pattern-creation problems: finding maximum density still-Lifes, finding smallest immediate predecessor patterns, and finding period-2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.     

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.      

Flexible solutions to systems of linear inequalities

In this paper we present two methods for calculating solutions to a system of linear inequalities which have certain prescribed distance properties to the constraints (referred to as flexibility properties). The first method (based on the calculation of the centre of an inscribed sphere, which is a well-known problem in linear programming) allows changes in the solution in any direction over a certain distance without becoming infeasible. The second method consists in the calculation of a solution with flexibility properties with respect to a prescribed coordinate system. It comprises an iterative procedure inside the area of feasible solutions using simple arithmetic operations. The major part of the paper will be devoted to the second method, since it is new and has attractive properties. Both methods are particularly applicable to the analysis of linear programming models with uncertain and inaccurate constraint parameters and in cases where operational adjustments are desired.     

Underestimating the cost of a soft constraint is dangerous: revisiting the edit-distance based soft regular constraint

Many real-life problems are over-constrained, so that no solution satisfying all their constraints exists. Soft constraints, with costs denoting how much the constraints are violated, are used to solve these problems. We use the edit-distance based SoftRegular constraint as an example to show that a propagation algorithm that sometimes underestimates the cost may guide the search to incorrect (non-optimal) solutions to an over-constrained problem. To compute correctly the cost for the edit-distance based SoftRegular constraint, we present a quadratic-time propagation algorithm based on dynamic programming and a proof of its correctness. We also give an improved propagation algorithm using an idea of computing the edit distance between two strings, which may also be applied to other constraints with propagators based on dynamic programming. The asymptotic time complexity of our improved propagator is always at least as good as the one of our quadratic-time propagator, but significantly better when the edit distance is small. Our propagators achieve domain consistency on the problem variables and bounds consistency on the cost variable. Our method can also be adapted for the violation measure of the edit-distance based Regular constraint for constraint-based local search.     

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax−by⩽z+c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions.Nonmonotone integer programs are optimization problems with constraints of the type ax+by⩽z+c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe.The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover.Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality.     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.