Search

Pseudo-Boolean (PB) constraints are highly expressive, and many combinatorial optimization problems can be modeled using pseudo-Boolean optimization (PBO). It is recognized that stochastic local search (SLS) is a powerful paradigm for solving combinatorial optimization problems, but the development of SLS for solving PBO is still in its infancy. In this paper, we develop an effective SLS algorithm for solving PBO, dubbed NuPBO, which introduces a novel scoring function for PB constraints and a new weighting scheme. We conduct experiments on a broad range of six public benchmarks, including three real-world benchmarks, a benchmark from PB competition, an integer linear programming optimization benchmark, and a crafted combinatorial benchmark, to compare NuPBO against five state-of-the-art competitors, including a recently-proposed SLS PBO solver LS-PBO, two complete PB solvers PBO-IHS and RoundingSat, and two mixed integer programming (MIP) solvers Gurobi and SCIP. NuPBO has been exhibited to perform best on these three real-world benchmarks. On the other three benchmarks, NuPBO shows competitive performance compared to state-of-the-art competitors, and it significantly outperforms LS-PBO, indicating that NuPBO greatly advances the state of the art in SLS for solving PBO.

This work is dedicated to improving local search solvers for the Boolean satisfiability (SAT) problem on structured instances. We propose a construct-and-cut (CnC) algorithm based on unit propagation, which is used to produce initial assignments for local search. We integrate our CnC initialization procedure within several state-of-the-art local search SAT solvers, and obtain the improved solvers. Experiments are carried out with a benchmark encoded from a spectrum repacking project as well as benchmarks encoded from two important mathematical problems namely Boolean Pythagorean Triple and Schur Number Five. The experiments show that the CnC initialization improves the local search solvers, leading to better performance than state-of-the-art SAT solvers based on Conflict Driven Clause Learning (CDCL) solvers.

The demand of electricity keeps increasing in this modern society and the behavior of customers vary greatly from time to time, city to city, type to type, etc. Generally, buildings are classified into residential, commercial and industrial. This study is aimed to distinguish the types of residential buildings in Singapore and establish a mathematical model to represent and model the load profile of each type. Modeling household energy consumption is the first step in exploring the possible demand response and load reduction opportunities under the smart grid initiative. Residential electricity load profiling includes the details on the electrical appliances, its energy requirement, and consumption pattern. The model is generated with a bottom-up load model. Simulation is performed for daily load profiles of 1 or 2 rooms, 3 rooms, 4 rooms and 5 rooms public housing. The simulated load profile is successfully validated against the measured electricity consumption data, using a web-based Customer Energy Portal (CEP) at the campus housings of Nanyang Technological University, Singapore.