The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
7
votes
3answers
263 views

Modeling the Choose function

In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose ...
6
votes
1answer
78 views

If-then constraints in MIP programming

For continuous variables $x$ and $y$, the constraints are: ...
5
votes
1answer
90 views

How to formulate a MIP that can minimize the costs with a combination of subsets given a set?

I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs: $\{1\}=8$, $\{2\}=9$, $\{3\}=7$, $\{1,2\}=9$, $\{1,3\}=18$, $\{2,3\}=15$ and $\{...
5
votes
1answer
72 views

Logical Constraints Modelling using Big-M formulation

I am trying to model some logical constraints in ILOG. Logical constraints could be given such as: Constraint 1 or Constraint 2, Constraint 3 or Constraint 4, Constraint 5 or Constraint 6. The ...
7
votes
0answers
73 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
7
votes
3answers
286 views

Linearization of a scheduling objective function

I am trying to maximize the workload per employee. An example: $e$ the index of an employee $j$ the index of a project decision variable: $x_{e,j} \in \mathbb{Z}$ and $0 \leq x_{e,j} \leq 100$ ...
14
votes
1answer
308 views

Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
8
votes
4answers
651 views

Modeling the Round (Nearest Integer) function

Modeling various non-differentiable functions is quite common knowledge including $\operatorname{abs}$, $\min$ and $\max$ functions. How would one go about modeling the nearest integer function, say ...
8
votes
1answer
190 views

Should I factor in time as a parameter or a variable in a scheduling problem with MILP?

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
10
votes
3answers
119 views

Theoretical results on performance of branch-and-bound

Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem? As an example, does there exist a result of ...
14
votes
1answer
69 views

In the context of LASSO regression, how to introduce a constraint for max number of selected betas?

In lasso, we have a regularization term in the loss function: $$\sum \|y-\hat{y}\|_{2} + \lambda \sum\|\beta\|_{1}$$ As the loss function is minimized, some $\beta$'s will become zero. That's what ...
18
votes
2answers
763 views

How do we decide/plan an SLA for an NP-hard optimization process running in production?

How do you decide or plan an SLA (Service Level Agreement) for an application that depends on an optimization process when the problems you deal with are NP-hard? That is, if you are developing an ...
7
votes
1answer
82 views

Extract info from Gurobi binary variables during run-time

Actually the question below is not specific to Gurobi, but that's the tool I am using. Consider a scheduling problem where a 2D array of binary variables $Z(i,v)$ is defined, where $i$ is index of ...
8
votes
3answers
176 views

How could we simplify solving the large scale MIPs without using any advanced methods like decompositions?

Many practical optimization models (specially MIPs) are NP-Hard and solving them need much time even with the modern solvers like CPLEX or GUROBI. One of the best way (but not easy) is using ...
10
votes
2answers
129 views

Difficulties with finding equivalent problem on literature

I'm working with a sort of pickup delivery problem right now. We need to assign vehicles to routes and requests to those vehicles. Each request has its due date, client and may be delivered in one of ...
3
votes
1answer
71 views

XOR constraint representation

In an scheduling optimization problem, for job $l$, $\xi_l$ is binary variable that $\xi_l=1$ shows job $l$ is selected. $t_{r,l}$ and $t_{e,l}$ are registration time and time that job is completed. ...
3
votes
1answer
105 views

Scheduling Optimization Problem

I want to solve below optimization problem. This is scheduling problem where I seek to complete as many of the jobs $\xi_l$ (objective function and constraint 1), with $T_C$ being the last time until ...
8
votes
4answers
1k views

Why is there not a feasible solution for a MIP?

Is there a way to see why a solver (OR-Tools, CPLEX, Gurobi) cannot find a feasible solution when solving a MIP? By that I mean, is there a possibility to show at which constraint and exact indices ...
8
votes
4answers
2k views

What do solvers like Gurobi and CPLEX do when they run into hard instances of MIP?

MIP is NP-Hard, so it is possible that an instance is very difficult and has multiple local minima that the search can get stuck in. With a Metaheuristic Algorithm, the stochastic and approximate ...
13
votes
3answers
476 views

Is using gradient descent for MIP a good idea?

I'm researching ways of solving constrained optimization problems on a cloud platform. I stumbled across this: https://cloud.google.com/blog/products/data-analytics/distributed-optimization-with-...
12
votes
2answers
143 views

Linearisation techniques for MINLPs

I am wondering what kinds of linearisations people do for MINLPs outside my field of expertise. I work in global optimisation, so by "linearisation" we would typically mean one of the following: ...
8
votes
1answer
266 views

How to resolve this issue in multi-objective optimization?

I have the following multiobjective optimization problem. The objectives are non-conflicting. The Optimization Problem: $$\underset{\large{a^{(l)}_{c,u},f^{(l)}_{c,u},z_{l,t},l\in\mathcal{L}}}{\max}...
9
votes
2answers
133 views

Valid Inequalities and Strong Inequalities

Consider the following mixed-integer set: \begin{equation} P(A, b ; S) \stackrel{\text { def }}{=}\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \text { for } j \in S\right\} \end{...
7
votes
2answers
299 views

Finding an Objective Function for Assigning Employees to Sequence Dates

I am using a mixed-integer-program to schedule employees to projects. These projects can have a time window to get completed from a few weeks to a few months. At the moment I am working in a ...
9
votes
1answer
73 views

How to model 24 hours demand into a daily shift schedule?

I am working on a weekly staff scheduling optimization problem with 24/7 demand. The binary decision variable is: $X_{\text{staff},\,\text{day},\,\text{shift}}$ whether to assign the staff $s$ to day ...
15
votes
3answers
921 views

How does the search space affect the speed of an ILP solver?

Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model ...
9
votes
1answer
105 views

Profit Maximization vs Cost Minimization for Employee Scheduling

I wanted to write two objective functions for an employee scheduling problem (MIP) until it occurred to me, that one objective function may be redundant. Is there a difference between the cost ...
12
votes
3answers
581 views

What is a “hard problem” in the context of Mixed-integer programming?

As a practical (real-world problems) point of view, it's important we could solve optimization problems as quickly as possible (for instance, to release a daily schedule). Maybe a problem with many ...
13
votes
2answers
449 views

State-of-the-art algorithms for solving linear programs

Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
6
votes
5answers
2k views

Algorithms vs LP or MIP

Is there a way of writing an algorithm with if-, while-statements to find an optimal solution without using linear-programming (LP)/MIP? If so, what would the benefits be against the LP/MIP? Is it ...
20
votes
6answers
1k views

How to compare two different formulations of a problem?

I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
15
votes
4answers
525 views

Best model for precedence constraints within scheduling problem

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to ...
5
votes
2answers
199 views

Bridge the gap between theory and practice in Integer Programming

I've finished Wolsey's book on Integer programming. It's a theoretic book. I aim to learn how the ideas presented in the book can be applied to solve real-world non-academic problems. I am looking ...
14
votes
2answers
277 views

How does a warm start work in LP/MIP?

Can someone explain how warm starts/ MIP starts work? How do solvers like CPLEX/GUROBI use warm start with the Simplex algorithm? I am interested in understanding how the entire warm start ...
11
votes
2answers
248 views

Is there a way to proportionalize fixed costs in a MILP?

So assume we have a MILP (e.g. inventory or capacity planning) and the objective is to minimize total costs (inventory costs, set-up costs, backorder costs, production costs etc.). The production of a ...
12
votes
1answer
213 views

Mixed-Integer Linear Programming (Capacity Planning)

I'm currently developing a small capacity planning problem and right now I am struggling with the "activation" of a subset. Needless to say I am not an expert in this kind of things. I have a set of $...
13
votes
4answers
2k views

Is there a SQL/English like language that lets you define formulations given some data?

It would be very useful for beginning and non technical users to be able to define models in a way that was natural for them. Further this could perhaps assist generating some kind of generic ...
9
votes
1answer
117 views

Static stochastic knapsack problem: unbounded version

In the static stochastic knapsack problem (SSKP) the weights $w_i$ of the items are distributed according to a probability distribution. Each item $i \in I$ can be selected at most once. So, ...
15
votes
1answer
147 views

Symmetric undirected $p$-median instance with fractional LP solution?

The $p$-median problem is NP-hard, so its LP relaxation does not naturally have all-integer solutions. However, it very often does; in fact, it can be hard to find an instance for which the LP ...
8
votes
2answers
91 views

Warm-start SCIP with a solution

I am trying to solve a MIP using SCIP. I let my solver run for some initial time-bound - let's say 10min. After 10min, I check if the problem is solved to optimality or 1% gap. If not, then I would ...
25
votes
1answer
221 views

The rationale to improve MTZ?

Currently I need to solve a quite specific problem involving symmetric TSP as a sub-problem (i.e., a Hamiltonian cycle is a necessary condition for optimizing some problem-specific variables that ...
12
votes
7answers
785 views

What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?

I'm specifically looking for real applications of the following form of MIP: $$\max\,Cx$$ subject to: \begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{...
19
votes
3answers
1k views

Are valid inequalities worth the effort given modern solvers?

In Laurence Wolsey's Integer Programming[1], he presents a well-known procedure for deriving valid inequalities (VI) suitable for integer and mixed integer linear problems (see Section 8.3, and also ...
6
votes
1answer
178 views

How to linearize min function as a constraint?

I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed ...
14
votes
1answer
443 views

Estimation of the size of Branch-and-Bound trees using ML

A short background: A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution ...
9
votes
2answers
118 views

Are there examples of spatially explicit MIP problems?

Disclosure: I am an MSc student in economics, but not an expert by any means in OR. I am trying to model a spatial MIP problem of an invasive species similar to this academic paper, however, my ...
12
votes
1answer
497 views

Complexity of verifying optimality in (mixed) integer programming

I looked around for a while, but I couldn't find a precise answer to the following question. If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of ...
17
votes
1answer
195 views

Warm start CPLEX using google or-tools

I have been trying to use the SetHint python API in google or-tools to warm start MIPs and solve it using CPLEX. It looks like my hints are accepted by the SetHint function but I am not sure whether ...
12
votes
2answers
138 views

Querying attributes of LP relaxation at MIP-optimality in Gurobi

Is there a way to configure Gurobi to allow the LP relaxation associated with the optimal solution leaf of a MIP branch-and-bound tree to be queried for shadow prices & other general LP properties-...
9
votes
1answer
139 views

Structural Optimization

Currently, I am working on a problem in which I need to use MILP to model equilibrium equations in a lightweight structure. Although this is an application based question, I wondered if there is a ...