Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

\(\) We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute … Read more

Column Elimination for Capacitated Vehicle Routing Problems

We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

Evaluation of Political Redistricting in Japan by Optimization and Enumeration

The political/electoral districting problem for the single-seat constituency system is a problem of decomposing a graph into connected components of a given number of seats under several conditions and objectives. We evaluate and analyze the current division of single-seat constituencies for the House of Representatives using optimization and enumeration. The objective function is to minimize … Read more

Multithread Interval Scheduling with Flexible Machine Availabilities: Complexity and Efficient Algorithms

In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specic time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more

A worst-case complexity analysis for Riemannian non-monotone line-search methods

In this paper we deal with non-monotone line-search methods to minimize a smooth cost function on a Riemannian manifold. In particular, we study the number of iterations necessary for this class of algorithms to obtain e-approximated stationary points. Specifically, we prove that under a regularity Lipschitz-type condition on the pullbacks of the cost function to … Read more

Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program

\(\) We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first one is for determining an optimal solution and the second one is for finding an optimal value. The first category of conditions includes the existence of a … Read more

On Supervalid Inequalities for Binary Interdiction Games

Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction … Read more

Nonexpansive Markov Operators and Random Function Iterations for Stochastic Fixed Point Problems

We study the convergence of random function iterations for finding an invariant measure of the corresponding Markov operator. We call the problem of finding such an invariant mea- sure the stochastic fixed point problem. This generalizes earlier work studying the stochastic feasibility problem, namely, to find points that are, with probability 1, fixed points of … Read more

A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport

We investigate a class of generalized Nash equilibrium problems (GNEPs) in which the objectives of the individuals are interdependent and the shared constraint consists of a system of partial differential equations. This setup is motivated by the modeling of strategic interactions of competing firms, which explicitly take into account the dynamics of transporting a commodity, … Read more

A Radial Basis Function Method for Noisy Global Optimisation

We present a novel response surface method for global optimisation of an expensive and noisy (black-box) objective function, where error bounds on the deviation of the observed noisy function values from their true counterparts are available. The method is based on the well-established RBF method by Gutmann (2001a,c) for minimising an expensive and deterministic objective … Read more