[en] This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110-1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p element of [0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε)

[en] Presented here is a novel algorithm for scheduling the observations of time-domain imaging surveys. Our integer linear programming approach optimizes an observing plan for an entire night by assigning targets to temporal blocks, enabling strict control of the number of exposures obtained per field and minimizing filter changes. A subsequent optimization step minimizes slew times between each observation. Our optimization metric self-consistently weights contributions from time-varying airmass, seeing, and sky brightness to maximize the transient discovery rate. We describe the implementation of this algorithm on the surveys of the Zwicky Transient Facility and present its on-sky performance.

[en] A collection of programs written in FORTRAN and ASSEMBLER programming languages used in DOS-IBM is presented. The problems solved are of different sorts: linear programming, integration, matrix calculus, computation of absorbed doses in teletherapy, data sets (files) on magnetic tapes and disks, completion of DOS operating system etc. For reasons of space no details are given on the numerical methods or supplements and devices developed in order to achieve superior programs as to computation time and accuracy of result, although these might have been of use. All the programs in the collection have been checked up on an IBM 370/135 computer. (author)

[en] Petrologists are increasingly turning to the results of phase equilibrium studies to estimate thermochemical data and mixing properties of solids, gases and solutions. Most estimates are obtained by linear regression of phase equilibria data, a method which assumes that the equilibrium conditions (T,P,X) are known. The use of linear programming allows for a more rigorous mathematical treatment of phase equilibria data. In constrast to linear regression, which provides a unique fit that tends towards the midpoints of experimental brackets while not ensuring consistency with all brackets, linear programming ensures consistency with all experimental data, but provides a range of solutions, which can be unique only for a given objective function. Any new experimental data should be added to the existing thermodyamics data base and all of the data should be retested for internal consistency. This process of updating and the calculation of new phase relationships can be completed in a relatively short time because of the power and efficiency of the linear programming method. 10 refs

[en] We propose a systematic method for constructing a sparse data reconstruction algorithm in compressed sensing at a relatively low computational cost for general observation matrix. It is known that the cost of ℓ₁-norm minimization using a standard linear programming algorithm is O(N³). We show that this cost can be reduced to O(N²) by applying the approach of posterior maximization. Furthermore, in principle, the algorithm from our approach is expected to achieve the widest successful reconstruction region, which is evaluated from theoretical argument. We also discuss the relation between the belief propagation-based reconstruction algorithm introduced in preceding works and our approach

[en] Influence Maximization is one of the important research topics in social networks which has many applications, e.g., in marketing, politics and social science. The goal of Influence Maximization is to select a limited number of vertices (called seed set) in a social graph, so that upon their direct activation, the maximum number of vertices is activated through social interaction of the seed set with the other vertices. Social interaction is modeled by diffusion models among which Linear Threshold Model is one of the most popular ones. In Linear Threshold Model, influence of nodes on each other is quantized by edge weights and nodes have a threshold for activation. If sum of the influence of activated neighbors of a node reaches a certain threshold, the node is activated. When thresholds are fixed, Influence Maximization reduces to Target Set Selection Problem. Ackerman et al. solved Target Set Selection Problem by Integer Linear Programming. In this paper, we analyze their work and show that their method cannot properly solve the problem in specific situations, e.g., when graph has cycle. We fix this problem and propose a new method based on Integer Linear Programming and show in the results that our method can handle graphs with cycles as well.

[en] Highlights: • A distribution network partitioning method for DSE is developed. • An optimal PMUs and communication links placement model for DSE is proposed. • Both the bandwidth cost and length cost of communication links are considered. -- Abstract: With the expansion in scale and complexity of distribution networks, distributed state estimation (DSE), a real-time database for other on-line applications, is becoming popular for large-scale active distribution networks (ADN). Measurements from phasor measurement units (PMUs) with the same time stamp can assist DSE to obtain faster and more accurate estimation; however, the configuration of PMUs and communication links should be updated to support data collection and transmission. This paper proposes an optimal PMUs and communication links placement method for DSE in distribution networks. A network partitioning method is presented with the aim of balancing calculation times among subareas. Then, a binary integer linear programming model that simultaneously considers the optimal placement of PMUs, phasor data concentrators (PDCs) and communication links is proposed. The economy of the configuration scheme is guaranteed on the premise that the network is fully observable. Finally, case studies on the IEEE 33-node, PG&E 69-node and IEEE 123-node systems verify the feasibility of the proposed method.

[en] Purpose: The CyberKnife delivers a large number of beams originating at different non-planar positions and with different orientation. We study how much the quality of treatment plans depends on the beams considered during plan optimization. Particularly, we evaluate a new approach to search for optimal treatment plans in parallel by running optimization steps concurrently. Methods: So far, no deterministic, complete and efficient method to select the optimal beam configuration for robotic SRS/SBRT is known. Considering a large candidate beam set increases the likelihood to achieve a good plan, but the optimization problem becomes large and impractical to solve. We have implemented an approach that parallelizes the search by solving multiple linear programming problems concurrently while iteratively resampling zero weighted beams. Each optimization problem contains the same set of constraints but different variables representing candidate beams. The search is synchronized by sharing the resulting basis variables among the parallel optimizations. We demonstrate the utility of the approach based on an actual spinal case with the objective to improve the coverage. Results: The objective function is falling and reaches a value of 5000 after 49, 31, 25 and 15 iterations for 1, 2, 4, and 8 parallel processes. This corresponds to approximately 97% coverage in 77%, 59%, and 36% of the mean number of iterations with one process for 2, 4, and 8 parallel processes, respectively. Overall, coverage increases from approximately 91.5% to approximately 98.5%. Conclusion: While on our current computer with uniform memory access the reduced number of iterations does not translate into a similar speedup, the approach illustrates how to effectively parallelize the search for the optimal beam configuration. The experimental results also indicate that for complex geometries the beam selection is critical for further plan optimization

[en] Highlights: • Real-world instances of the Hydro Unit Commitment problem present several sources of infeasibility. • Method to analyze and classify the feasibility issues. • 2-stage approach to solve the problem while minimizing the violation of strategic constraints. • Computational results show the effectiveness to recover feasibility. -- Abstract: This article deals with feasibility issues of the hydro-unit commitment relative to units along a valley in the price-taker revenue-maximizing setting. The problem is formulated as a mixed-integer linear programming model. Besides physical constraints, we consider two additional specifications that apply to a subset of units and reservoirs within a valley, namely the power-flow curves of each unit feature discrete operational points and each reservoir level should meet target volumes. These specifications, together with the standard issues affecting real-world data, make our problem harder to solve, often infeasible. We follow a step-by-step approach to identify and repair one source of infeasibility at a time, namely numerical errors and model infeasibilities. The former is analyzed and fixed through tools like an exact solver and a model and data preprocessing. The remaining infeasibilities are eliminated with a 2-stage method. In the first stage, a minimal deviation from target volumes, i.e., strategic, thus relaxable, constraints, is computed to make the problem feasible. In the second stage, the original problem is solved with a possible deviation from the target volumes as defined in the first stage. Computational results confirm the effectiveness of the proposed method to recover feasibility on a challenging real-world test set.

[en] Short communication