Questions tagged [mixed-integer-programming]
A mixed-integer programming (MIP) problem is a linear program where some of the decision variables are constrained to take integer values.
453 questions
1
vote
0
answers
33
views
Computing Minimum Mean Cycle with Specific Edge
A little context: I am implementing a branch and cut algorithm and I have a separation routine, where I construct a digraph and have to run a minimum mean cycle algorithm to check whether some ...
- 43
0
votes
1
answer
47
views
How to write a Dantzig-Wolfe reformulation for a variant of the assignment problem?
I am trying to solve a large instance of a specific assignment problem by column generation. The compact formulation would be something like this:
\begin{align*}
\text{Max}_{(compact)} \quad & \...
- 177
0
votes
1
answer
54
views
How to denote common condition for a group of constraints in MIP?
I am formulating in latex a mixed integer programming (MIP) problem (i.e., defining the objective function, decision variables and constraints).
Among the problem constraints, I have the following set ...
- 101
2
votes
2
answers
131
views
LP relaxation leads to exponential Branch & Bound
Consider the following LP program
$$ \min x_{n+1} $$
subject to:
$$ \sum_{i=0}^n 2 x_i + x_{n+1} = n $$
$$ x_i \in \{ 0, 1 \} $$
And $n$ odd.
The claim is that using the standard B&B algorithm ...
- 2,005
5
votes
1
answer
106
views
Column generation and reduced costs
Suppose I have a Master Problem (MP) with several inequality constraints for the decision variables, e.g.
$$\min c^Tx \quad \text{s.t.} \quad Ax \leq b, \quad \Vert x\Vert_1 \leq r, \quad x\geq 0.$$
...
- 157
0
votes
1
answer
80
views
How to deal with the different subproblems (II)?
This is a follow-up question regarding this post and I am looking for how the added patterns that are produced in the column generation procedure can affect the master problem. After trying to use a ...
- 177
2
votes
0
answers
34
views
Mixed integer model predictive control for exploration and exploitation planning
I have a dynamical system $\mathbf{x}_{k+1}=\mathbf{f}(\mathbf{x}_k,\mathbf{u}_k)$ tracking some pre-computed trajectory, $\mathbf{x}_t = (\mathbf{x}_{t,1},\cdots,\mathbf{x}_{t,K})$. Suppose we just ...
0
votes
1
answer
51
views
How to decompose a specific constraint in the sub-problem (II)?
This is a follow-up question on this one and I would like to know how the problem can be implemented in the coding layer. The decomposed problem is as follows:
Master problem:
\begin{align*}
\text{...
- 177
1
vote
0
answers
108
views
Find all Integer points inside a bounded domain
Given positive integer bounds $m_1,m_2,...m_n$, irrational numbers $p_1,p_2,...,p_n$ and a small real number $R > 0$, find all solution sets $k_1, k_2,..., k_n \in \mathbb{Z}$ satisfying $$0 < ...
- 533
0
votes
1
answer
126
views
How to deal with the different subproblems?
I am working on a problem to understand how the best structure of the problem to decompose would be. The compact formulation is as follows:
\begin{align*}
\text{Min}_{(compact)} \quad & \sum_s y_s ...
- 177
1
vote
1
answer
136
views
Linearization of Linear Fractional Constraint
Can this constraint be converted to a set of linear constraints:
$$
z_j \leq \sum_{c \in C} \left( \mu_c \cdot x_{cj} + (1 - \mu_c) \cdot \frac{L_{cj} \cdot (1+\beta_{cj})}{\sum_{k \in S} L_{ck} \...
0
votes
0
answers
59
views
Solving a System of Fully-Integer Linear Equations over a Bounded Finite Integer Vector Space with Clamping
Title is a bit of a mouthful, apologies.
Solving a system of integer linear equations which "describe a vector space" is a fairly well-explored problem with a number of good off-the-shelf ...
1
vote
1
answer
77
views
Multi-objective optimisation methods suitable for LPs and (M)ILPs
Which methods (classic/modern) are utilised to solve multi-objective optimisation problems compatible with linear programming (LP) and mixed-integer linear programming.
Utilised in the context of time ...
- 265
1
vote
0
answers
106
views
A discrete optimization problem
We have $\mathbf{A}\in \mathbb{C} ^{N\times K},\mathbf{A}=\left[ \begin{matrix}
a_{1,1}& …& a_{1,K}\\
…& a_{i,j}& …\\
a_{N,1}& …& a_{N,K}\\
\end{matrix} \right] ,|a_{i,...
- 31
2
votes
1
answer
146
views
How is it useful in branch-and-bound to focus on lowering the global dual bound?
It seems to me that if you want branch-and-bound to be highly efficient then you should try to determine good solutions (primal bounds) as fast as possible so that you can prune more subtrees on the ...
- 477