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
8
votes
2answers
850 views

Complexity of LP and MILP Problems?

My original problem is an MILP. I make it an LP by relaxing the integer variables. Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general? Is ...
6
votes
2answers
157 views

A heuristic approach to solve a MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem? Since I have an additional but ...
13
votes
6answers
199 views

How to formulate: each pair of elements in $A$ has one common unit in $B$

We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite ...
8
votes
2answers
408 views

Is there a greedy heuristic approach to the MILP problem?

I have the following optimization problem which is an MILP. I can solve it with an MILP solver. \begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\...
10
votes
3answers
1k views

Is there a heuristic approach to the MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. \begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
11
votes
2answers
347 views

How difficult is it to understand a Machine Learning method based on integer optimization?

I'm trying to understand a paper called "Supersparse Linear Integer Models for Predictive Scoring Systems" by Ustun, Tracà and Rudin, who introduce a really interesting method for generating an ...
10
votes
1answer
99 views

Wild oscillation of dual infeasibility in Gurobi mixed-integer solver

As the question says, I am wondering what happens "behind the scene" when the Dual Infeasibility column of the Gurobi runtime log oscillates wildly, before Gurobi eventually quits with infeasibility. ...
10
votes
2answers
642 views

How to use warm start to solve MIPs efficiently?

I'm working on the scheduling model which takes a long time to solve to optimality (even for a small instance), therefore I would like to use a warm start (MIP start) to solve the problem. I'm using ...
9
votes
3answers
703 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 ...
12
votes
1answer
1k views

If-then constraints in MIP programming

For continuous variables $x$ and $y$, the constraints are: ...
9
votes
2answers
188 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 $\{...
7
votes
1answer
210 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 ...
10
votes
0answers
148 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 ...
8
votes
3answers
410 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$ ...
15
votes
1answer
481 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
707 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 ...
9
votes
1answer
210 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
137 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
104 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 ...
19
votes
2answers
807 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 ...
8
votes
1answer
128 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 ...
9
votes
3answers
379 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 ...
11
votes
2answers
166 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 ...
4
votes
1answer
213 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. ...
4
votes
1answer
218 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
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 ...
10
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
621 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
163 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
292 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
359 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
570 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
98 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
1k 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
173 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
724 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 ...
14
votes
2answers
826 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 ...
24
votes
6answers
2k 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 ...
16
votes
4answers
794 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
273 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 ...
17
votes
2answers
2k 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 ...
12
votes
2answers
325 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
316 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
153 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
165 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 ...
9
votes
2answers
353 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
322 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 ...
13
votes
7answers
849 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{...

1
3 4
5
6 7