Interactive gender inference aims to infer the genders of the two involved users in a communication from the interactive text. In this paper, we address this task by proposing a joint inference approach which well incorporates label correlations among the instances. Specifically, an Integer Linear Programming (ILP) approach is proposed to achieve global optimization with various kinds of intra-task and extra-task constraints. Empirical studies demonstrate the effectiveness of the proposed ILP-based approach to interactive gender inference.

Many robotic tasks require solutions that maximize multiple performance objectives. For example, in path-planning, these objectives often include finding short paths that avoid risk and maximize the information obtained by the robot. Although there exist many algorithms for multiobjective optimization, few of these algorithms apply directly to robotic path-planning and fewer still are capable of finding the set of Pareto optimal solutions. We present the MORRF*(Multi-Objective Rapidly exploring Random Forest*) algorithm, which blends concepts from two different types of algorithms from the literature: Optimal rapidly exploring random tree (RRT*) for efficient path finding and a decomposition-based approach to multi-objective optimization. The random forest uses two types of tree structures: a set of reference trees and a set of subproblem trees. We present a theoretical analysis that demonstrates that the algorithm asymptotically produces the set of Pareto optimal solutions, and use simulations to demonstrate the effectiveness and efficiency of MORRF* in approximating the Pareto set.

Pareto optimization solves a constrained optimization task by reformulating the task as a bi-objective problem. Pareto optimization has been shown quite effective in applications; however, it has little theoretical support. This work theoretically compares Pareto optimization with a penalty approach, which is a common method transforming a constrained optimization into an unconstrained optimization. We prove that on two large classes of constrained Boolean optimization problems, minimum matroid optimization (P-solvable) and minimum cost coverage (NP-hard), Pareto optimization is more efficient than the penalty function method for obtaining the optimal and approximate solutions, respectively. Furthermore, on a minimum cost coverage instance, we also show the advantage of Pareto optimization over a greedy algorithm.

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e.g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.

Continuous optimization is an important problem in many areas of AI, including vision, robotics, probabilistic inference, and machine learning. Unfortunately, most real-world optimization problems are nonconvex, causing standard convex techniques to find only local optima, even with extensions like random restarts and simulated annealing. We observe that, in many cases, the local modes of the objective function have combinatorial structure, and thus ideas from combinatorial optimization can be brought to bear. Based on this, we propose a problem-decomposition approach to nonconvex optimization. Similarly to DPLL-style SAT solvers and recursive conditioning in probabilistic inference, our algorithm, RDIS, recursively sets variables so as to simplify and decompose the objective function into approximately independent sub-functions, until the remaining functions are simple enough to be optimized by standard techniques like gradient descent. The variables to set are chosen by graph partitioning, ensuring decomposition whenever possible. We show analytically that RDIS can solve a broad class of nonconvex optimization problems exponentially faster than gradient descent with random restarts. Experimentally, RDIS outperforms standard techniques on problems like structure from motion and protein folding.

We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, which, to the best of our knowledge, is the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments on a suite of PPDDL problems augmented with constraints show that these features enable i-dual to achieve up to two orders of magnitude improvement in run-time and memory over linear programming algorithms.

In this work, we investigate a multi-period Home Health Care Scheduling Problem (HHCSP) under stochastic service and travel times. We first model the deterministic problem as an integer linear programming model that incorporates real-world requirements, such as time windows, continuity of care, workload fairness, inter-visit temporal dependencies. We then extend the model to cope with uncertainty in durations, by introducing chance constraints into the formulation. We propose efficient solution approaches, which provide quantifiable near-optimal solutions and further handle the uncertainties by employing a sampling-based strategy. We demonstrate the effectiveness of our proposed approaches on instances synthetically generated by real-world dataset for both deterministic and stochastic scenarios.

For example, we may need to (i) perform inverse learning of the cost parameters of a multi-objective reward based on observed agent behavior; (ii) perform sensitivity analyses of policies to various parameter settings; or (iii) analyze and optimize policy performance as a function of policy parameters. When such problems have mixed discrete and continuous state and/or action spaces, this leads to parameterized hybrid MDPs (PHMDPs) that are often approximately solved via discretization, sampling, and/or local gradient methods (when optimization is involved). In this paper we combine two recent advances that allow for the first exact solution and optimization of PHMDPs. We first show how each of the aforementioned use cases can be formalized as PHMDPs, which can then be solved via an extension of symbolic dynamic programming (SDP) even when the solution is piecewise nonlinear. Secondly, we can leverage recent advances in non-convex solvers that require symbolic forms of the objective function for non-convex global optimization in (i), (ii), and (iii) using SDP to derive symbolic solutions for each PHMDP formalization. We demonstrate the efficacy and scalability of our optimal analytical framework on nonlinear examples of each of the aforementioned use cases.

Last-mile transportation (LMT) refers to any service that moves passengers from a hub of mass transportation (MT), such as air, boat, bus, or train, to destinations, such as a home or an office. In this paper, we introduce the problem of scheduling passengers jointly on MT and LMT services, with passengers sharing a car, van, or autonomous pod of limited capacity for LMT. Passenger itineraries are determined so as to minimize total transit time for all passengers, with each passenger arriving at the destination within a specified time window. The transit time includes the time spent traveling through both services and, possibly, waiting time for transferring between the services. We provide an integer linear programming (ILP) formulation for this problem. Since the ILMTP, is NP-hard and problem instances of practical size are often difficult to solve, we study a restricted version where MT trips are uniform, all passengers have time windows of a common size, and LMT vehicles visit one destination per trip. We prove that there is an optimal solution that sorts and groups passengers by their deadlines and, based on this result, we propose a constructive grouping heuristic and local search operators to generate high-quality solutions. The resulting groups are optimally scheduled in a few seconds using another ILP formulation. Numerical results indicate that the solutions obtained by this heuristic are often close to optimal %, even when multiple destinations are allowed per group, and that warm-starting the ILP solver with such solutions decreases the overall computational times significantly.

Abduction is a form of inference that seeks the best explanation for the given observation. Because it provides a reasoning process based on background knowledge, it is used in applications that need convincing explanations. In this study, we consider weighted abduction, which is one of the commonly used mathematical models for abduction. The main difficulty associated with applying weighted abduction to real problems is its computational complexity. A state-of-the-art method formulates weighted abduction as an integer linear programming (ILP) problem and solves it using efficient ILP solvers; however, it is still limited to solving problems that include at most 100 rules of background knowledge and observations.