Integer Programming

Approximating the Pareto frontier for bi-objective preventive maintenance and workshop scheduling. A Lagrangean lower bounding methodology for evaluating contracting forms

  • Gabrijela Obradović
  • Ann-Brith Strömberg
  • Felix Held
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    Effective planning of preventive maintenance plays an important role in maximizing the operational readiness of any industrial system. We consider an operating system and a maintenance workshop governed by two stakeholders who collaborate based on a mutual contract: components of the operating system that need maintenance are sent to the maintenance workshop, where necessary maintenance … Read more

    Adaptive Partitioning for Chance-Constrained Problems with Finite Support

  • Marius Roland
  • Alexandre Forel
  • Thibaut Vidal
    • Categories Integer Programming, Stochastic Programming

    This paper studies chance-constrained stochastic optimization problems with finite support. It presents an iterative method that solves reduced-size chance-constrained models obtained by partitioning the scenario set. Each reduced problem is constructed to yield a bound on the optimal value of the original problem. We show how to adapt the partitioning of the scenario set so … Read more

    An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original … Read more

    Submodular Dispatching with Multiple Vehicles

  • Ignacio Erazo
  • Alejandro Toriello
    • Categories Integer Programming, Production and Logistics, Transportation Tags , , , ,

    Motivated by applications in e-commerce logistics and production planning where orders (or items, or jobs) arrive at different times and must be dispatched or processed in batches, we consider a multi-vehicle dispatching problem that captures the tension between waiting for orders to arrive and the economies of scale due to batching. Our model extends the … Read more

    upgrading the network in discrete location problems with customers satisfaction

  • Inmaculada Espejo
  • Alfredo Marín
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , , , , , ,

    Generally speaking, in a discrete location problem the decision maker chooses a set of facilities among a finite set of possibilities and decides to which facility each customer will be allocated in order to minimize the allocation cost. However, it is natural to consider the more realistic situation in which customers have their own criterion … Read more

    An outer approximation method for solving mixed-integer convex quadratic programs with indicators

  • Linchuan Wei
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    Mixed-integer convex quadratic programs with indicator variables (MIQP) encompass a wide range of applications, from statistical learning to energy, finance, and logistics. The outer approximation (OA) algorithm has been proven efficient in solving MIQP, and the key to the success of an OA algorithm is the strength of the cutting planes employed. In this paper, … Read more

    Computing an approximation of the nondominated set of multi-objective mixed-integer nonlinear optimization problems

  • Leo Warnow
  • Gabriele Eichfelder
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Multi-Criteria Optimization Tags , , , ,

    In practical applications, one often has not only one, but several objectives that need to be optimized simultaneously. What is more, modeling such real world problems usually involves using both, continuous and integer variables. This then results in multi-objective mixed-integer optimization problems, which are in focus of this paper. We present an approximation concept, called … Read more

    A two-stage stochastic programming approach incorporating spatially-explicit fire scenarios for optimal firebreak placement

  • Sebastián Dávila
  • Andres Weintraub
  • Franco Quezada
  • Jaime
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    Ensuring the effective placement of firebreaks across the landscape is a critical issue in wildfire prevention, as their success relies on their ability to block the spread of future fires. To address this challenge, it is essential to recognize the stochastic nature of fires, which are highly unpredictable from start to finish. The issue is … Read more

    Facets of the knapsack polytope from non-minimal covers

  • Guneshwar Anand
  • Sachin Jayaswal
  • B. Srirangacharyulu
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , , , ,

    We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more

    Solving Nonconvex Optimization Problems using Outer Approximations of the Set-Copositive Cone

  • Kurt M. Anstreicher
  • MarkusGabl
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Global Optimization Theory Tags , ,

    We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with conic constraints and cutting planes. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a … Read more