共查询到20条相似文献,搜索用时 15 毫秒
1.
Xiaobo Li Karthik Natarajan Chung-Piaw Teo Zhichao Zheng 《European Journal of Operational Research》2014
In this paper, we review recent advances in the distributional analysis of mixed integer linear programs with random objective coefficients. Suppose that the probability distribution of the objective coefficients is incompletely specified and characterized through partial moment information. Conic programming methods have been recently used to find distributionally robust bounds for the expected optimal value of mixed integer linear programs over the set of all distributions with the given moment information. These methods also provide additional information on the probability that a binary variable attains a value of 1 in the optimal solution for 0–1 integer linear programs. This probability is defined as the persistency of a binary variable. In this paper, we provide an overview of the complexity results for these models, conic programming formulations that are readily implementable with standard solvers and important applications of persistency models. The main message that we hope to convey through this review is that tools of conic programming provide important insights in the probabilistic analysis of discrete optimization problems. These tools lead to distributionally robust bounds with applications in activity networks, vertex packing, discrete choice models, random walks and sequencing problems, and newsvendor problems. 相似文献
2.
Description of 2-integer continuous knapsack polyhedra 总被引:1,自引:0,他引:1
In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems. 相似文献
3.
In 1988, Nemhauser and Wolsey introduced the concept of MIR inequality for mixed integer linear programs. In 1998, Wolsey gave another definition of MIR inequalities. This note points out that the natural concepts of MIR closures derived from these two definitions are distinct. Dash, Günlük and Lodi made the same observation independently. 相似文献
4.
In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as
well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities
for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for
mixed integer programs.
The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive
lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong
valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer
rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0–1 single node flow set.
This paper appeared in 4OR, 1, 173–208 (2003).
The first author is supported by the FNRS as a chercheur qualifié. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction
initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed
by the authors. 相似文献
5.
本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解. 相似文献
6.
Paul McAree Lawrence Bodin Michael Ball James Segars 《Annals of Operations Research》2006,144(1):133-152
In this paper, two mixed integer programming models, the Aggregate Bin Assignment Model (ABAM) and Aggregate Rack Assignment
Model (ARAM), are developed for the analysis of possible large package sort facility designs for Federal Express Corporation.
Applying the ABAM and RAM algorithm on the current topological design of the sort facility reduces the number of forklifts
and total forklift travel time for accomplishing the sort by about 20%. Tests on 16 other configurations proposed by Federal
Express indicated that savings of 33% with respect to the number of forklifts required and over 50% in the total forklift
travel time when compared to the existing operations can be achieved. 相似文献
7.
《Operations Research Letters》2023,51(5):521-527
A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub. 相似文献
8.
Regulation of Overlaps in Technology Development Activities 总被引:6,自引:0,他引:6
John Liu 《Annals of Operations Research》2000,99(1-4):123-139
In this paper, we present an algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems involving (i) 0-1 integer variables, and, (ii) more than one parameter, bounded between lower and upper bounds, present on the right hand side (RHS) of constraints. The solution is approached by decomposing the mp-MILP into two subproblems and then iterating between them. The first subproblem is obtained by fixing integer variables, resulting in a multiparametric linear programming (mp-LP) problem, whereas the second subproblem is formulated as a mixed integer linear programming (MILP) problem by relaxing the parameters as variables. 相似文献
9.
Pierre Bonami Gérard Cornuéjols Sanjeeb Dash Matteo Fischetti Andrea Lodi 《Mathematical Programming》2008,113(2):241-257
Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often
gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the
Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose
MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP,
since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this
paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea
is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then
to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts
have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically
be solved in a reasonable amount of computing time.
Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894.
Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n.
FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract
n. FP6-021235-2). 相似文献
10.
In this paper a mixed integer set resulting from the intersection of a single constrained mixed 0–1 set with the vertex packing set is investigated. This set arises as a subproblem of more general mixed integer problems such as inventory routing and facility location problems. Families of strong valid inequalities that take into account the structure of the simple mixed integer set and that of the vertex packing set simultaneously are introduced. In particular, the well-known mixed integer rounding inequality is generalized to the case where incompatibilities between binary variables are present. Exact and heuristic algorithms are designed to solve the separation problems associated to the proposed valid inequalities. Preliminary computational experiments show that these inequalities can be useful to reduce the integrality gaps and to solve integer programming problems. 相似文献
11.
We consider mixed integer linear sets defined by two equations involving two integer variables and any number of non-negative continuous variables. We analyze the benefit from adding a non-split inequality on top of the split closure. Applying a probabilistic model, we show that the importance of a type 2 triangle inequality decreases with decreasing lattice width, on average. Our results suggest that this is also true for type 3 triangle and quadrilateral inequalities. 相似文献
12.
In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with two or more constraints. In particular, Andersen et al. (2007) [2] and Borozan and Cornuéjols (2009) [3] have studied sets defined by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes based on this approach have already been computationally studied by Espinoza (2008) [8] for general mixed-integer problems, and there is ongoing computational research in this area.In this paper, we extend the model studied in the earlier papers and require the integer variables to be non-negative. We extend the results in [2] and [3] to our case, and show that cuts generated by their approach can be strengthened by using the non-negativity of the integer variables. In particular, it is possible to obtain cuts which have negative coefficients for some variables. 相似文献
13.
Gérard Cornuéjols 《Mathematical Programming》2008,112(1):3-44
This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from
polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project
cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships
between these families. The tutorial also discusses computational aspects of generating the cuts and their strength.
Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894. 相似文献
14.
We present the Composite Approach for solving the Capacitated Arc Routing Problem with Vehicle/Site Dependencies (CARP-VSD).
We also present two mixed integer programs, the Initial Fleet Mix Generator (IFM) and the Mathematical Programming Procedure
(MPP), and a multi-criterion function called the Measure of Goodness. The IFM, MPP and Measure of Goodness are critical components
of the Composite Approach. A key application area of the CARP-VSD is the routing of residential sanitation vehicles; throughout
this paper, we derive parameters specific to this problem. In this paper, we describe the Composite Approach, the IFM, the
MPP, the Measure of Goodness and work out several examples in detail. 相似文献
15.
We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer
programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we
refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük (Math Program 105(1):29–53, 2006) are the
first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.
相似文献
16.
A pair of symmetric dual multiobjective variational mixed integer programs for the polars of arbitrary cones are formulated, which some primal and dual variables are constrained to belong to the set of integers. Under the separability with respect to integer variables and partial-invexity assumptions on the functions involved, we prove the weak, strong, converse and self-duality theorems to related minimax efficient solution. These results include some of available results. 相似文献
17.
Lizhi Wang 《Operations Research Letters》2009,37(2):114-116
We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal. 相似文献
18.
Models and algorithms to improve earthwork operations in road design using mixed integer linear programming 总被引:1,自引:0,他引:1
In road construction, earthwork operations account for about 25% of the construction costs. Existing linear programming models for earthwork optimization are designed to minimize the hauling costs and to balance the earth across the construction site. However, these models do not consider the removal of physical blocks that may influence the earthwork process. As such, current models may result in inaccurate estimates of optimal earthwork costs, leading to poor choices in road design. In this research, we extend the classical linear program model of earthwork operations to a mixed integer linear program model that accounts for blocks. We examine the economic impact of incorporating blocks via mixed integer linear programming, and find significant savings for most road designs in our test-set. However, the resulting model is considerably harder to solve than the original linear program. Based on structural observations, we introduce a set of algorithms that theoretically reduce the solving time of the model. We confirm this reduction in solve time with numerical experiments. 相似文献
19.
Muhong Zhang 《Operations Research Letters》2011,39(5):342-345
In this paper, we consider the two-stage minimax robust uncapacitated lot-sizing problem with interval uncertain demands. A mixed integer programming formulation is proposed. Even though the robust uncapacitated lot-sizing problem with discrete scenarios is an NP-hard problem, we show that it is polynomial solvable under the interval uncertain demand set. 相似文献