mixed-integer linear programming

Solution of Binary-Constrained Quadratic-Defined Optimization Problems by a Progressive Integer Programming Method

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , ,

Extending a classic result of Giannessi and Tomasin [\textit{Lecture Notes in Comput. Sci. 3}, Springer, 1973, pp. 437–449], this paper shows that a binary-constrained quadratic-defined optimization problem can be formulated as a binary-constrained linear program with linear complementarity constraints (Bi-LPCC). The term “quadratic-defined problems” encompasses many problems that are defined by quadratic functions in the … Read more

An exact algorithm for the probabilistic TSP via a new tractable convex representation of recourse

Categories (Mixed) Integer Linear Programming, Convex Optimization, Stochastic Programming Tags , , , ,

We consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a … Read more

Synthetic Population Generation and Georeferenced Household Allocation Via Iterative Proportional Fitting and Integer Programming

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Data Science Applications Tags , , ,

Georeferenced synthetic populations are essential inputs for agent-based simulations in epidemiology, transportation, and urban planning, yet existing methods for spatial allocation of households to residences lack formal optimality guarantees. We present a two-stage mathematical framework for generating such populations from publicly available census data. The first stage combines Iterative Proportional Fitting (IPF) with a mixed-integer … Read more

Multi-Fidelity Benders Decomposition for Generation, Storage, and Transmission Expansion Planning

Categories (Mixed) Integer Linear Programming, Energy Tags , , , ,

Modern energy grid expansion planning, by necessity, includes timeseries data to accurately model storage and renewable assets. Representative time periods are commonly used as a way to decrease problem size and therefore mitigate the increased complexity from this inclusion. However, there are many choices around these representative periods: length; location in planning horizon; boundary conditions. … Read more

The value of storage in electricity distribution: The role of markets

Categories Energy Tags , , , ,

Electricity distribution companies deploy battery storage to defer grid upgrades by reducing peak demand. In deregulated jurisdictions, such storage often sits idle because regulatory constraints bar participation in electricity markets. Here, we develop an optimization framework that, to our knowledge, provides the first formal model of market participation constraints within storage investment and operation planning. … Read more

Folding Mixed-Integer Linear Programs and Reflection Symmetries

Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , ,

For mixed-integer linear programming and linear programming it is well known that symmetries can have a negative impact on the performance of branch-and-bound and linear optimization algorithms. A common strategy to handle symmetries in linear programs is to reduce the dimension of the linear program by aggregating symmetric variables and solving a linear program of … Read more

Integral Inverse Optimization Problems

Categories (Mixed) Integer Linear Programming, Bilevel Optimization Tags , ,

Inverse optimization problems are bilevel optimization problems in which the leader modifies the follower’s objective such that a prescribed feasible solution becomes an optimal solution of the follower. They capture hierarchical decision-making problems like parameter estimation tasks or situations where a planner wants to steer an agent’s choice. In this work, we study integral inverse … Read more

Zimpler – Integer Programming, easier

Categories (Mixed) Integer Linear Programming, Modeling Languages and Systems Tags , , , ,

This paper introduces Zimpler, a free tool built on the ZIMPL modeling language to streamline the solution of mixed-integer linear programs (MILP). Zimpler extends existing ZIMPL workflows by integrating native data sources—such as Excel spreadsheets—without requiring manual conversion to text-based tables. In addition, it supports solution refinement by adapting solver outputs into alternative formats, including … Read more

A Surface-Based Formulation of the Traveling Salesman Problem

Categories (Mixed) Integer Linear Programming, Other Topics Tags , , , ,

We present an exact formulation of the symmetric Traveling Salesman Problem (TSP) that replaces the classical edge-selection view with a surface-building approach. Instead of selecting edges to form a cycle, the model selects a set of connected triangles where the boundary of the resulting surface forms the tour. This method yields a mixed-integer linear programming … Read more

Solving the Heilbronn Triangle Problem using Global Optimization Methods

Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications Tags , , , ,

We study the Heilbronn triangle problem, which involves placing \(n\) points in the unit square such that the minimum area of any triangle formed by these points is maximized. A straightforward maximin formulation of this problem is highly non-linear and non-convex due to the existence of bilinear terms and absolute value equations. We propose two … Read more