Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization using special ordered sets and mixed-integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm for optimizing a separable discontinuous PLF over a closed convex set. It offers slim and sparse linear programming relaxations, sharpness throughout the search tree, and an increased flexibility in branching decisions. The main feature of our algorithm is the generation of convex underestimators at the root node of the search tree and their quick and efficient updates at each node after branching. Convergence to the global optimum is achieved when the PLFs are lower semicontinuous. A Python implementation of our algorithm is tested on knapsack and network flow problems for both continuous and discontinuous PLFs. Our algorithm is compared with four logarithmic MILP formulations solved by Gurobi’s MILP solver as well as Gurobi’s PLF solver. We also compare our method against mixed-integer nonlinear program formulations solved by Gurobi. The numerical experiments indicate significant performance gains up to two orders of magnitude for medium- to large-sized PLFs. Finally, we also give an upper bound on the additive error from PLF approximations of nonconvex separable optimization. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The research of S. Rebennack is supported by the Deutsche Forschungsgemeinschaft [Grant 445857709]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0755 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0755 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two versions of an exact algorithm using semidefinite programming (SDP) to compute this constant for any graph. The SDP relaxation is used to first reduce the search space considerably. One version applies then an SDP-based branch-and-bound algorithm, along with heuristic search. The other version transforms the problem into an instance of a max-cut problem and solves this using a state-of-the-art solver. Numerical results demonstrate that we clearly outperform mixed-integer quadratic solvers as well as another SDP-based algorithm from the literature.

We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms.

We present an iterative algorithm to compute feasible solutions in reasonable running time to quadratically constrained quadratic programs (QCQPs), which form a challenging class of nonconvex continuous optimization. This algorithm is based on a mixed-integer linear program (MILP) which is a restriction of the original QCQP obtained by discretizing all quadratic terms. In each iteration, this MILP restriction is solved to get a feasible QCQP solution. Since the quality of this solution heavily depends on the chosen discretization of the MILP, we iteratively adapt the discretization values based on the MILP solution of the previous iteration. To maintain a reasonable problem size in each iteration of the algorithm, the discretization sizes are fixed at predefined values. Although our algorithm did not always yield good feasible solutions on arbitrary QCQP instances, an extensive computational study on almost 1300 test instances of two different problem classes - box-constrained quadratic programs with complementarity constraints and disjoint bilinear programs, demonstrates the effectiveness of our approach. We compare the quality of our solutions against those from heuristics and local optimization algorithms in two state-of-the-art commercial solvers and observe that on one instance class we clearly outperform the other methods whereas on the other class we obtain competitive results.

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the decision variables, akin to single objective problems, although we also sometimes split gaps and branch in the objective space. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances and on a new set of instances that we generate using a benchmark library (MIPLIB2017) for single objective problems. We also perform comparisons against the triangle splitting method from literature, which is an objective space search algorithm. Summary of Contribution: Biobjective mixed-integer optimization problems have two linear objectives and a mixed-integer feasible region. Such problems have many applications in operations research, because many real-world optimization problems naturally comprise two conflicting objectives to optimize or can be approximated in such a manner and are even harder than single objective mixed-integer programs. Solving them exactly requires the computation of all the nondominated solutions in the objective space, whereas some applications may also require finding at least one solution in the decision space corresponding to each nondominated solution. This paper provides an exact algorithm for solving these problems using the branch-and-bound method, which works predominantly in the decision space. Of the many ingredients of this algorithm, some parts are direct extensions of the single-objective version, but the main parts are newly designed algorithms to handle the distinct challenges of optimizing over two objectives. The goal of this study is to improve solution quality and speed and show that decision-space algorithms perform comparably to, and sometimes better than, algorithms that work mainly in the objective-space.

The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategic fleet-sizing, tactical assignment, operational vehicle routing and scheduling problems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a stochastic mixed-integer linear programming model for the H-SARA problem. Additionally, a reduced deterministic version is introduced which allows to solve small-scale instances to optimality with two acceleration approaches. For larger instances, we develop a tailored two-stage decision support system that provides high-quality and in-time solutions based on information revealed at different stages. Our solution method aims to reduce various costs under stochasticity, to create reasonable routes with balanced workload and team-based customer service zones, and to increase customer satisfaction by introducing a two-stage appointment notification system updated at different time stages before the actual service. Our two-stage heuristic is competitive to CPLEX’s exact solution methods in providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information. Results show that our two-stage heuristic is able to tackle reasonable-size instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.

Abstract. Biobjective mixed integer linear programs (BOMILP) are optimization problems where two linear objectives are optimized over a polyhedron while restricting some of the variables to be integer. Since many of the techniques for solving BOMILP (or approximating its solution set) are iterative processes which utilize data discovered during early iterations to aid in the discovery of improved data during later iterations, it is highly desirable to efficiently store the nondominated subset of a given set of data. This problem has not received considerable attention in the context of BOMILP; only naive methods have been implemented. We seek to bridge this gap by presenting a new data structure in the form of a modified binary tree that stores, updates, searches and returns nondominated solutions. This structure takes points and line segments in R2 as input and stores the nondominated subset of this input. We note that when used alongside an exact solution procedure, such as branch-and-bound (BB), at termination the data stored by this structure is precisely the set of Pareto optimal solutions. We perform two experiments. The first is designed to compare the utility of our structure for storing nondominated data to that of a dynamic list which updates via pairwise comparison. In the second we use our data structure alongside the biobjective BB techniques available in the literature and solve specific instances of BOMILP. The results of our first experiment suggest that the data structure performs reasonably well in handling input of up to 107 points or segments and does so much more efficiently than a dynamic list. The results of the second experiment show that when our structure is utilized alongside BB fathoming is enhanced and running times improve slightly. 1.