Questions tagged [mixed-integer-programming]
For questions about mathematical optimization problems involving both continuous and binary or general integer variables.
1,151 questions
5
votes
1
answer
139
views
How to solve this riddle with a MIP?
On a square grid, a loop passes through each cell exactly once. For certain rows and columns, the maximum number of consecutive cells traversed by the path in that row or column is bounded by the tag ...
- 486
1
vote
0
answers
41
views
Reducing time horizon in column generation subproblems using release dates and time windows
I am currently solving a column generation problem for my machine scheduling model. In the master problem, all orders are coordinated and the allocation plans are created in the individual subproblems ...
- 11
4
votes
3
answers
167
views
Mixed-Integer Programming Formulation for Unrelated Parallel Machine Scheduling with Sequence Length Constraints
I'm an engineer who is working on an unrelated parallel machine scheduling problem to minimize total completion time, but with an additional practical constraint: each machine has a maximum sequence ...
0
votes
1
answer
144
views
What is the biggest instance of VRP solved to optimality?
I am developing an algorithm for a variant of the Vehicle Routing Problem (VRP). For benchmarking purposes, I would like to know the largest VRP instances that have been solved to proven optimality, ...
- 111
4
votes
2
answers
195
views
Comparing L1 vs L2 norm objectives for minimizing deviation from due dates in parallel machine scheduling?
I'm a network engineer who is curious about a parallel machine scheduling problem where jobs have due dates, and I'm interested in understanding the trade-offs or advantages between using absolute ...
2
votes
0
answers
45
views
Example of an iterative algorithm considering the simplex of optimal solutions a sub-LP
Many algorithms in OR such as branch and cut, branch and price, column generation or sequential linear programming solve sub-LPs find an optimal solution and use it (or associated dual prices) to ...
- 4,307
0
votes
2
answers
133
views
How to linearize min/max function of a large number of values as a constraint?
Assuming I have 100 variables $r_1 \dots r_{100}$ which can be positive or negative and I try to find the minimum of all of them in a MILP problem and bind that to a variable $y$.
$$y = \min_{i \in \{...
- 4,307
0
votes
0
answers
75
views
How can I formulate this disaggregation problem as a network flow?
I am struggling to formulate this disaggregation problem as a network flow. Can anyone help me see a way to make things work? I am not fully familiar with all of the tricks and gadgets for network ...
- 1
1
vote
0
answers
69
views
How to give a sufficient or necessary condition of a ILP's relaxation?
I have a class of ILP questions in the form of:
\begin{align*}
\text{Max} \quad & c^T x \\
\text{subject to} \quad & Ax \leq b \\
& A \in \{0,-1,1\}^{(m+n+mn)*(mn+n)...
- 11
1
vote
1
answer
70
views
Fixing model.context.cplex_parameters.randomseed is sufficient to provide same optimal solution MILP with multiple optimal solutions?
I have perhaps a silly question. But I am observing some weird behavior when solving my MILP model. Using the same machine and environment, I solve my model twice, and I see that even if defining ...
- 23
5
votes
1
answer
271
views
MIP model for minimum spanning tree
In this post, Erwin Kalvelagen explores how the minimum spanning tree problem can me modeled with different MIPs. The models are based on Optimal Trees (Magnanti, Wolsey).
In the flow formulation II, ...
- 486
0
votes
2
answers
188
views
Upper bound on dual variable
Solving $\min_{As\le b} c^\top s$, where $As\le b$ is compact, using KKT conditions with complementary slackness encoding using MILP leads to:
\begin{align}
A^\top y+c&=0 \\
As &\le b \\
y &...
- 21
1
vote
2
answers
241
views
Cplex seems to terminate early as optimal before the default gaps
Cplex seems to terminate early as optimal before the default gaps? Why?
...
- 11
0
votes
1
answer
145
views
Solving a large scale MILP problem with cplex takes long time
I am solving a large scale MILP problem with cplex, it takes too much time and cannot obtain the solution, does it means that cplex is not suitable for this large scale MILP problem? what can I do to ...
- 11
2
votes
0
answers
63
views
Graph crossing minimization problem
I would like to formulate the graph crossing minimization problem as a MI(N)LP (it's ok if it is non linear) : given a graph $G(V,E)$, what is the minimum number of edge crossings in any drawing of $G$...
- 486
