Recently, the XHSTT format for high school timetabling was introduced. It provides a uniform way of modeling problem instances and corresponding solutions. The format supports a wide variety of constraints, and curren...
详细信息
Recently, the XHSTT format for high school timetabling was introduced. It provides a uniform way of modeling problem instances and corresponding solutions. The format supports a wide variety of constraints, and currently 38 real-life instances from 11 different countries are available. Thereby, the XHSTT format serves as a common ground for researchers within this area. This paper describes the first exact method capable of handling an arbitrary instance of the XHSTT format. The method is based on a mixed-integer linear programming (MIP) model, which is solved in two steps with a commercial general-purpose MIP solver. Computational results show that our approach is able to find previously unknown optimal solutions for 2 instances of XHSTT and proves optimality of 4 known solutions. For the instances not solved to optimality, new non-trivial lower bounds were found in 11 cases, and new best known solutions were found in 9 cases. Furthermore, the approach is compared with the finalists of Round 2 of the International Timetabling Competition 2011 and is shown to be competitive with one of the finalists.
作者：
Cussens, JamesUniv York
Dept Comp Sci York YO10 5DD N Yorkshire England Univ York
York Ctr Complex Syst Anal York YO10 5DD N Yorkshire England
Bayesian networks provide an attractive representation of structured probabilistic information. There is thus much interest in 'learning' BNs from data. In this paper the problem of learning a Bayesian network...
详细信息
Bayesian networks provide an attractive representation of structured probabilistic information. There is thus much interest in 'learning' BNs from data. In this paper the problem of learning a Bayesian network using integer programming is presented. The SCLP (Solving Constraint integer programming) framework is used to do this. Although cutting planes are a key ingredient in our approach, primal heuristics and efficient propagation are also important.
We deal with three competitive location problems based on the classical Maximal Covering Location Problem. The environment of these problems consists of an open market with two firms (leader and follower), several cus...
详细信息
We deal with three competitive location problems based on the classical Maximal Covering Location Problem. The environment of these problems consists of an open market with two firms (leader and follower), several customers and locations where facilities can be located. In order to capture the demand of the customers, the leader enters the market by locating a set of facilities knowing the potential locations where the follower can locate her facilities after the leader's decision. We consider here three pairs of objective functions for the leader/follower previously studied in the literature: maximizing/minimizing the demand captured by the leader, minimizing/maximizing the regret of the leader, maximizing the demand captured by each firm (also known as Stackelberg). For each model, we propose an integer linear programming formulation with a polynomial number of variables and an exponential number of constraints. The formulations are solved by branch-and-cut algorithms where the constraints are generated on demand by solving appropriate separation problems. We report extensive computational experiments realized on instances inspired by those from the literature, comparing our algorithms with the exact and heuristic algorithms previously published for these problems. (C) 2017 Elsevier B.V. All rights reserved.
This paper studies the mid-term production planning of high-tech low-volume industries. Mid-term production planning (6 to 24 months) allocates the capacity of production resources to different products over time and ...
详细信息
This paper studies the mid-term production planning of high-tech low-volume industries. Mid-term production planning (6 to 24 months) allocates the capacity of production resources to different products over time and coordinates the associated inventories and material inputs so that known or predicted demand is met in the best possible manner. High-tech low-volume industries can be characterized by the limited production quantities and the complexity of the supply chain. To model this, we introduce a mixed integer linear programming model that can handle general supply chains and production processes that require multiple resources. Furthermore, it supports semi-flexible capacity constraints and multiple production modes. Because of the integer production variables, size of realistic instances and complexity of the model, this model is not easily solved by a commercial solver. Applying Benders' decomposition results in alternative capacity constraints and a second formulation of the problem. Where the first formulation assigns resources explicitly to release orders, the second formulation assures that the available capacity in any subset of the planning horizon is sufficient. Since the number of alternative capacity constraints is exponential, we first solve the second formulation without capacity constraints. Each time an incumbent is found during the branch and bound process a maximum flow problem is used to find missing constraints. If a missing constraint is found it is added and the branch and bound process is restarted. Results from a realistic test case show that utilizing this algorithm to solve the second formulation is significantly faster than solving the first formulation. (C) 2018 Elsevier B.V. All rights reserved.
This paper addresses the problem of designing an optimal micro-hydro power installation in rivers with generic profiles, when micro-hydro schemes are studied. This is geared towards the application of Micro Hydro Powe...
详细信息
This paper addresses the problem of designing an optimal micro-hydro power installation in rivers with generic profiles, when micro-hydro schemes are studied. This is geared towards the application of Micro Hydro Power Plants to supply marginal isolated areas using small Pelton wheels, where both technology and resources are limited. For this purpose, a model of a Pelton micro-hydro plant is first developed. Subsequently, a discretization of the river profile is made, on the basis of which a set of integer variables are proposed, being the model transformed then into an integer optimization problem. Finally, the effectiveness of the proposed method is showed through a specific design problem. The application of the developed method is especially interesting when designing micro-hydro plants to provide electricity to isolated populations, where both technology and resources are limited. (C) 2018 Elsevier Ltd. All rights reserved.
Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most onc...
详细信息
Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If negative costs are allowed, the problem is NP-hard. In this paper, several integer programming formulations for the ESPP are compared. We present analytical results based on a polyhedral study of the formulations, and computational experiments where we compare their linear programming relaxation bounds and their behavior within a branch-and-cut framework. The computational results show that a formulation with dynamically generated cutset inequalities is the most effective. (C) 2016 Elsevier B.V. All rights reserved.
A proper edge-coloring of a given undirected graph with natural numbers identified with colors is an interval (or consecutive) coloring if the colors of edges incident to each vertex form an interval of consecutive in...
详细信息
A proper edge-coloring of a given undirected graph with natural numbers identified with colors is an interval (or consecutive) coloring if the colors of edges incident to each vertex form an interval of consecutive integers. Not all graphs admit such an edge-coloring and the problem of deciding whether a graph is interval colorable is NP-complete. For a graph that is not interval colorable, determining a graph invariant called the (minimum) deficiency is a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring. The majority of the studies in the literature either derive bounds on the deficiency of general graphs or calculate the deficiency of graphs belonging to some special graph classes. In this work, we derive integer programming formulations of the Minimum Deficiency Problem which seeks to find the exact deficiency value of a graph, given a bound on the number of colors that can be used. We further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via a branch-and-cut algorithm. Our computational study on a large set of random graphs illustrates the strength of our formulation and the efficiency of the proposed approach.
A printed circuit board (PCB) assembly task requires that a set of components be picked from their respective pickup locations and then be placed at their respective placement locations on the card being assembled, A ...
详细信息
A printed circuit board (PCB) assembly task requires that a set of components be picked from their respective pickup locations and then be placed at their respective placement locations on the card being assembled, A pick-and-place robot is used for automated assembly of PCB's, The overall assembly time depends on two different decision variables: i) the pickup locations of the components (in general there are several alternative pickup locations available, whereas the placement location of components is fixed and is determined by the card being assembled), and ii) the sequence in which the pickup and placement of components is performed, In this paper, we develop a technique based on integer programming to determine both an optimal assignment of pickup locations as well as an optimal sequence of pickup and placements of the components, We demonstrate that the overall optimization problem is an instance of linear integer programming, and hence it is computationally intractable, We obtain near optimal solutions-that are computationally tractable-using the techniques of i) minimum weight matching for determining an optimal assignment of pickup locations, and ii) traveling salesman problem for determining an optimum sequence of pickups and placements, Near optimal solutions provide an upper bound for the optimal assembly time;we consider a linear programming relaxation of the problem to obtain a lower bound for the optimal assembly time. The gap between the upper bound and the lower bound provides a measure of closeness of near optimal solutions to an optimal one, Finally, we use simulations to compare the saving in overall assembly time using the techniques developed here and some of the techniques that are currently in use in industrial settings.
Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing lit...
详细信息
Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.
In this study, an integer programming approach is introduced to construct unequal error protection (UEP) codes for a multiuser broadcast communication system. The authors establish integer programming models for both ...
详细信息
In this study, an integer programming approach is introduced to construct unequal error protection (UEP) codes for a multiuser broadcast communication system. The authors establish integer programming models for both binary and non-binary UEP codes. The results show that optimal UEP codes can be constructed such that their code lengths achieve the integer programming bounds. Based on the bounds, the authors investigate asymptotic behaviour of code rates with symbols in GF(q), and the authors present performance analysis of multiuser communications over a degraded broadcast channel with the optimal UEP codes.
暂无评论