this paper introduces an integerprogramming approach for a class of staff scheduling problems which is applicable for various kinds of the problems by both adopting an optimization model and parameter estimation tech...
详细信息
ISBN:
(纸本)9781467327435;9781467327428
this paper introduces an integerprogramming approach for a class of staff scheduling problems which is applicable for various kinds of the problems by both adopting an optimization model and parameter estimation techniques based on a mathematical programming formulation. For a work in which a staff must change or rotate shifts, generally, a responsible personnel (e.g., a manager) makes a schedule (e.g., a dairy or a weekly staff assignment) in a manual way based on some experiences. It is very hard, however, to generate not only a good schedule but also a feasible one, due to several kinds of constraints and requirements should be satisfied. Here, it is the case that the constraints are not be completely clear because these have no evident boundary, which makes the scheduling problems more difficult. In this paper, first, the staff scheduling problem is formally described in a rather generalized form to apply a wide range of work types, and is formulated as a integerprogramming model. In this formulation, so many parameters concerning the desires of workers as well as the conditions on works are included. then, some ways of identifying the parameters is investigated by utilizing the available information acquired extraction from the past staff schedules and listening from managers. In the case that the setting of the parameters is not suitable, a good schedule or even a practical schedule can not be obtained through the integerprogramming model. With respect to this point, some computational examples have been done in order to examine the reliability of the way of setting parameters as well as the model of optimizing schedule. through the result of computational examples, the effectiveness and the potential of the proposed approach are confirmed.
Orbital branching is a method for branching on variables in integerprogrammingthat reduces the likelihood of evaluating redundant, isomorphic nodes in the branch-and-bound procedure. In this work, the orbital branch...
详细信息
ISBN:
(纸本)9783540688860
Orbital branching is a method for branching on variables in integerprogrammingthat reduces the likelihood of evaluating redundant, isomorphic nodes in the branch-and-bound procedure. In this work, the orbital branching methodology is extended so that the branching disjunction can be based on an arbitrary constraint. Many important families of integer programs are structured such that small instances from the family are embedded in larger instances. this structural information can be exploited to define a group of strong constraints on which to base the orbital branching disjunction. the symmetric nature of the problems is further exploited by enumerating non-isomorphic solutions to instances of the small family and using these solutions to create a collection of typically easy-to-solve integer programs. the solution of each integer program in the collection is equivalent to solving the original large instance. the effectiveness of this methodology is demonstrated by computing the optimal incidence width of Steiner Triple Systems and minimum cardinality covering designs.
Consider an integer program max(c(t)x : Ax = b, x >= 0, x is an element of Z(n)) where A is an element of Z(mxn) , b is an element of Z(m), and c is an element of Z(n). We show that the integer program can be solve...
详细信息
ISBN:
(纸本)9783540727910
Consider an integer program max(c(t)x : Ax = b, x >= 0, x is an element of Z(n)) where A is an element of Z(mxn) , b is an element of Z(m), and c is an element of Z(n). We show that the integer program can be solved in pseudo-polynomial time when A is non-negative and the column-matroid of A has constant branch-width.
this paper addresses the problem of generating strong convex relaxations of Mixed integer Quadratically Constrained programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non...
详细信息
ISBN:
(纸本)9783540688860
this paper addresses the problem of generating strong convex relaxations of Mixed integer Quadratically Constrained programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities by using the equation Y = xx(T). We use the concave constraint 0 >= Y - xx(T) to derive disjunctions of two types. the first ones are directly derived from the eigenvectors of the matrix Y-xx(T) with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the width of the disjunction. We also use the convex SDP constraint Y - xx(T) >= 0 to derive convex quadratic cuts and combine both approaches in a cutting plane algorithm. We present preliminary computational results to illustrate our findings.
Since Wagner and Whitin published a seminal paper on the deterministic uncapacitated lot-sizing problem, many other researchers have investigated the structure of other fundamental models on lot-sizing that are embedd...
详细信息
ISBN:
(纸本)9783540688860
Since Wagner and Whitin published a seminal paper on the deterministic uncapacitated lot-sizing problem, many other researchers have investigated the structure of other fundamental models on lot-sizing that are embedded in practical production planning problems. In this paper we consider basic versions of such models in which demand (and other problem parameters) are stochastic rather than deterministic. It is named stochastic uncapacitated lot-sizing problem with backlogging. We define a production path property of optimal solutions for this model and use this property to develop backward dynamic programming recursions. this approach allows us to show that the value function is piecewise linear and continuous, which we can further use to define a polynomial time algorithm for the problem in a general stochastic scenario tree setting.
作者：
Meister, BICPS
LSIIT F-67400 Illkirch Graffenstaden France
this paper presents a new method for computing the integer hull of a parameterized rational polyhedron by introducing the concept of periodic polyhedron. Besides concerning generally parametric combinatorial optimizat...
详细信息
ISBN:
(纸本)3540212973
this paper presents a new method for computing the integer hull of a parameterized rational polyhedron by introducing the concept of periodic polyhedron. Besides concerning generally parametric combinatorialoptimization, the method has many applications for the analysis, optimization and parallelization of loop nests, especially in compilers.
We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare...
详细信息
ISBN:
(纸本)9783540688860
We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants withthat of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprizing phenomenon.
the paper suggests several ways how to combine a genetic algorithm withintegerprogramming to improve the quality of the problem solution. the motivation is that today's integerprogramming solvers are very sophi...
详细信息
ISBN:
(纸本)9789616165457
the paper suggests several ways how to combine a genetic algorithm withintegerprogramming to improve the quality of the problem solution. the motivation is that today's integerprogramming solvers are very sophisticated and efficient and they are worth utilizing in combination with metaheuristics to solve hard combinatorialoptimization problems. the capacitated p-median problem is chosen as an example of such a problem that is intractable for an exact method and needs a heuristic or metaheuristic method, e.g. a genetic algorithm to get a near-optimal solution. A genetic algorithm can be combined withintegerprogramming in such a way that the metaheuristics acts at a higher level and controls the calls to the solver. the solver can be used for: (i) fitness calculation, (ii) improving the best solution, and (iii) generating elite solutions. Several variants of the hybrid genetic algorithm are proposed and tested using benchmark instances.
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastic...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
We describe an algorithm that finds an is an element of-approximate solution to a concave mixed-integer quadratic programming problem. the running time of the proposed algorithm is polynomial in the size of the proble...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We describe an algorithm that finds an is an element of-approximate solution to a concave mixed-integer quadratic programming problem. the running time of the proposed algorithm is polynomial in the size of the problem and in 1/is an element of, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. the running time of the proposed algorithm is expected unless P = NP.
暂无评论