We propose a general methodology based on robust optimization to address the problem of optimally controlling a supply chain subject to stochastic demand in discrete time. the attractive features of the proposed appro...
详细信息
ISBN:
(纸本)3540221131
We propose a general methodology based on robust optimization to address the problem of optimally controlling a supply chain subject to stochastic demand in discrete time. the attractive features of the proposed approach are: (a) It incorporates a wide variety of phenomena, including demands that are not identically distributed over time and capacity on the echelons and links;(b) it uses very little information on the demand distributions;(c) it leads to qualitatively similar optimal policies (basestock policies) as in dynamic programming;(d) it is numerically tractable for large scale supply chain problems even in networks, where dynamic programming methods face serious dimensionality problems;(e) in preliminary computational experiments, it often outperforms dynamic programming based solutions for a wide range of parameters.
Knapsack problem is one of classical combinatorialoptimization problems, and has a lot of applications. It is known to be NP-hard. In this paper we propose a multistart local search heuristic for solving the knapsack...
详细信息
Answer set programming is a programming paradigm where a given problem is formalized as a logic program whose answer sets correspond to the solutions to the problem. In this paper, we link answer set programming with ...
详细信息
In this work we present the Partner Units Problem as a novel challenge for optimization methods. It captures a certain type of configuration problem that frequently occurs in industry. Unfortunately, it can be shown t...
详细信息
ISBN:
(纸本)9783642213113
In this work we present the Partner Units Problem as a novel challenge for optimization methods. It captures a certain type of configuration problem that frequently occurs in industry. Unfortunately, it can be shown that in the most general case an optimization version of the problem is intractable. We present and evaluate encodings of the problem in the frameworks of answer set programming, propositional satisfiability testing, constraint solving, and integerprogramming. We also show how to adapt these encodings to a class of problem instances that we have recently shown to be tractable.
Standard mixed-integerprogramming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomi...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Standard mixed-integerprogramming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-sizeMIP formulation requires Omega(n/ log(2) n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Omega(root n/ log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we show that there exists a family of n-node graphs whose stable set polytopes satisfy the following: any (1 + epsilon/n)-approximate extended formulation for these polytopes, for some constant epsilon > 0, has size 2(Omega(n / log n)). Our proof extends and simplifies the information-theoretic methods due to Goos, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) who showed the same result for the case of exact extended formulations (i.e. epsilon = 0).
Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary...
详细信息
Discrete black-box optimization problems are challenging for model-based optimization (MBO) algorithms, such as Bayesian optimization, due to the size of the search space and the need to satisfy combinatorial constrai...
Discrete black-box optimization problems are challenging for model-based optimization (MBO) algorithms, such as Bayesian optimization, due to the size of the search space and the need to satisfy combinatorial constraints. In particular, these methods require repeatedly solving a complex discrete global optimization problem in the inner loop, where popular heuristic inner-loop solvers introduce approximations and are difficult to adapt to combinatorial constraints. In response, we propose NN+MILP, a general discrete MBO framework using piecewise-linear neural networks as surrogate models and mixed-integer linear programming (MILP) to optimize the acquisition function. MILP provides optimality guarantees and a versatile declarative language for domain-specific constraints. We test our approach on a range of unconstrained and constrained problems, including DNA binding, constrained binary quadratic problems from the MINLPLib benchmark, and the NAS-Bench-101 neural architecture search benchmark. NN+MILP surpasses or matches the performance of black-box algorithms tailored to the constraints at hand, with global optimization of the acquisition problem running in a few minutes using only standard software packages and hardware.
We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which a...
详细信息
ISBN:
(纸本)9783540727910
We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which are new. Variant 1 is the original procedure of [6] with minor modifications. Variant 2 uses a new procedure for choosing the pivot element: After identifying the set of row candidates for an improving pivot, the pivot element (and column) is chosen by optimizing over the entries of all candidate rows. Finally, Variant 3 replaces the source row with its disjunctive modularization, and after each pivot it again modularizes the resulting source row. We report on computational results withthe above three variants and their combinations on 65 MIPLIB.3 instances.
Gomory's Mixed-integer Cuts (GMICs) are widely used in modern branch-and-cut codes for the solution of Mixed-integer Programs. Typically, GMICs are iteratively generated from the optimal basis of the current Linea...
详细信息
ISBN:
(纸本)9783642135194
Gomory's Mixed-integer Cuts (GMICs) are widely used in modern branch-and-cut codes for the solution of Mixed-integer Programs. Typically, GMICs are iteratively generated from the optimal basis of the current Linear programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach prone to instability. In this paper we analyze a different scheme for the generation of rank-1 GMIC read from a basis of the original LP-the one before the addition of any cut. We adopt a relax-and-cut approach where the generated GMIC are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast-yet accurate-variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality, including those proposed very recently by Balas and Bonami and by Dash and Goycoolea.
Nursing workload in hospitals has an impact on the quality of care and on job satisfaction. Understandably there has been much recent research on improving the staffing and nurse-patient assignment decisions in increa...
详细信息
ISBN:
(纸本)9783319339542;9783319339535
Nursing workload in hospitals has an impact on the quality of care and on job satisfaction. Understandably there has been much recent research on improving the staffing and nurse-patient assignment decisions in increasingly realistic settings. On a version of the nurse-patient assignment problem given a fixed staffing of neonatal intensive care units, constraint programming (CP) was shown to perform better than competing optimization methods. In this paper we take advantage of recent improvements to the CP approach to solve the integrated problem of staffing and nurse-patient assignment. We then consider a more difficult but also more realistic version of the problem in which patients are categorized into a small number of types and the workload associated with each type is nurse-dependent.
暂无评论