State-of-the-art solvers for mixed integerprogramming (MIP) problems are highly parameterized, and finding parameter settings that achieve high performance for specific types of MIP instances is challenging. We study...
详细信息
ISBN:
(纸本)9783642135194
State-of-the-art solvers for mixed integerprogramming (MIP) problems are highly parameterized, and finding parameter settings that achieve high performance for specific types of MIP instances is challenging. We study the application of an automated algorithm configuration procedure to different MIP solvers, instance types and optimization objectives. We show that this fully-automated process yields substantial improvements to the performance of three MIP solvers: CPLEX, GUROBI, and LPSOLVE. Although our method can be used "out of the box" without any domain knowledge specific to MIP, we show that it outperforms the CPLEX special-purpose automated tuning tool.
this paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic varia...
详细信息
ISBN:
(纸本)9783642130359
this paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting. the answer is a nonconvex region that can be obtained as the union of convex polyhedra.
We describe new algorithms for solving linear programming relaxations of very large precedence constrained production scheduling problems. We present theory that motivates a new set of algorithmic ideas that;can be em...
详细信息
ISBN:
(纸本)9783642130359
We describe new algorithms for solving linear programming relaxations of very large precedence constrained production scheduling problems. We present theory that motivates a new set of algorithmic ideas that;can be employed on a wide range of problems;on data sets arising in the mining industry our algorithms prove effective on problems with many millions of variables and constraints, obtaining provably optimal solutions in a few minutes of computation(1).
In this paper, we present a constraint programming approach for the service consolidation problem that is being currently tackled by Neptuny, Milan. the problem is defined as: Given a data-center, a set of servers wit...
详细信息
ISBN:
(纸本)9783642135194
In this paper, we present a constraint programming approach for the service consolidation problem that is being currently tackled by Neptuny, Milan. the problem is defined as: Given a data-center, a set of servers with a priori fixed costs, a set of services or applications with hourly resource utilizations, find an allocation of applications to servers while minimizing the data-center costs and satisfying constraints on the resource utilizations for each hour of the day profile and on rule-based constraints defined between services and servers and amongst different services. the service consolidation problem can be modelled as an integer Linear programming problem with 0-1 variables, however it is extremely difficult to handle large sized instances and the rule-based constraints. So a constraint programming approach using the COMET programming language is developed to assess the impact of the rule-based constraints in reducing the problem search space and to improve the solution quality and scalability. Computational results for realistic consolidation scenarios are presented, showing that the proposed approach is indeed promising.
In the cutting stock problem we are given a set T of object types, where objects of type T-i is an element of T have integer length p(i) > 0. Given a set O of n objects containing n(i) objects of type T-i, for each...
详细信息
ISBN:
(纸本)9783642130359
In the cutting stock problem we are given a set T of object types, where objects of type T-i is an element of T have integer length p(i) > 0. Given a set O of n objects containing n(i) objects of type T-i, for each i = 1, ..., d, the problem is to pack O into the minimum number of bins of capacity beta. In this paper we consider the version of the problem in which the number d of different object types is constant and we present an algorithm that computes a solution using at most OPT + 1 bins, where OPT is the value of an optimum solution.
We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing o...
详细信息
ISBN:
(纸本)9783642130359
We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problem us with box constraints. the main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.
We present a new method to compute upper bounds of the number of solutions of binary integerprogramming (BIP) problems. Given a BIP, we create a dynamic programming (DP) table for a redundant knapsack constraint whic...
详细信息
ISBN:
(纸本)9783642135194
We present a new method to compute upper bounds of the number of solutions of binary integerprogramming (BIP) problems. Given a BIP, we create a dynamic programming (DP) table for a redundant knapsack constraint which is obtained by surrogate relaxation. We then consider a Lagrangian relaxation of the original problem to obtain an initial weight bound on the knapsack. this bound is then refined through subgradient optimization. the latter provides a variety of Lagrange multipliers which allow us to filter infeasible edges in the DP table. the number of paths in the final table then provides an upper bound on the number of solutions. Numerical results show the effectiveness of our counting framework on automatic recording and market split problems.
Majority of process plants contain heat exchanger networks. these facilitate heat exchange between hot and cold process streams and thus lower demand for energy of the entire plant. As a result, this leads not only to...
详细信息
ISBN:
(纸本)9788895608051
Majority of process plants contain heat exchanger networks. these facilitate heat exchange between hot and cold process streams and thus lower demand for energy of the entire plant. As a result, this leads not only to lower operational costs but can also cause an abatement of emissions plants produce. the aim of this paper is to provide a multi-objective optimization algorithm that can be used for automated synthesis of small-scale heat exchanger networks commonly used in waste-to-energy process plants. this algorithm employs two optimization models, first of which is an MILP (Mixed-integer Linear programming) model that does not support stream splitting or any other feature requiring non-linear constraints. Optimum design of a simple HEN is always quickly reached due to model's linearity. the other model is a more sophisticated MINLP (Mixed-integer Non-Linear programming) one which contains non-linear constraints and therefore its computational requirements are relatively high. Both models are based on previous work of Turek et al. (2009) and are enhanced withthe emphasis on obtaining a global solution within a reasonable time frame. Also, an existing heat exchanger network is analyzed in the paper and possible improvements are discussed.
Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT ...
详细信息
ISBN:
(纸本)9783642135194
Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integerprogramming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.
In the standard Constraint programming (CP) framework, an integer variable represents a signed integer and its domain is bounded by some minimal and maximal integer type values. In existing CP tools, the integer type ...
详细信息
ISBN:
(纸本)9783642135194
In the standard Constraint programming (CP) framework, an integer variable represents a signed integer and its domain is bounded by some minimal and maximal integer type values. In existing CP tools, the integer type is used to represent domain values, and hence domain bounds are inherently limited by the minimal and maximal signed integer values representable on a given platform. However, this implementation of integer variable fails to satisfy use cases where modeled integers can be arbitrarily large. An example of such CP application is the functional test generation where integer variables are used to model large architectural fields like memory addresses or operand data. In addition, in such applications, the set of standard arithmetic operations on an integer variable provided by the traditional CP framework does not represent the whole range of operations required for modeling. In this paper, we define a new type of integer variables with arbitrarily large domain size and a modified operation set. We show how this variable type can be realized on top of a traditional CP framework by means of global constraints over standard integer variables. the ideas presented in this paper can also be used to implement a native variable of the introduced type in a CP tool. the paper provides experimental results to demonstrate the effectiveness of the proposed approach.
暂无评论