We study the design of an electromagnetic cloak from multiple materials with an additional constraint on the mass of the cloak. Our problem is an example of a topology optimization problem, and we formulate this probl...
详细信息
We study the design of an electromagnetic cloak from multiple materials with an additional constraint on the mass of the cloak. Our problem is an example of a topology optimization problem, and we formulate this problem as a mixed-integer partial-differential equation constrained optimization (MIPDECO) problem, where Maxwell's equation models the propagation of the wave through the cloak and surrounding medium. We use binary variables to model the assignment of the different materials, and their relevant properties (permittivity and density). The mass constraint adds a nontrivial constraint to this problem. We propose a two-phase strategy to solve this problem. In the first phase, we solve a continuous relaxation, and then propose a new variant of the feasibility pump that exploits the structure of the PDE to obtain an initial integral solution candidate. In the second phase, we use a trust-region approach to improve this incumbent. We also consider a continuation or mesh-sequencing approach to find better solutions faster on consecutively finer meshes. We present detailed numerical results to illustrate the effectiveness of our approaches for constructing multi-material cloaks with a mass constraint.
The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend th...
详细信息
The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, we present a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs, which is based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Strategies for filtering product relations are discussed and tested. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. This algorithm is applicable to RLT cuts generated for all types of bilinear terms, including but not limited to the detected implicit products. A detailed computational study based on independent implementations in two solvers evaluates the performance impact of the proposed methods.
This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avo...
详细信息
This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the ap21 (2009), pp. 641--649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5\% more instances to exact optimality and reduce solving times by 26.8\% on the MIPLIB 2017 benchmark test set.
Effective planning of human resources is critical in designing an efficient home healthcare system. In this study, we present a novel home healthcare staffing, routing, and scheduling problem inspired by a real-world ...
详细信息
Effective planning of human resources is critical in designing an efficient home healthcare system. In this study, we present a novel home healthcare staffing, routing, and scheduling problem inspired by a real-world application. The proposed problem addresses a set of patients, with varying daily visit requirements, being served by a set of caregivers with different qualification levels over a multi-day multi-shift planning horizon. The problem aims to minimize the number of extra shifts for caregivers, maximize the allocation of caregivers to emergencies, and minimize the sum of route durations over the planning horizon. These objectives are optimized hierarchically while considering a set of restrictions, including time windows, skill matching, synchronization, care continuity, and labor regulations. To tackle the problem, we introduce a mixed-integer linear programming model. The model is then extended and two sets of valid inequalities are incorporated to enhance its tightness. Computational experiments are conducted on a set of 20 instances. The results highlight the efficiency of the proposed extension in increasing both the number of instances that can be solved to optimality and the number of instances for which a feasible solution is found.
This paper addresses the multi-objective maritime cargo routing and scheduling problem, in which the delivery of bulk products from pickup to delivery ports is served by a heterogeneous fleet of vessels. A mixed integ...
详细信息
This paper addresses the multi-objective maritime cargo routing and scheduling problem, in which the delivery of bulk products from pickup to delivery ports is served by a heterogeneous fleet of vessels. A mixedinteger linear programming (MILP) model is formulated to simultaneously minimize total operation costs, the scheduling makespan, and delays in selected deliveries. The model accounts for several real features, such as time windows, capacity of the vessel's compartments, and ports requirements. A fuzzy weighted max-min method was applied to solve the problem. Two heuristics were developed to effectively handle the complex generated MILP models during the solution process. Experiments were conducted to evaluate the optimization approach using real-life instances provided by a fertilizer company. Finally, a case study shows that the developed model and algorithmic framework are flexible and effective in coping with real problems, incorporating specific business rules from different companies.
With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is of...
详细信息
With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed-integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real-world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.
This paper investigates different factors that affect the performance of containerised transportation in parcel delivery networks. Motivated by challenges confronted by a postal delivery company in Australia, we study...
详细信息
This paper investigates different factors that affect the performance of containerised transportation in parcel delivery networks. Motivated by challenges confronted by a postal delivery company in Australia, we study how container utilisation rate, sortation decisions, and changes in cost parameters can affect the overall performance of a parcel delivery network. Leveraging a combination of mixed-integer programming and machine learning, we model a realistic parcel delivery network and evaluate its performance using data from a major postal service provider. The insights obtained from our analysis offer valuable guidance to parcel delivery companies, empowering them to make informed parcel sortation and containerisation decisions.
作者：
Wallrath, RoderichFranke, MeikWalter, MatthiasUniv Twente
Fac Sci & Technol Sustainable Proc Technol Proc Design & Optimizat Drienerlolaan 5 NL-7522 NB Enschede Netherlands Univ Twente
Fac Elect Engn Math & Comp Sci Appl Math Math Operat Res Drienerlolaan 5 NL-7522 NB Enschede Netherlands
Machine scheduling problems with makespan minimization have been addressed in various academic and industrial fields using mixed-integer programming (MIP). Inmost MIP models, however, the makespan variable is poorly l...
详细信息
Machine scheduling problems with makespan minimization have been addressed in various academic and industrial fields using mixed-integer programming (MIP). Inmost MIP models, however, the makespan variable is poorly linked to the natural date variables of jobs. To address this, we propose novel, strengthening inequalities, derived from the single-machine scheduling polyhedron augmented by a makespan variable. While the associated optimization problem fora single machine is trivial, these inequalities can be applied as cutting planes to more complicated scheduling problems. In this work, we demonstrate their use for non- permutation flow shops. Using the Taillard benchmark set, we analyze the effect of the inequalities on the linear programming relaxations and mixed-integer programs of three commonly used MIP models. The experiments show that the inequalities significantly improve the ability of linear-ordering and time-indexed models to bound the optimum. The positive effect also extends to linear-ordering models with changeover times, demonstrating the potential of these inequalities to improve more general, application-oriented flow shop problems.
Car manufacturers are electrifying their product portfolios as a reaction to restrictions imposed on car emissions. This leads to additional product introductions of battery electric vehicles to the existing portfolio...
详细信息
Car manufacturers are electrifying their product portfolios as a reaction to restrictions imposed on car emissions. This leads to additional product introductions of battery electric vehicles to the existing portfolio of internal combustion engine vehicles. For each introduction, car manufacturers must engineer the corresponding production systems. The engineering of these production systems is executed as projects that consist of designing, building, installing, and testing, requiring different types of engineers. Car manufacturers deploy an engineering workforce and outsource work to engineering service providers. In practice, workforce planning, project planning, and outsourcing are performed sequentially using spreadsheets. However, portfolio electrification increases the complexity of planning, calling for more advanced methods. We formulate an integrated workforce and project planning problem (mixed-integer programme) to minimise outsourcing and perform an experimental study using realistic data representing different prevalent strategies for portfolio electrification. Our approach significantly reduces outsourcing and increases workforce utilisation compared to current industry practice for a wide range of workforce sizes. Furthermore, we investigate the benefit of partially aligning the current practice with our integrated approach. Optimising outsourcing alone while maintaining the sequential planning process reaps 70% to 80% of the potential benefits, and integrating workforce or project planning achieves up to 90%.
Simultaneous topological design and optimization of complex processes that are described by partial differential equations is a challenging but promising research area. Widely adopted nested and sequential approaches ...
详细信息
Simultaneous topological design and optimization of complex processes that are described by partial differential equations is a challenging but promising research area. Widely adopted nested and sequential approaches are mostly applicable based on heuristic solutions, hindering the theoretical improvement potential due to decentralized decision-making in subsequent stages with a significant number of trial-and-error procedures. This study introduces a mixedinteger formulation addressing the governing equations and case-dependent topological constraints at each discretization point, enabling solutions through rigorous solvers under process-related constraints and objectives. Nonlinear expressions in the formulations are further tailored using piecewise linear approximations, still representing the major nonlinear trends through a mixed-integer linear nature to favor global optimality and benefit from computational advancements, when needed. Heat and Stokes flow problems are used as case studies to demonstrate the applicability of the methodology.
暂无评论