The Conditional Preference Network (CP-net) graphically represents the user's qualitative and conditional preference statements under the ceteris paribus interpretation. The constrained CP-net extends the CP-net to a set of hard constraints. The constrained CP-net can help represent and solve real-world applications where the goal is to select one or more scenarios that are feasible according to constraints while maximizing
user's preferences.

Existing algorithms for solving the constrained CP-net require expensive
dominance testing operations. To overcome this challenge in practice, we propose several efficient solving approaches. In our first approach, we alter the constrained CP-net by eliciting additional relative importance statements between variables to have a total order over the outcomes. This new model is the constrained Relative Importance Network (constrained CPR-net). Consequently, we show that the constrained CPR-net has one optimal outcome (assuming the constrained CPR-net is consistent) that we can obtain without dominance testing. In our second solution, we extend the Lexicographic Preference Tree (LP-tree) to a set of constraints. Then, we propose a recursive backtrack search algorithm to find the most preferable outcome. We show that the first feasible outcome returned by Search-LP (without dominance testing) is also preferable to any other feasible outcome. Finally, in our third solution, we preserve the semantics of the CP-net and propose a variant of the branch-and-bound algorithm improved with look-ahead strategies and variable ordering heuristics. A divide-and-conquer variant of the branch-and-bound algorithm is also explored as an alternative method.

We study a general class of interdiction games that model an adversarial, finite, sequential, and alternating interaction between two decision-makers—i.e., an attacker and a defender. A prototypical example of these types of games consists of a three-stage defender-attacker-defender problem in which the defender conducts a set of fortification strategies during the first stage to protect its operation from the attacker's course of actions; in the second stage, the attacker deploys a set of disruptive attacks, parameterized by the fortification strategies, to optimally deteriorate the defender's operational objective; finally, in the third stage, the defender optimizes their operation, considering the effects of the previous stages.

We focus on a general variation in which there is a direct (and possibly disruptive) interaction between the actions taken by non-consecutive rounds. For example, in the three-stage game described before, we consider instances in which actions made by the defender in the first stage may also turn solutions for the defender's operation in the third stage infeasible. General applications of these games arise in problems with an underlying network structure, where the defender can alter the composition of the network in the first stage by adding/removing edges and vertices. In this presentation, we develop an exact solution framework for these problems based on a combinatorial branch-and-bound search. We provide some examples of applications arising from communications and network design problems.

In this presentation, we study sparse factorization of the (scaled) square all-ones matrix $J$ of arbitrary order. We introduce the concept of hierarchically banded matrices and propose two types of hierarchically banded factorization of $J$: the reduced hierarchically banded (RHB) factorization and the doubly stochastic hierarchically banded (DSHB) factorization. Based on the DSHB factorization, we propose the sequential doubly stochastic (SDS) factorization, in which~$J$ is decomposed as a product of sparse, doubly stochastic matrices. Finally, we discuss the application of the proposed sparse factorizations to the decentralized average consensus problem and decentralized optimization.

This talk introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories. Two binary programming models are introduced, both of which incorporate path-based node-to-edge distances to reflect road travel. The first model requires an exponential number of cut set-based constraints to model contiguity; it is paired with a separation scheme that usually generates only a small number of these constraints, namely, a branch-and-cut (B&C) algorithm. The second model utilizes a polynomial number of shortest-path constraints to model contiguity and can be solved with off-the-shelf solvers. The two solution approaches associated with the proposed models are tested on road networks with over 2,700 nodes and close to 3,400 edges, yielding models with over 9.6 million binary variables. Solving the model based on shortest path contiguity (SPC) constraints via standard branch and bound attains speedups in computational time of up to 52x relative to the cut set-based B&C implementation. In addition, the SPC constraints are demonstrated to be non-valid logic cuts of the edge-based p-median (EpM) model (i.e., for which contiguity is not explicitly required), meaning that they cut off integer feasible but non-optimal solutions of this simpler problem. Finally, the talk explores structural insights and connections between ECpM and the edge-based districting (EBD) problem, which enforces an additional planning criterion (work balance). An existing model that utilizes cut set-based contiguity constraints was unable to find a feasible solution within 12 hours for all instances, while the new EBD model with SPC constraints was able to solve most of the feasible instances to optimality.