MIP 2024 Logo

Mixed Integer Programming International Workshop 2024

December 2-6, 2024

Indian Institute of Technology Bombay, Mumbai, India

We are happy to announce the inaugural International Mixed Integer Programming (MIP) Workshop, to be held in Mumbai, India. International MIP Workshops are held in addition to the classical MIP Workshop series (see here for the list of past events and the 2024 edition at the University of Kentucky) and in countries other than the USA.

MIP Workshop is a single-track workshop series highlighting the latest trends in mixed-integer programming and discrete optimization, with speakers chosen by invitation, and poster presentations open to students and postdoctoral researchers. It brings together researchers, students, and industry actors from around the globe, fostering collaboration and providing a showcase for students, early career academics, and developments in industry and novel applications. MIP International 2024 is supported by the Mixed Integer Programming Society (MIPS), a section of the Mathematical Optimization Society (MOS).

Confirmed Speakers

Program

The program for the workshop is as follows. Please click on the speaker name to highlight the talk details.

   Monday   (December 2) (9:00 AM) Opening Remarks
(9:30 AM) Santanu Dey Two strong-duality theorems for binary MINLPs

Motivated by two applications, we develop two general-purpose strong duals for binary MINLPs. The first result is motivated by the need to conduct sensitivity analysis of mixed binary quadratic programs (MBQP) with respect to changing right-hand-sides. We show that the co-positive dual of Burer’s completely positive reformulation of MBQP has no duality gap, if the feasible region is bounded or the objective is a convex function. The right-hand-side of the original MBQP only appears in the objective function of this dual, thus allowing sensitivity analysis. Our second result is motivated by designing distributed algorithms for nearly decomposable nonlinear mixed binary programs. The classical Lagrangian relaxation allows distributed computation as it leads to decomposition into sub-problems but suffers from a non-zero duality gap. We develop a hierarchy of relaxations, all of which allow problem decomposition, progressively getting tighter, with the first level being the Lagrangian relaxation and the final level of hierarchy being a strong dual. We analyze the quality of the bounds obtained at different levels of the hierarchy for packing MILPs. This is joint work with Diego Cifuentes and Jinge Xu.
(11:00 AM) Burak Kocuk Proximity results in conic mixed-integer programming

We study the distance between the optimal solutions (resp. optimal values) of mixed-integer conic programs and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of the continuous relaxation when the recession cone is regular. We then specialize our analysis to mixed-integer second order cone programs (SOCPs). In the case of SOCPs whose feasible regions are defined by a single Lorentz cone constraint, we show that the distance can be upper bounded in terms of the data of the problem (the objective function vector, the matrix defining the SOCP, and the right-hand side). We also study when this bound can be made independent of the right-hand side, akin to the mixed-integer programming case. Finally, in the case the feasible region of the SOCP is defined by two or more Lorentz cone constraints, then we show that, in general, the distance cannot be bounded independently of the right-hand side defining the SOCP, not even when its feasible region is compact or one of the Lorentz cones constraints defines a polyhedral set.
(11:30 AM) Kristof Berczi Approximability of multiway cut

In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák while the best known inapproximability factor was known to be at least 1.2 due to Angelidakis, Makarychev and Manurangsi. In this talk we show how to improve on the lower bound by constructing an integrality gap instance for the CKR relaxation. A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. One of the byproducts from our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák.
(2:00 PM) Poster Introductions
(2:45 PM) Pietro Belotti Spatial branching for convex MIPs

Branch-and-bound algorithms are the workhorse of mixed integer optimization solvers. For problems whose continuous relaxation is convex, branching is only necessary on discrete variables. Spatial branching is needed only in nonconvex optimization; however, branching on continuous variables can prove effective on convex MIPs. We report on computational tests for a special class of classification problems admitting a convex mixed integer optimization model, and show that spatial branching is far more effective than the standard integer branching machinery of a commercial MIP solver.
(4:00 PM) Poster Introductions
   Tuesday   (December 3)
(9:00 AM) Dabeen Lee From Coordinate Subspaces over Finite Fields to Ideal Multipartite Uniform Clutters.

Take a prime power q, an integer n ≥ 2, and a coordinate subspace S ⊆ GF(q)^n over the Galois field GF(q). One can associate with S an n-partite n-uniform clutter C, where every part has size q and there is a bijection between the vectors in S and the members of C. This talk discusses when this clutter is ideal, a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly, the characterization differs depending on whether q is 2, 4, a higher power of 2, or otherwise. Each characterization uses crucially that idealness is a minor-closed property: first the list of excluded minors is identified, and only then is the global structure determined. A key insight is that idealness of C depends solely on the underlying matroid of S. Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence, we prove the Replication and 𝜏 = 2 Conjectures for this class of clutters. This is joint work with Ahmad Abdi (London School of Economics).
(9:45 AM) Gustavo Angulo Generalized formulations for the traveling salesman problem

The traveling salesman problem is a widely studied classical combinatorial problem for which several integer linear formulations exist. In this work, we consider the Miller-Tucker-Zemlin (MTZ) formulation. First, we argue that the choice of some parameters of this formulation is arbitrary and, therefore, there exists a family of formulations of which MTZ is a particular case. We analyze this family, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Next, we study the intersection of this family, demonstrating that it is equivalent to a formulation from the literature. Finally, we extend this approach to the Desrochers-Laporte and Single-Commodity Flow formulations, obtaining similar results. Based on joint work with Diego Morán (RPI).
(11:00 AM) Andrea Lodi Efficient Branching Rules for Optimizing Range and Order-Based Objective Functions

We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top of problem-specific branching schemes. We show several desirable properties of range branching and show its effectiveness on a series of instances of the fair capacitated vehicle routing problem and fair generalized assignment problem. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branch-and-bound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to order-based objective functions, such as the Gini deviation.
(2:00 PM) Vineet Goyal Distributionally Robust Newsvendor on a Metric

We consider a fundamental generalization of the classical newsvendor problem where the seller needs to decide on the inventory of a product jointly for multiple locations on a metric as well as a fulfillment policy to satisfy the uncertain demand that arises sequentially over time after the inventory decisions have been made. To address the distributional-ambiguity, we consider a distributionally robust setting where the decision-maker only knows the mean and variance of the demand, and the goal is to make inventory and fulfillment decisions to minimize the worst-case expected inventory and fulfillment cost (where the expectation is taken over the worst case choice of distribution with given mean and variance). We present a significant generalization of the classical result of Scarf (1958) and give a policy with strong theoretical guarantees as well as good practical performance while maintaining the simplicity and interpretability of the solution in Scarf (1958). In particular, our policy first identifies a hierarchical clustering of the locations, and assigns a "virtual-underage cost" for each cluster. Our inventory solution ensures that for each cluster, the total inventory in the cluster is at least as large as the inventory level suggested by Scarf's solution for the virtual-underage cost if the cluster was a single point. We show that the policy achieves a poly-logarithmic approximation. To the best of our knowledge, this is the first algorithm with provable performance guarantees. Furthermore, our numerical experiments show that the policy performs well in practice.
(2:45 PM) Sanjeeb Dash Applications of polynomial optimization to scientific discovery and solution techniques

Many data-driven machine learning techniques are nowadays used in scientific discovery including symbolic regression. In symbolic regression, the functional form is not fixed a priori and one instead learns a function of bounded expression length that can be composed of an input list of operators and variables. However, finding formulas that are consistent with known theory is a challenging task. We describe our recent software implementation, named AI Hilbert, that draws on techniques from polynomial optimization and algebraic geometry to obtain a scientific formula when both the desired formula and background theory are expressible via polynomial expressions. We also discuss recent work on improving polynomial optimization techniques that are motivated by discrete optimization methods.
(4:00 PM) Swati Gupta New Challenges in Optimization for Ethical Decisions.

When someone is denied a job, offered a different price for the same goods or services, denied bail or declined a loan, intent to discriminate is often not the case. The decision system applies the same data and rules to all and yet has a disproportionate effect on various groups. The causes of such disparate impact in machine learning and optimization are many, and these create an opportunity for us to develop new optimization-based solutions. I will present three such opportunities. The first is motivated by challenges due to bias and errors in evaluation data. I will present new optimization problems using ordinal data, which can create a pathway to solving discrimination in hiring (Management Science, 2023 with Salem, and UC Davis Law Review, 2023 with Salem and Desai). Next, I will discuss the challenge of selecting the “right” notion of fairness. I will present the concept of portfolios, that ask to find a small set of approximate solutions that summarize the set (potentially infinite) set of fairness objectives. I will showcase combinatorial techniques to tackle this challenge, and connections to polyhedral structure (EC 2023, SODA 2025, with Singh and Moondra). Finally, motivated by the recent lawsuits on price fluctuations, I will discuss challenges in trajectory-constrained stochastic optimization, which for example, can provide algorithms that monotonically change prices in demand learning (WINE 2022, with Kamble and Salem). This talk is based on joint work with Jad Salem, Deven Desai, Mohit Singh, Jai Moondra, and Vijay Kamble.
   Wednesday   (December 4)
(9:00 AM) Carla Michini Price of Anarchy in Paving Matroid Congestion Games

Congestion games allow to model competitive resource sharing in various distributed systems. Pure Nash equilibria, that are stable outcomes of a game, could be far from being socially optimal. Our goal is to identify combinatorial structures that limit the inefficiency of equilibria. This question has been mainly investigated for congestion games defined over networks. Instead, we focus on symmetric matroid congestion games, where the strategies of every player are the bases of a given matroid. We derive new upper bounds on the Price of Anarchy (PoA) of congestion games defined over k-uniform matroids and paving matroids with delay functions in class. For both affine and polynomial delay functions, our bounds indicate that the inefficiency of pure Nash equilibria is limited by these combinatorial structures. This is a joint work with Bainian Hao.
(9:30 AM) Daniel Espinoza An exponential penalization, network decomposition algorithm for large LPs

CLarge linear programs, in the order of hundred of millions or more variables and constraints, with large network-flow sub-structures, naturally arise in applications like mine planning, joint network design and routing problems, pricing problems, and in many other contexts. Most of these instances are impossible to solve with standard commercial LP solvers, but there are some specialized algorithms making headway for this class of problems. In this presentation we motivate the importance of this class of problems, give a short literature review of the area, both of the theory and of previous implementations and alternative algorithms, and present our current results on an implementation of an exponential-penalization network-sub-structure-aware parallel algorithm; comparing it against both simplex and barrier methods on MIPLIB linear relaxations, and on a set of large instances collected from different applications.
(11:00 AM) Claudia D'Ambrosio Mixed Integer Programming for Urban Air Mobility

Cities with high population density, such as New York, Los Angeles, and Paris, face significant traffic congestion. Urban Air Mobility (UAM) aims to transform transportation worldwide with a straightforward concept: utilizing the sky to alleviate ground traffic over medium distances. Companies are developing electric Vertical Take-Off and Landing (eVTOL) vehicles to bring this vision to life. However, several technical and societal challenges remain: How can UAM be developed sustainably? How can safety be ensured? How could we build efficiently the needed infrastructure or adapt the new one? We will focus on how mixed integer programming contributes in making UAM a reality and introduce formulations, instances generators, and solution methods for solving problems arising in this new application domain.
(2:00 PM) Akshay Gupte Power of permutations in nonlinear integer programming

We present some algebraic approaches for optimising over integer points in a compact set, by constructing families of inner- and outer-approximations using monomial orders on the integer lattice. Our particular focus is on orders obtained using permutation matrices. When maximising a monotone subadditive function over some integer points, we establish for our approximation scheme some tight approximation factors which depend on sparsity of the function, and also give a solvability result in terms of a certain parameter. For representability of the integer points, some conditions are identified for the outer-approximation to be exact. Our scheme is not polynomial-time in general due to the bottleneck operation of computing minimal and maximal elements in the feasible set, and hence some algorithms are designed to apply it as a heuristic method. Numerical results on benchmark and random test instances show competitive performance of our approximation scheme. Joint work with Yiran Zhu (Edinburgh).
(2:45 PM) Laura Sanita On the number of degenerate Simplex pivots

The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge direction of the underlying polyhedron. A key issue in the simplex algorithm’s performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that it is always possible to limit the number of consecutive degenerate pivots that the simplex algorithm performs to n-m-1, where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form. The drawback of the whole machinery is that it requires an improving feasible direction at a given vertex, that is in general as hard as solving an LP. However, from a theoretical perspective, our results show that for several polytopes, not only a short path on the 1-skeleton exists, but a short sequence of simplex pivots always exists (and can also be efficiently computed): that is, a short sequence of basis exchanges that follow improving directions, when performing both degenerate and non-degenerate pivots.
(4:00 PM) Sebastian Pokutta Exploring Mixed-Integer Convex Optimization with Conditional Gradients: Foundations and Applications

In this talk, I will introduce the Boscia framework, an algorithmic approach to tackling mixed-integer convex optimization (MICO) problems. The Boscia method leverages (variants of) the Frank-Wolfe algorithm within a branch-and-bound framework, offering significant computational benefits for solving MICO problems. Most notably, it only requires black box access to the objective and feasible region. Following an overview of the framework, I will present two real-world applications where this method demonstrates its efficacy. The first is the Optimal Experiment Design Problem, where we aim to choose experiments or observations that maximize the information gained about a system. The second application addresses the Network Design Problem for Traffic Assignment, a critical task in urban planning and transportation. Our results for both applications highlight Boscia’s adaptability and efficiency, particularly when solving large-scale instances with complex constraints.
   Thursday   (December 5) Outdoor Activity
(3:00 PM) Pierre Le Bodic The quest to make an academic career in MIP solving

Obtaining speed-ups in MIP solvers has become increasingly challenging. They are complex software, so results are subject to performance variability, and understanding them is challenging. Nowadays, a MIP solver improvement typically yields a single digit or sub-single digit increment. Such changes are hard to detect without a very large testset, and can be hard to publish. Hence, researching MIP solving in academia is a challenge. We will present principles that can help succeed in this line of research, and demonstrate how they were applied in the development of abstract models for MIP solvers.
(4:00 PM) Manish Bansal Distributionally Risk-Receptive and Robust Stackelberg MIP Games

Stackelberg games are played between two players: an interdictor/attacker and a defender. The interdictor is a player who makes interdiction decisions using limited resources to degrade the defender’s performance, and the defender makes decisions after observing the interdiction decision. These games are helpful for making long-term planning decisions, analyzing vulnerabilities in a system, and resiliency planning. However, three challenges associated with these games are combinatorial nature of the decisions, stochastic nature of the attacks, and limited availability of relevant historical information that leads to distributional ambiguity. We introduce new algebraic modeling frameworks that allow uncertainty in the success and impact of the attacks by an interdictor, adjustments based on risk-appetite (risk-receptive or risk-averse) of the decision makers (both interdictor and defender), and incomplete information of probability distribution associated with uncertain data parameters. More specifically, we introduce distributionally risk-receptive and distributionally robust (or risk-averse) multistage stochastic mixed-integer programs (denoted by DRR- and DRA-MSIPs), and present cutting plane-based and reformulation-based approaches for solving DRR- and DRA-MSIPs without and with decision-dependent uncertainty to optimality. Based on our computational results for multistage maximum flow and facility location interdiction problems, we observe that the cutting plane-based approaches are 2800% and 2410% (on average) faster than the reformulation-based approaches for the distributional risk-averse and risk-receptive, respectively, variants of these problems. In this talk, we will also discuss two more Stackelberg games with applications in machine learning and robotics: Adversarial Camera View-Frame Placement and Feature Selection Interdiction Problems. This is a joint work with my PhD students: Sumin Kang and Seonghun Park.
   Friday   (December 6)
(9:00 AM) Karthyek Murthy A Nonparametric Approach with Marginals for Modeling Consumer Choice: MIP formulations & applications

Given data on the choices made by consumers for different offer sets, a key challenge is to develop parsimonious models that describe and predict consumer choice behaviour while being amenable to prescriptive tasks such as pricing, assortment optimization, etc. The marginal distribution model (MDM) is one such model, that requires only the specification of marginal distributions of the random utilities. This talk aims to establish necessary and sufficient conditions for given choice data to be consistent with the MDM choice model hypothesis, inspired by the utility of similar characterizations for the random utility model (RUM). This endeavour leads to an exact characterization of the set of choice probabilities that the MDM can represent. Verifying the consistency of choice data with this characterization is equivalent to solving a polynomial-sized linear program. Since the analogous verification task for RUM is computationally intractable and neither of these models subsumes the other, MDM is helpful in striking a balance between tractability and representational power. The characterization is convenient to be used with robust optimization for making data-driven sales and revenue predictions for new unseen assortments via mixed integer linear programs. When the choice data lacks consistency with the MDM hypothesis, finding the best-fitting MDM choice probabilities reduces to solving a mixed integer convex program. Experiments with both real and simulated data demonstrate the efficacy of the developed mixed integer formulations in offering better representational power and prediction accuracy than multinominal logit and significantly better computational performance than RUM.
(9:45 AM) Nikhil Kumar Relative Survivable Network Design

One of the fundamental problems in network design is to find a minimum-cost subgraph of an input graph that satisfies a given cut-requirement function f. Jain introduced the iterative rounding method in the context of this problem and gave a 2-approximation algorithm when f is weakly supermodular. The above formulation assumes that the input graph does not have a cut with fewer edges than the requirement function. To circumvent this assumption, Dinitz, Koranteng, and Kortsarz have recently introduced a relative version of the problem, where the number of edges to be picked across a cut S is the minimum of two quantities: the number of edges across the cut S and the value of the given requirement function f(S). This new requirement function defined above is not weakly supermodular if f is weakly supermodular, and the previous methods cannot be used directly to find an approximation algorithm. We introduce novel techniques and give a new approximation algorithm for this problem.
(10:30 AM) Concluding Remarks and Workshop Conclusion

The workshop welcome and registrant check-in will be from 8:00 AM on Monday, December 2, 2024.

Poster session

Registration

Registration for MIP International 2024 is now closed. The registration fee includes lunch for the participants. Please refer to the following table for the respective registration fees.

  Participant Registration Fees (Domestic) Registration Fees (Foreign)
   (Full Time) Students/Postdocs INR 2500 USD 50
  Academics/Faculty INR 8000 USD 100
  Industry Affiliates / Executive Program Students INR 16000 USD 200

The deadline to register for the workshop is Oct 15, 2024. For any questions or queries regarding registration please contact us at mipint2024 [at] iitb [dot] ac [dot] in

Registration fee is non-refundable if one does not attend!

Workshop venue

The main workshop venue is Victor Menezes Convention Center(VMCC), IIT Bombay.

Getting to IIT Bombay

Domestic Arrivals

Air

Domestic flights land at Chhatrapati Shivaji Maharaj International Airport both at Terminals T1 and T2 (12kms and 8kms away from IIT Bombay, respectively). Local public transport in terms of buses, auto rickshaws, regular/pre-paid taxis or Uber/Ola are available to reach the IIT Bombay, Powai (Gate 2).

International Arrivals

International flights land at Chhatrapati Shivaji Maharaj International Airport Terminal 2 (T2), which is about 8 kms from IIT Bombay, Powai. A pick-up can be arranged with prior intimation to workshop organizers. Prepaid taxis and Uber service the airport and can be used to reach the IIT Bombay, Powai (Gate 2).

For participants staying in hotels outside IIT Bombay, the workshop will arrange for pick-ups and drops from hotels to workshop venue and back.

Accommodation

Limited shared hostel accommodation facility (separate hostels for boys and girls) is available for domestic and international student participants on a first-come, first-served basis. A separate email will be sent to the student participants to apply for the same.

Nearby Hotels

In response to the requests from the workshop participants, we are providing a list of the nearby hotels for convenience. Please note that the workshop organisers, or IIT Bombay, will not take any responsibility for the stay or any related concerns whatsoever and will not need to be contacted for this purpose. Participants will be responsible to check on their own for the suitability of the accommodation. (The names are hyperlinked with their official website)

Organization

MIP Program Committee

Local Organization

Contact

  • email : mipint2024 [AT] iitb.ac.in

Credits

Poster Design by Radhika Gupta. Logo-Design by ©Julia Silbermann (Font-Credits: Cornerstone, by Zac Freeland). Layout based on skeleton using Raleway font