Biobjective mixed integer programs (BOMIPs) have recently received much attention due to their broad applications. A class of methods which use tabu or "no-good" constraints have been developed to solve biobjective mixed integer linear programs. In this work, we propose an extension of tabu methods to the case of nonlinear problems. We use the structure of the outcome space of nonlinear BOMIPs to "leap" between slices of the Pareto set, skipping over dominated slices. We discuss theoretical results and propose an algorithm, Pareto LEAP, which may be flexibly implemented in any language, using any suitable solver. We also demonstrate Pareto LEAP on an example problem from the literature.

In this talk, we present a concrete approach for solving multi-objective mixed-integer nonconvex optimization problems. In fact, our algorithm uses information from the image space to build adaptively individualized piecewise linear relaxations of nonlinear terms appearing in the original problem. This procedure allows us to compute a so-called pseudo enclosure of the nondominated set of some predetermined accuracy relying on MILPs and NLPs. Within the successive refinement framework, the introduction of adaptivity and therefore individualization with respect to the current region of interest serves to avoid unnecessary complexity of the MILP relaxations. We validate the proposed scheme with numerical experiments.

An efficient integer assignment for multiobjective mixed-integer problems is a fixing of the integer variables so that there exists an efficient point with exactly that fixing. Depending on the instance, solution algorithms for multiobjective mixed-integer problems may need to detect a large number of efficient integer assignments, possibly all integer feasible assignments, so that a full enumeration cannot be avoided. This shows a big difference with respect to the single objective case and a big challenge in terms of algorithms development. In this talk, we present a branch-and-bound method for multiobjective mixed-integer convex quadratic programs that computes a superset of efficient integer assignments and a coverage of the nondominated set. The method relies on outer approximations of the upper image set of continuous relaxations.
These outer approximations are obtained addressing the dual formulations of specific subproblems where the values of certain integer variables are fixed.
The devised pruning conditions and a tailored preprocessing phase allow a fast enumeration of the nodes.
Despite we do not require any boundedness of the feasible set, we are able to prove that the method stops after having explored a finite number of nodes. Numerical experiments on a broad set of instances with two, three, and four objectives are presented.

In this talk, we introduce a novel approximation guaranteed algorithm for (feasibility) mixed integer nonlinear programming (MINLP) by straightforwardly extending the Plotkin, Shmoys and Tardos algorithm for fractional packing and covering problems and the multiplicative weights update (MWU) framework. The approximation guaranteed algorithm aims to find a epsilon-feasible solution with respect to a feasibility region described by possibly non-convex nonlinear constraints, by solving an opportune surrogate relaxation of the given problem, calling an oracle for a polynomial number of times, and adapting the weights of the surrogate relaxation by means of the MWU algorithm. We implement our new method in order to heuristically solve (non-convex) separable problems (SPs), i.e., MINLP problems in which each occurring function is representable as the sum of non-convex univariate functions. We can assume without loss of generality that the objective function of SPs is linear. In particular, we combine plain bisection approach with the novel approximation guaranteed method in order to deal with optimality and feasibility issues at the same time. In this latter particular case, since the original problem is separable, the oracle is reasonably easy to implement, by computing the roots of the first derivative of the univariate functions and its value on the boundary and eventually rounding the computed values. We present preliminary computational results on random generated instances, showing the proposed method is competitive against the state-of-the-art exact solvers for non-convex MINLP, namely Couenne and Scip.