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
50
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
106
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
125
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
135
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
58
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
76
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
103
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
144
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
2
votes
1
answer
122
views
How to decompose a specific constraint in the sub-problem?
I am trying to solve a scheduling problem related to the line balancing systems with the aim of column generation (price & branch). The simplified compact formulation would be:
\begin{align*}
\...
- 177
1
vote
1
answer
68
views
Mixed integer programming formulation of point cover with specified miscover rate?
Imagine a set of $N$ points in $R^m$ labeled $y_{+}$ or $y_{-}$. The task is to pick a corner of $m$ dimensional box $(x_1,x_2,...x_m)$ such that rectangle $(-\infty,-\infty,...,-\infty)$ to $(x_1,x_2,...
- 75
1
vote
1
answer
41
views
Stopping criterion of mathematical programming problem
I am currently working on a project that involves recreating results from A fix-and-optimize heuristic for the Unrelated Parallel Machine Scheduling Problem. I do not understand a constraint in the ...
2
votes
1
answer
116
views
0-1 Linear programming and non-optimal multidimensional knapsack
I would like to create a set of constraints forcing a set of knapsacks to be filled. The knapsacks should be filled, so that no further element of a set of elements fits into it. It is not a classical ...
- 265
0
votes
1
answer
83
views
Consecutive binary block in MIP modeling with variable length
I'm currently modeling a MIP and face a problem on how to tackle consecutive binarys.
I have a integer variable $A_v$ which marks the start time and a integer processing time $P_v$. I want to model ...
- 5
1
vote
1
answer
79
views
Reformulating Mixed-integer Bilevel program into MINLP
I am working on a problem where I have this Bilevel programming problem:
$ Max \quad a+b $
$s.t.\quad \quad \alpha \in \{0, 0.5, 0.8\} $
$\quad \quad \quad \; \ a = min \ \lambda$
$ \quad \quad \; \ ...
- 51
2
votes
2
answers
48
views
Explanation of multiple constraints from one rule [closed]
I'm trying to understand this case study:
https://github.com/DorisRipley/Art-Exhibition-Optimization-A-BIP-Modeling-Approach/blob/main/Art%20Exhibition%20Optimization.pdf
and I'm having trouble with ...
1
vote
1
answer
130
views
Find the optimal solutions to a system of linear equations?
I have a linear optimization problem $\mathbf{A}\cdot \mathbf{x} < \mathbf{0}$, where $\mathbf{A}$ is a particular square matrix for my application, and $\mathbf{x} \geq \mathbf{0}$.
I want to ...
- 19.3k
1
vote
1
answer
58
views
Trading model - apply fee at specific time point
I am currently developing an energy trading model, where I look a few hours ahead of the current time. This model is runned for several time points (but discretized into hours), namely for $\tau \in T=...
- 99
1
vote
0
answers
55
views
Formulate weight lifting as MILP problem
Consider two variables $x_1$, $x_2$ describing how high a weight is in two succeeding states. I need to minimize effort of lifting the weight, but I don't care about dropping the weight: $\min w\cdot\...
-1
votes
2
answers
72
views
Identify optimal product size configuration based on historical data and some constraints [closed]
We have historical data for the demand of a product. Product can be demanded in any quantity between 0-1000g and the historical data show the distribution of previous request sizes. We can only pack ...
2
votes
1
answer
88
views
Tractable formulation of a mixed integer program
Given constant matrices $A_1\in\mathbb{R}^{1\times l}$ and $A_2\in\mathbb{R}^{1\times l}$, and constants $b_i$, $i=1,\dots,n$. Consider the following mixed integer program (MIP) with decision ...
- 69
1
vote
2
answers
123
views
Formulating a linear programming/optimization problem with a "soft" constraint
I have an optimization problem which I hope I can formulate as a linear program. The problem involves a vector $x$ of binary decision variables (so each entry of the $x$-vector is either $0$ or $1$). ...
- 13
1
vote
1
answer
187
views
Task Assignment Problem using MILP (tasks >> agents)
I have a general assignment problem that assigns a set of payload tasks $T$ to a set of workers $A$, where $|T|$ >> $|A|$. Each task $T_i \in T$ consists of a tuple $(s_i, g_i)$, which represent ...
- 13
2
votes
1
answer
171
views
Mixed linear programming: why is big-M needed to set a variable to the max of other variables?
Let's say I want to set a variable $z$ to the maximum of other variables. We'll assume that the objective function is not of help, that is, the objective function doesn't try to minimize the maximum. ...
- 123
1
vote
1
answer
295
views
Non-linear optimization programming, with step function in constraint
I want to optimize a non-linear function $f(x)$, $f: \mathcal{R}^{n} \to \mathcal{R}$ (being a log-likelihood over $m$ observations, i.e. $i$ being the observation index) under constraints numerically,...
- 25
0
votes
1
answer
104
views
How can linear programming condition check if variable is a multiple of number?
Let's say we have linear programming problem
with x1 and x2 variables.
Maximize x1 + x2
where (for example)
0.3x1 + 0.7x2 <= 2
0.2x1 + 0.3x2 <= 3
How can be added one more condition, so linear ...
-1
votes
1
answer
174
views
How to linearize a max function in a constraint? [closed]
I have linear program that has constraint as follows:
$
\max(x,y) \geq 0
$
where $x$ and $y$ are variables.
How to linearize this inequality?
How to write this constraints in google or tools?
2
votes
0
answers
26
views
Vector simultaneous containment problem
Given a matrix $A\in\mathbb{R}^{n \times k}$, with rows $a_1,\dots,a_n \in \mathbb{R}^k$, I want to find vectors $\ell,u\in\mathbb{R}^k$ such that:
The (elementwise) inequality $\ell \le a_i \le u$ ...
- 483
2
votes
0
answers
262
views
How many hexagons to fill a square tile
I am filling a square tile of width wTile with equal hexagons stacked flat side on top of each other at an angle I call colourAngle as shown in the diagram. I call the rows of hexagons "Perp Line&...
2
votes
1
answer
206
views
Approximating the Max Cut Solution of a Graph by the Graph Laplacian
Given a weighted graph with $n$ vertices and weights $w_{ij}\geq 0$, the max-cut problem is equivalent to
$$
\max_{x \in \mathbb{R}^n} \sum_{i,j} w_{ij} (1-x_i x_j) \quad \mbox{s.t.} \quad x_i \in \{-...
- 209
0
votes
1
answer
98
views
Mutual exclusivity variables in mixed integer programming problems
I am working on a employee scheduling problems (assigning shifts to temporary workers) by modeling it as a MIP. There is a one shift per day constraint for the employees that restricts more than one ...
- 1
0
votes
1
answer
75
views
Does this linear integer optimization problem have a unique antichain of solutions?
I am working with an integer linear optimization problem which, abstractly, is:
Find $\vec{x}$ such that $\mathbf{A}\cdot \vec{x} \leq -1$, and such that the sum of the entries of $\vec{x}$ is as ...
- 19.3k
1
vote
1
answer
118
views
Indicator function with multiple conditions in optimization
I have the following problem
$$\begin{align*}
& \min \ f(X) \newline
& X = \begin{cases}
1&; x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3, \newline
0&; \text{otherwise}.
\end{cases} \...
- 945
1
vote
0
answers
29
views
Convert a MINLP problem with semi-continuous variables to a problem with continuous variables?
Is there a way do (approximately) convert a nonlinear optimization problem with semi-continuous design variables to a problem with continuous variables? I want to avoid the use of MINLP solvers and ...
- 31
0
votes
1
answer
123
views
How to linearize or formulate optimization constraints that are stated in terms of "if-then" sentence?
I am a engineer who is working on an optimization problem and my constraints are in the form of this statement "if $x_1=1$ then $d_1=1T$" where $T$ is just a given time period.
Scenario 1
...
3
votes
0
answers
128
views
Column generation when number of rows depend on number of columns.
Say I have the following optimization problem:
$$
\begin{align}
\textrm{minimize } & \sum_{p\in P}{c_p \lambda_p} \\
\textrm{s.t. } & \lambda_{p_1} + \lambda_{p_2} \leq 1, \forall p_1,p_2 \in ...
- 179
1
vote
0
answers
36
views
The facet-defining inequalities for a single resource scheduling problem
Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions:
$$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
- 177
0
votes
1
answer
96
views
SDP relaxation of mixed-integer nonlinear program
I am having trouble understanding the semidefinite programming (SDP) relaxation of a mixed-integer nonlinear program (MINLP) from section 3 of this paper. The optimization problem in MINLP form is
\...
2
votes
3
answers
96
views
Maximize sum of absolute values over a box set
I am interested in the following linear problem:
$$
\begin{array}{cl}
\max & |a_{11} x_1 + a_{12} x_2| + |a_{21} x_1 + a_{22} x_2| \\
\mathrm{s.t.} & 0 \leq x_1 \leq b_1 \\
& 0 \leq x_2 \...
- 41
1
vote
1
answer
97
views
Constraint formulation for variable cleaning times - MILP optimization
I have a Mixed Integer Linear Problem where I want to schedule the production of different orders ($O$) in which in each order, there is only one product ($P$) produced.
Each order can be produced ...
0
votes
1
answer
152
views
How to apply integer cut to a simple MILP?
I'm self-studying on cutting plane methods, and I'm reviewing the following problem from Bertsimas' book (see below). I know what cutting plane methods do, and how they eliminate infeasible solutions ...
- 71
0
votes
1
answer
114
views
MILP to LP; is it possible?
There is a machine that can produce $x_t \in [0, \overline x]$ quantities of a good in hour $t \in T = \{1, 2, \ldots, 8760\}$. The production of a unit has linear costs of $k_t \in \mathbb R_+$. The ...
- 811
2
votes
0
answers
162
views
MILP constraint for connected node selection
I am formulating constraints for a network as shown in Figure .
Blue circles represent a set of nodes, $N = \{1, 2, \ldots, 5\}$. Three different types of devices are connected to different nodes in ...
- 41
0
votes
1
answer
120
views
How to write if statement for 3 dimensional problem linear programming
I have a problem regarding formulating the following with math notation. My goal is that if shop i’s arrival time is lower than all the other shop’s arrival times, then shop i must be allocated to the ...
