# Questions tagged [mixed-integer-programming]

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

474 questions
Filter by
Sorted by
Tagged with
218 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....
149 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 ...
175 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 ...
2k 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 ...
132 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 ...
816 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 ...
144 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 ...
193 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 ...
504 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 ...
2k views

### Why is it important to choose big-M carefully and what are the consequences of doing it badly?

The question here discusses the two different use of "big-M method", where one of them is the big-M in logical constraints and linearization in (mixed-)integer programming problems (that's what I'm ...
518 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{...
322 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. ...
297 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 ...
317 views

222 views

### Assignment Problem with Decreasing Costs

Problem: I have $i$ jobs that I can assign to $j$ workers. Each job has a cost. Each worker can perform up to an arbitrary max number of jobs. However, there is a cost efficiency for each job that is ...
3k 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 ...
161 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 ...
587 views

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

A short background: A paper  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 ...
542 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 ...
820 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 ...
338 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-...
152 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 ...
741 views

### How to set a maximum time to improve a solution with Pyomo and CBC

In relation to using CBC via Pyomo: I was wondering if anyone knew if it was possible to set a maximum allowed time to improve a solution, rather than a maximum total time. This way, if you've been ...
435 views

### Good resources for solving techniques (Metaheuristics, MILP, CP etc)

I want some resources (tutorials, online courses, lecture notes, articles, books, etc.) to learn the different techniques to solve OR problems (metaheuristics, CP, MILP, etc). It would be better if ...
Let's observe an example constraint: $\sum \limits^E_{e\ \in \ A_a \ \cap \ B_b \ \cap \ C_c} x_{e,a,b,c} \geq n_{a,b,c} \; \; \; \forall a \in A,b \in B,c \in C$ with $e \in E$ an element and $A_a$ ...