Search

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. [ABSTRACT FROM AUTHOR]

We present a new model for finding the optimal placement of electric vehicle charging stations across a multiperiod time frame so as to maximise electric vehicle adoption. Via the use of stochastic discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. We adopt a simulation approach and precompute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Our major contribution is a reformulation into a maximum covering model, which uses the precomputed error terms to calculate the users covered by each charging station. This allows solutions to be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and greedy randomised adaptive search procedure heuristics to obtain good-quality solutions more efficiently. Extensive computational results are provided, and they compare the maximum covering formulation with the current state of the art for both exact solutions and the heuristic methods. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Hydro-Québec and the Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-06054; Collaborative Research and Development Grant CRDPJ 536757–19]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0185. [ABSTRACT FROM AUTHOR]

The increasing penetration of renewable energy sources in the electricity grid brings new operational challenges. This brings up the need for effective means to provide demand response in spite of its distributed nature throughout the grid. Aggregators can be created to manage a set of such demand response resources, but deciding how to allocate an aggregator’s resources is an important problem. One of the aspects that needs more attention is the impact of the transmission system on these decisions. In this paper, we propose a short-term optimization model for allocating demand response(DR) resources as well as generation resources to supply external demand that is offered after the scheduling decision is made. The DR resources will only be available for use after the scheduling decision is made. Finally, our work also considers the impact of congestion in the transmission system when allocating DR. We propose the use of a semidefinite relaxation to provide a good initial point to solve our model with the aim of guaranteeing that we will find an optimal solution. Results from numerical tests with the IEEE 96-RTS and the ACTIVSG500 test grids are reported. We found that DR resources mitigates congestion management, allowing the generators to supply more of the external demand that is offered. Besides that, we observe that using our proposed solution methodology, we were able to obtain optimal solution for both cases studies, which is not the case when solving the original formulation for the ACTIVSG500 grid. [ABSTRACT FROM AUTHOR]

Demand response (DR) has been increasingly growing in significance among the solutions to tackle climate change, by supporting the development of intermittent renewable energy sources in the smart grid. Many models based on mathematical optimization have been developed to address the challenge of supporting residential customers in providing flexibility services to the grid. However, comparing and applying those models is not always straightforward because of particular data handling or specific assumptions. In this work, we take advantage of the common aspects of DR models to build a metamodel, and hence an open source Python library that aims to unify the concepts and the data streaming in and out of the underlying mathematical optimization models. We demonstrate the effectiveness of the metamodel and of the Python library by using it to implement a task scheduler and to optimize the energy consumption for two dwellings. [ABSTRACT FROM AUTHOR]

We present a solution approach for a multi‐trip vehicle routing problem with time windows in which the locations of a prescribed number of depots and the fleet sizes must also be optimized. Given the complexity of the task, we divide the problem into subproblems that are solved sequentially. First, we address strategic decisions, which are solved once and remain constant thereafter. Depots are allocated by solving a p‐median problem and fleet sizes are determined by identifying the vehicle requirements of several worst‐case demand instances. Then, we address the operational planning aspect: optimizing the vehicle routes on a daily basis to satisfy the fluctuating customer demand. We assign customers to depots based on distance and "routing effort," and for the routing problem we combine a tailor‐made branch‐and‐cut algorithm with a heuristic consisting of a route construction phase and packing of routes into vehicle trips. Our strategic decision models are robust in the sense that when applied to unseen data, all customers could be visited with the allocated fleet sizes and depot locations. Our operational routing methods are both time and cost‐effective. The exact method yields acceptable optimality gaps in 20 min and the heuristic runs in less than 2 min, finding optimal or near‐optimal solutions for small instances. Finally, we explore the trade‐off between depot and fleet costs, and routing costs to make recommendations on the optimal number of depots. Our solution approach was entered into the 12th AIMMS‐MOPTA Optimization Modeling Competition and was awarded the first prize. [ABSTRACT FROM AUTHOR]

Near-optimality robustness extends multilevel optimization with a limited deviation of a lower level from its optimal solution, anticipated by higher levels. We analyze the complexity of near-optimal robust multilevel problems, where near-optimal robustness is modelled through additional adversarial decision-makers. Near-optimal robust versions of multilevel problems are shown to remain in the same complexity class as the problem without near-optimality robustness under general conditions. [ABSTRACT FROM AUTHOR]

This paper introduces the algorithmic design and implementation of Tulip, an open-source interior-point solver for linear optimization. It implements a regularized homogeneous interior-point algorithm with multiple centrality corrections, and therefore handles unbounded and infeasible problems. The solver is written in Julia, thus allowing for a flexible and efficient implementation: Tulip's algorithmic framework is fully disentangled from linear algebra implementations and from a model's arithmetic. In particular, this allows to seamlessly integrate specialized routines for structured problems. Extensive computational results are reported. We find that Tulip is competitive with open-source interior-point solvers on the H. Mittelmann's benchmark of barrier linear programming solvers. Furthermore, we design specialized linear algebra routines for structured master problems in the context of Dantzig–Wolfe decomposition. These routines yield a tenfold speedup on large and dense instances that arise in power systems operation and two-stage stochastic programming, thereby outperforming state-of-the-art commercial interior point method solvers. Finally, we illustrate Tulip's ability to use different levels of arithmetic precision by solving problems in extended precision. [ABSTRACT FROM AUTHOR]

This is the editorial for the Special Issue on Energy Networks. [ABSTRACT FROM AUTHOR]

Semidefinite Programming (SDP) is a powerful technique to compute tight lower bounds for Optimal Power Flow (OPF) problems. Even using clique decomposition techniques, semidefinite relaxations are still computationally demanding. However, there are many different clique decompositions for the same SDP problem and they are not equivalent in terms of computation time. In this paper, we propose a new strategy to compute efficient clique decompositions with a clique merging heuristic. This heuristic is based on two different estimates of the computational burden of an SDP problem: the size of the problem and an estimation of a per-iteration cost for a state-of-the-art interior-point algorithm. We compare our strategy with other algorithms on MATPOWER instances and we show a significant decrease in solver time. [ABSTRACT FROM AUTHOR]

The facility layout problem is concerned with finding an arrangement of non-overlapping indivisible departments within a facility so as to minimize the total expected flow cost. In this paper we consider the special case of multi-row layout in which all the departments are to be placed in three or more rows, and our focus is on, for the first time, solutions for large instances. We first propose a new mixed integer linear programming formulation that uses continuous variables to represent the departments' location in both x and y coordinates, where x represents the position of a department within a row and y represents the row assigned to the department. We prove that this formulation always achieves an optimal solution with integer values of y, but it is limited to solving instances with up to 13 departments. This limitation motivates the application of a two-stage optimization algorithm that combines two mathematical optimization models by taking the output of the first-stage model as the input of the second-stage model. This algorithm is, to the best of our knowledge, the first one in the literature reporting solutions for instances with up to 100 departments. [ABSTRACT FROM AUTHOR]

The Time-and-Level-of-Use (TLOU) system is a recently developed approach for electric energy pricing, extending Time-of-Use with an energy capacity that customers can book in advance for a given consumption time. We define a bilevel optimization model for determining the pricing parameters of TLOU, maximizing the supplier revenue while anticipating an optimal reaction of the customer. A solution approach is built, based on the discrete finite set of optimality candidates of the lower-level customer problem. [ABSTRACT FROM AUTHOR]

With the increasing presence of renewable energy sources in the electrical power grid, demand response via thermostatic appliances such as electric water heaters is a promising way to compensate for the significant variability in renewable power generation. We propose a multistage stochastic optimization model that computes the optimal day-ahead target profile of the mean thermal energy contained in a large population of heaters, given various possible wind power production and uncontrollable load scenarios. This optimal profile is calculated to make the variable net demand as even as possible. [ABSTRACT FROM AUTHOR]

We study demand-side participation in an electricity market for an industrial consumer of electricity, with some flexibility to reduce demand, and capable of offering interruptible load reserve. Our consumer is a price maker, and the impact of its actions in the market is modelled via a bi-level optimization problem. We have extended a standard model for optimal strategic consumption, to the case where reserve offer curves need to be optimized simultaneously with consumption curves; our models provide intuition into this interaction. Furthermore, we provide tailor-made solution strategies for the resulting problems under uncertainty, and report numerical results of our implementation on instances over the full New Zealand network yielding a realistic and large problem set. [ABSTRACT FROM AUTHOR]

The optimal reactive power dispatch (ORPD) problem is an alternating current optimal power flow (ACOPF) problem where discrete control devices for regulating the reactive power, such as shunt elements and tap changers, are considered. The ORPD problem is modeled as a mixed-integer nonlinear optimization problem and its complexity is increased compared to the ACOPF problem, which is highly nonconvex and generally hard to solve. Recently, convex relaxations of the ACOPF problem have attracted a significant interest since they can lead to global optimality. We propose a tight conic relaxation of the ORPD problem and show that a round-off technique applied with this relaxation leads to near-global optimal solutions with very small guaranteed optimality gaps, unlike with the nonconvex continuous relaxation. We report computational results on selected MATPOWER test cases with up to 3375 buses. [ABSTRACT FROM AUTHOR]

Summary: Smart homes have the potential to achieve optimal energy consumption with appropriate scheduling. The control of smart appliances can be based on optimization models, which should be realistic and efficient. However, increased realism also implies an increase in solution time. Many of the optimization models in the literature have limitations on the types of appliances considered and/or their reliability. This paper proposes a home energy management scheduling model that is more realistic and efficient. We develop a mixed integer linear optimization model that minimizes the energy cost while maintaining a given level of user comfort. Our main contribution is the variety of specific appliance models considered and their integration into a single model. We consider the use of energy in appliances and electric vehicles (EVs) and take into account renewable local generation, batteries, and demand response. Our models of a shower, a fridge, and a hybrid EV consider both the electricity consumption and the conventional fuel cost. We present computational results to validate the model and indicate how it overcomes the limitations of other models. Our results, compared with the best competitors, provide cost savings ranging from 8% to 389% over a horizon of 24 hours. [ABSTRACT FROM AUTHOR]

We study equilibria in traffic networks and in power system networks with storage in the presence of logic constraints. These constraints consist of binary variables that are added to complementarity-based equilibrium models. Although these models have been thoroughly studied, the addition of logic constraints can provide additional benefits for practical applications. The main contribution of this work is to demonstrate, using two specific examples of applications, that logic constraints can render classical equilibrium models more realistic by allowing the inclusion of useful features such as equity in network flows or threshold events. Specifically, for the traffic equilibrium problem, we show how logic constraints can introduce some equity in the assignment of traffic when more than one equilibrium exists. For power system networks, we show that the presence of a storage operator acting as a service provider will not only support the operation of a power grid, but will also help stabilise the price of electricity and avoid the well-documented price-shifting effect. Unlike previous works, our model considers the storage operator as a service provider rather than a competitor to the producers. We also consider the minimum power output of production. We present results illustrating the expanded capabilities and insights provided by these new paradigms. [ABSTRACT FROM AUTHOR]

Demand-response aggregators are faced with the challenge of how to best manage numerous and heterogeneous distributed energy resources (DERs). This paper proposes a decentralized methodology for optimal coordination of DERs. The proposed approach is based on Dantzig–Wolfe decomposition and column generation, thus allowing to integrate any type of resource whose operation can be formulated within a mixed-integer linear program. We show that the proposed framework offers the same guarantees of optimality as a centralized formulation, with the added benefits of distributed computation, enhanced privacy, and higher robustness to changes in the problem data. The practical efficiency of the algorithm is demonstrated through extensive computational experiments, on a set of instances generated using data from Ontario energy markets. The proposed approach was able to solve all test instances to proven optimality, while achieving significant speed-ups over a centralized formulation solved by state-of-the-art optimization software. [ABSTRACT FROM AUTHOR]

The classical alternating current optimal power flow problem is highly nonconvex and generally hard to solve. Convex relaxations, in particular semidefinite, second-order cone, convex quadratic, and linear relaxations, have recently attracted significant interest. The semidefinite relaxation is the strongest among them and is exact for many cases. However, the computational efficiency for solving large-scale semidefinite optimization is lower than for second-order cone optimization. We propose a conic relaxation obtained by combining semidefinite optimization with the reformulation-linearization technique, commonly known as RLT. The proposed relaxation is stronger than the second-order cone relaxation and nearly as tight as the standard semidefinite relaxation. Computational experiments using standard test cases with up to 6515 buses show that the time to solve the new conic relaxation is up to one order of magnitude lower than for the chordal relaxation, a semidefinite relaxation technique that exploits the sparsity of power networks. [ABSTRACT FROM AUTHOR]

Maintenance activities help prevent costly generator breakdowns but because generators under maintenance are typically unavailable, the impact of maintenance schedules is significant and their cost must be accounted for when planning maintenance. In this paper, we address the generator maintenance scheduling problem in hydropower systems. We propose a mixed-integer programing model that considers the time windows of the maintenance activities, as well as the nonlinearities and disjunctions of the hydroelectric production functions. Because the resulting model is hard to solve, we also propose an extended formulation, a set reduction approach that uses logical conditions for excluding unnecessary set elements from the model, and valid inequalities. We performed computational experiments using a variety of instances adapted from a real hydropower system in Canada, and the extended formulation with set reduction achieved the best results in terms of computational time and optimality gap. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses articles in the issue on topics including global optimization, mathematical optimization, and linear optimization.

We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study of four classes of inequalities from the literature: clique, general clique, wheel and bicycle wheel. We considered 10 combinations of these classes and tested them on both dense and sparse instances for k∈{3,4,5,7}. Our computational results suggest that the bicycle wheel and wheel are the strongest inequalities for k=3, and that for k∈{4,5,7} the wheel inequalities are the strongest by far. Furthermore, we observe an improvement in the performance for all choices of k when both bicycle wheel and wheel are used, at the cost of 72% more CPU time on average when compared with using only one of them. [ABSTRACT FROM AUTHOR]

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research. [ABSTRACT FROM AUTHOR]

Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that are based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and stable-set problems. Each level k of the proposed hierarchy consists of the basic semidefinite relaxation of the problem augmented by the constraints enforcing the structural projection condition on every k-node subgraph of the problem. This hierarchy has the distinguishing feature that all the relaxations are formulated in the space of the original semidefinite relaxation. Because the size of the relaxations increases rapidly with the number of subgraphs, we explore the possibility of adding the projection constraints only for selected subgraphs. Preliminary computational results show that the proposed hierarchy yields improved bounds when compared to the initial relaxation for benchmark instances of the max-cut and stable-set problems, and that the improved bounds result in significantly smaller enumeration trees when the relaxation is used in a branch-and-bound scheme. [ABSTRACT FROM AUTHOR]

This paper presents a system architecture for load management in smart buildings which enables autonomous demand side load management in the smart grid. Being of a layered structure composed of three main modules for admission control, load balancing, and demand response management, this architecture can encapsulate the system functionality, assure the interoperability between various components, allow the integration of different energy sources, and ease maintenance and upgrading. Hence it is capable of handling autonomous energy consumption management for systems with heterogeneous dynamics in multiple time-scales and allows seamless integration of diverse techniques for online operation control, optimal scheduling, and dynamic pricing. The design of a home energy manager based on this architecture is illustrated and the simulation results with Matlab/Simulink confirm the viability and efficiency of the proposed framework. [ABSTRACT FROM PUBLISHER]

This paper examines the polytope of feasible power generation schedules in the unit commitment (UC) problem. We provide computational results comparing formulations for the UC problem commonly found in the literature. We introduce a new class of inequalities, giving a tighter description of feasible operating schedules for generators. Computational results show that these inequalities can significantly reduce overall solution times. [ABSTRACT FROM PUBLISHER]

The minimum k-partition (M kP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) for the M kP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the M kP problem. We compare ICH to the hyperplane rounding techniques of Goemans and Williamson and of Frieze and Jerrum, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the M kP problem. ICH is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-bound tree. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing a fast exact approach for k≥3. [ABSTRACT FROM AUTHOR]

Despite the many advantages of interior-point algorithms over active-set methods for linear optimization, one of the remaining practical challenges is their current limitation to efficiently solve series of related problems by an effective warmstarting strategy. As a remedy, in this paper we present a new infeasible-interior-point approach to quickly reoptimize an initial problem instance after data perturbations, or a new linear programming relaxation after adding cutting planes for discrete or combinatorial problems. Based on the detailed complexity analysis of the underlying algorithm, we perform a comparative analysis to coldstart initialization schemes and present encouraging computational results with iteration savings of around 50% on average for perturbations of the Netlib linear programs (LPs) and successive linear programming relaxations of max-cut and the traveling salesman problem. [ABSTRACT FROM AUTHOR]

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) interactions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to 30 facilities. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988. [ABSTRACT FROM AUTHOR]

In VLSI layout, floorplanning refers to the task of placing macrocells on a chip without overlap while minimizing design objectives such as timing, congestion, and wire length. Experienced VLSI designers have traditionally been able to produce more efficient floorplans than automated methods. However, with the increasing complexity of modern circuits, manual design flows have become infeasible. An efficient top-down strategy for overlap removal which repairs overlaps in floorplans produced by placement algorithms or rough floorplanning methodologies is presented in this article. The algorithmic framework proposed incorporates a novel geometric shifting technique coupled with topological constraint graphs and linear programming within a top-down flow. The effectiveness of this framework is quantified across a broad range of floorplans produced by multiple tools. The method succeeds in producing valid placements in almost all cases; moreover, compared with leading methods, it requires only one-fifth of the run-time and produces placements with 4-13% less wire length and up to 43% less cell movement. [ABSTRACT FROM AUTHOR]

This paper proposes a two-level framework for the operation of a competitive market for reactive power ancillary services. It is argued that the first-level, i.e., reactive power procurement, be on a seasonal basis while the second-level, i.e., reactive power dispatch, be close to real-time operation. To this effect, a reactive power procurement market model is proposed here taking into consideration system security aspects. This procurement procedure is based on a two-step optimization model. First, the marginal benefits of reactive power supply from each provider with respect to system security are obtained by solving an optimal power flow (OPF) that maximizes system loadability subject to transmission security constraints imposed by voltage limits, thermal limits, and stability limits. Second, the selected set of generators is then determined by solving an OPF-based auction to maximize a societal advantage function comprising generators' offers and their corresponding marginal benefits with respect to system security, considering all transmission system constraints. The proposed procedure yields the selected set of generators and zonal price components, which would form the basis for seasonal contracts between the system operator and the selected reactive power service providers. [ABSTRACT FROM AUTHOR]

The article focuses on several studies related to the concepts of satisfiability, Boolean modeling and computation. One study described disjunctive normal form (DNF) tautologies with terms conflicting in one or two variables pairwise and possessing a tree-like structure. Another study proposed a semidefinite programming relaxation for the satisfiability problem. A third study discussed theoretical and experimental results on the use of satisfiability problem (SAT) algorithms for colouring special classes of graphs.

We revisit a regularization technique of Mészáros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed regularization is able to achieve the same or significantly better accuracy over standard options of splitting variables, using a quadratic cone, and solving indefinite systems. [ABSTRACT FROM AUTHOR]

An affine supply function equilibrium (SFE) approach is used to discuss voltage constraints and reactive power issues in the modeling of strategic behavior. Generation companies (GenCos) can choose their bid parameters with no restrictions for both energy and spinning reserves. The strategic behavior of generators is formulated as a multi-leader single-follower game. Each GenCo is modeled as a leader, while the central market operator running a cost minimization process is the sole follower. An ac model is considered to represent the transmission system. A three-node system is used to illustrate several cases, and study the implications of the incentives of the strategic players to exploit active and reactive power, and spinning reserves in order to maximize profits. Results for a 14-node system are also presented. [ABSTRACT FROM AUTHOR]

In this paper, oligopolistic competition in a centralized power market is characterized by a multi-leader single-follower game, and formulated as a nonlinear programming (NLP) problem. An ac network is used to represent the transmission system and is modeled using rectangular coordinates. The follower is composed of a set of competitive suppliers, demands, and the system operator, while the leaders are the dominant suppliers. The ac approach allows one to capture the strategic behavior of suppliers regarding not only active but also reactive power. In addition, the impact of voltage and apparent power flow constraints can be analyzed. Different case studies are presented using a three-node system to highlight the features of the formulation. Results on a 14-node system are also presented. [ABSTRACT FROM AUTHOR]

We present a new framework for efficiently finding competitive solutions for the facility-layout problem. This framework is based on the combination of two new mathematical-programming models. The first model is a relaxation of the layout problem and is intended to find good starting points for the iterative algorithm used to solve the second model. The second model is an exact formulation of the facility-layout problem as a nonconvex mathematical program with equilibrium constraints (MPEC). Aspect ratio constraints, which are frequently used in facility-layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are easily incorporated into this new framework. Finally, we present computational results showing that the complete framework can be solved efficiently using widely available optimization software, and the resulting layouts improve on those obtained using previous approaches in the literature. Moreover, the framework can be used to find different competitive layouts with relatively little computational effort, which is advantageous for a user who wishes to consider several competitive layouts rather than simply using a mathematically optimal layout. [ABSTRACT FROM AUTHOR]

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variableXis maximized (or minimized) subject to linear constraints on the elements ofXand the additional constraint thatXbe positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of “higher liftings” for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims. [ABSTRACT FROM AUTHOR]

This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in conjunctive normal form. We propose a new SDP relaxation for 3-SAT and prove some of its theoretical properties. We also show that, together with two SDP relaxations previously proposed in the literature, the new relaxation completes a trio of linearly sized relaxations with increasing rank-based guarantees for proving satisfiability. A comparison of the relative practical performances of the SDP relaxations shows that, among these three relaxations, the new relaxation provides the best tradeoff between theoretical strength and practical performance within an enumerative algorithm. [ABSTRACT FROM AUTHOR]

The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying height and width) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard combinatorial optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distances that arise in this derivation. Computational results demonstrating the potential of our approach are presented. [ABSTRACT FROM AUTHOR]