this paper studies the quayside operation problem, in which three seaside planning decisions are integrated, withthe objective of minimizing the maximum relative tardiness. A refinement of the state-of-the-art formul...
详细信息
ISBN:
(纸本)9781538651780
this paper studies the quayside operation problem, in which three seaside planning decisions are integrated, withthe objective of minimizing the maximum relative tardiness. A refinement of the state-of-the-art formulation is presented in this work, and an improved exact combinatorial Benders decomposition algorithm is devised for the problem at container terminals which used to be typically modeled by mixed-integer linear programming problems containing a large number of "big-M" coefficients.
Linear programs with joint probabilistic constraints (PCLP) are known to be highly intractable due to the non-convexity of the feasible region. We consider a special case of PCLP in which only the right-hand side is r...
详细信息
ISBN:
(纸本)9783540727910
Linear programs with joint probabilistic constraints (PCLP) are known to be highly intractable due to the non-convexity of the feasible region. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We present a mixed integerprogramming formulation and study the relaxation corresponding to a single row of the probabilistic constraint, yielding two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results that indicate that by using our strengthened formulations, large scale instances can be solved to optimality.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from pro...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. this paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral con...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chv ' atal closure, and Carath ' eodory rank to integer points in arbitrary cones.
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integerprogramming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n item...
详细信息
ISBN:
(纸本)9783031327254;9783031327261
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integerprogramming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. the objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. On many of the harder instances, our algorithm is hundreds of times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. this dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. the relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.
AND/OR search spaces are a unifying paradigm for advanced algorithmic schemes for graphical models. the main virtue of this representation is its sensitivity to the structure of the model, which can translate into exp...
详细信息
ISBN:
(纸本)9783540723967
AND/OR search spaces are a unifying paradigm for advanced algorithmic schemes for graphical models. the main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. In this paper we introduce an AND/OR search algorithm that explores a context-minimal AND/OR search graph in a best-first manner for solving 0/1 integer Linear Programs (0/1 ILP). We also extend to the 0/1 ILP domain the depth-first AND/OR Branch-and-Bound search with caching algorithm which was recently proposed by [1] for solving optimization tasks in graphical models. the effectiveness of the best-first AND/OR search approach compared to depth-first AND/OR Branch-and-Bound search is demonstrated on a variety of benchmarks for 0/1 ILPs, including instances from the MIPLIB library, real-world combinatorial auctions, random uncapacitated warehouse location problems and MAX-SAT instances.
A fundamental difficulty when dealing with a minimization problem given by a nonlinear, convex objective function over a nonconvex feasible region, is that even if we can efficiently optimize over the convex hull of t...
详细信息
ISBN:
(纸本)9783642130359
A fundamental difficulty when dealing with a minimization problem given by a nonlinear, convex objective function over a nonconvex feasible region, is that even if we can efficiently optimize over the convex hull of the feasible region, the optimum will likely lie in the interior of a high dimensional face, "far away" from any feasible point, yielding weak bounds. We present theory and implementation for an approach that relies on (a) the S-lemma. a major tool in convex analysis, (b) efficient projection of quadratics to lower dimensional hyperplanes, and (c) efficient computation of combinatorial bounds for the minimum distance from a given point to the feasible set, in the case of several significant optimization problems. On very large examples, we obtain significant lower bound improvements at a small computational cost(1).
In this paper, we present a systematic method to derive strong superadditive approximations of multidimensional lifting functions using single-dimensional superadditive functions. this constructive approach is based o...
详细信息
ISBN:
(纸本)9783540727910
In this paper, we present a systematic method to derive strong superadditive approximations of multidimensional lifting functions using single-dimensional superadditive functions. this constructive approach is based on the observation that, in many cases, the lifting function of a multidimensional problem can be expressed or approximated through the single-dimensional lifting function of some of its components. We then apply our approach to two variants of classical models and show that it yields an efficient procedure to derive strong valid inequalities.
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick lineari...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad's result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.
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.
暂无评论