The paper presents a new mixed-integer programming formulation for the maximally diverse grouping problem (MDGP) with attribute values. The MDGP is the problem of assigning items to groups such that all groups are as ...
详细信息
The paper presents a new mixed-integer programming formulation for the maximally diverse grouping problem (MDGP) with attribute values. The MDGP is the problem of assigning items to groups such that all groups are as heterogeneous as possible. In the version with attribute values, the heterogeneity of groups is measured by the sum of pairwise absolute differences of the attribute values of the assigned items, i.e. by the Manhattan metric. The advantage of the version with attribute values is that the objective function can be reformulated such that it is linear instead of quadratic like in the standard MDGP formulation. We evaluate the new model formulation for the MDGP with attribute values in comparison with two different MDGP formulations from the literature. Our model formulation leads to substantially improved computation times and solves instances of realistic sizes (for example the assignment of students to seminars) with up to 70 items and three attributes, 50 items and five attributes, and 30 items and ten attributes to (near) optimality within half an hour.
In this article, we study the bi-level linear programming problem with multiple objective functions on the upper level (with particular focus on the bi-objective case) and a single objective function on the lower leve...
详细信息
In this article, we study the bi-level linear programming problem with multiple objective functions on the upper level (with particular focus on the bi-objective case) and a single objective function on the lower level. We have restricted our attention to this type of problem because the consideration of several objectives at the lower level raises additional issues for the bi-level decision process resulting from the difficulty of anticipating a decision from the lower level decision maker. We examine some properties of the problem and propose a methodological approach based on the reformulation of the problem as a multiobjective mixed 0-1 linear programming problem. The basic idea consists in applying a reference point algorithm that has been originally developed as an interactive procedure for multiobjective mixed-integer programming. This approach further enables characterization of the whole Pareto frontier in the bi-objective case. Two illustrative numerical examples are included to show the viability of the proposed methodology.
Handling traffic delays in a mobile communication network (MCN) is a principal problem due to time and cost expenses. Delays limit mobile coverage. Therefore, optimisation techniques and tools are applied to minimise ...
详细信息
Handling traffic delays in a mobile communication network (MCN) is a principal problem due to time and cost expenses. Delays limit mobile coverage. Therefore, optimisation techniques and tools are applied to minimise delays. However, there is still a high chance that at some points the network will lose its integral connectivity and delays happen. Delays prohibit call transmissions and produce several breaks. System breaks/delays cause call pending for a connection. Accordingly, network partitioning happens, thus leads to disconnection. This paper proposes a mixed-integer programming (MIP) to minimise network delays while a reliable trade-off between registration signalling (RS) and paging (P) coverage distances is maintained. The proposed MIP is NP-hard. For this reason, a metaheuristic approach, genetic algorithm (GA), is developed and compared with it. MIP validation is endorsed by GA approximations in different random trials and comparative analysis investigates GA performance metrics in a numerical example.
The increased use of multi-vehicles raises concerns about safety and economic aspects in several applications. Therefore, this work proposes a moving horizon planning algorithm for covering unexplored regions using mu...
详细信息
Fenchel cutting planes are based on the dual relationship between separation and optimization and can be applied in many instances where alternative cutting planes cannot. They are deep in the sense of providing the m...
详细信息
Fenchel cutting planes are based on the dual relationship between separation and optimization and can be applied in many instances where alternative cutting planes cannot. They are deep in the sense of providing the maximum separation between a point ($) over cap x and a polyhedron P as measured by an arbitrary norm which is specified in the process of generating a Fenchel cut. This paper demonstrates a number of fundamental convergence properties of Fenchel cuts and addresses the question of which norms lead to the most desirable Fenchel cuts. The strengths and weaknesses of the related class of 1-polar cuts are also examined.
Multi-piece mould design is a moulding technology that involves three-dimensional spatial construction of two or more mould pieces in a manner similar to assembling/dissembling a three-dimensional puzzle to build prod...
详细信息
Multi-piece mould design is a moulding technology that involves three-dimensional spatial construction of two or more mould pieces in a manner similar to assembling/dissembling a three-dimensional puzzle to build production parts. Using such a moulding technology, complex parts with intricate geometries can be made for limited run productions. Compared to traditional two-piece moulds and rapid prototyping, the multi-piece mould approach has many advantages with respect to part complexity and production speed, etc.;however, the technology has challenges in designing the actual multi-piece moulds. Previous methodologies address this problem primarily using heuristics. We present a multi-piece mould design (MPMD) framework that is based on a mixed-integer programming approach. The method constructs the MPMD by minimising the number of mould pieces that is required for a given Computer-Aided Design (CAD) model. The solution strategy for the formulated linear mixed-integer optimisation problem is presented. The algorithmic strategy for solving the resulting mixed-integer programming problem is also provided with examples that illustrate the effectiveness and efficiency of the approach.
The present authors consider the widely popular Argentine Turismo Carretera car racing series, which consists of 11 regular phase races followed by five playoff races. After the regular phase, the first 12 racers in t...
详细信息
The present authors consider the widely popular Argentine Turismo Carretera car racing series, which consists of 11 regular phase races followed by five playoff races. After the regular phase, the first 12 racers in the standings qualify for the playoffs, which determine the champion. The present authors address the problem of determining, at any point within the regular phase, the minimum number of points that each racer must earn in the remainder of the regular phase in order to secure a playoff spot. Two mixed-integer programming models for this problem are presented, their properties and practical performance are analysed, and the obtained results are discussed.
Dantzig-Wolfe decomposition can be used to solve the Lagrangian dual of a linear mixed-integer programming problem (MIP) if the dual structure of the (MIP) is exploited via Lagrangian relaxation with respect to the co...
详细信息
We present an ideal mixed-integer programming (MIP) formulation for a rectified linear unit (ReLU) appearing in a trained neural network. Our formulation requires a single binary variable and no additional continuous ...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
We present an ideal mixed-integer programming (MIP) formulation for a rectified linear unit (ReLU) appearing in a trained neural network. Our formulation requires a single binary variable and no additional continuous variables beyond the input and output variables of the ReLU. We contrast it with an ideal "extended" formulation with a linear number of additional continuous variables, derived through standard techniques. An apparent drawback of our formulation is that it requires an exponential number of inequality constraints, but we provide a routine to separate the inequalities in linear time. We also prove that these exponentially-many constraints are facet-defining under mild conditions. Finally, we study network verification problems and observe that dynamically separating from the exponential inequalities (1) is much more computationally efficient and scalable than the extended formulation, (2) decreases the solve time of a state-of-the-art MIP solver by a factor of 7 on smaller instances, and (3) nearly matches the dual bounds of a state-of-the-art MIP solver on harder instances, after just a few rounds of separation and in orders of magnitude less time.
A methodology to solve the network expansion planning problem considering N-1 security criterion is proposed. The main idea to achieve the desired results is to separate the whole problem into two subproblems and solv...
详细信息
ISBN:
(纸本)9781424483570
A methodology to solve the network expansion planning problem considering N-1 security criterion is proposed. The main idea to achieve the desired results is to separate the whole problem into two subproblems and solve them iteratively. The aim of upper level problem is to solve the mixed-integer programming model with all identified constraints. For the lower level problem, all N-1 contingencies are checked one by one and the corresponding constraints are added the upper level problem if line overload or network split is found. Each constraint is formed based on rigorous sensitivity or network topology analysis. The iteration between the two subproblems stops till a satisfactory planning solution is reached. Test results on two systems show effectiveness of the proposed method.
暂无评论