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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
21 views

Several questions on Column Generation: degeneracy, columns in/out and non-integer solutions

I am currently using Column Generation accompanied with Dantzig-Wolfe decomposition to solve MILP. I have several questions to ask. At the beginning, the objective value of RMP does not improve even ...
2 votes
2 answers
52 views

How to write a constraints on a first nodes for a courier-package problem?

We have an employee whose job is to pick up and deliver some packages, and they have each a capacity of C. They can also pick up multiple packages in their route, and packages can be transferred ...
  • 23
0 votes
0 answers
15 views

Is type of variables can help in linearization?

I was wondering if the type of variables, whether binary or non-negative can affect the linearization? For example assuming that $x_{i,j,t}$ and $y_{i,t,s}$ are two binary variables, then when we want ...
  • 367
1 vote
1 answer
69 views

How to linearize an if-then statement?

I want to write constraints for finding a path for some rider, driver on a directed network problem. Let $x_{i,j}^d$ indicate whether driver travels from $i$ to $j$ and $z_{i,j}^{r,d}$ indicates ...
  • 25
1 vote
1 answer
40 views

Linearize tricky constraint to MILP, LP

It's hard to describe this constraints. Please check this: It is a selection problem. Item Name Brand Value Price item 1 A 0.1 0.2 item 2 B 0.2 0.3 item 3 A 0.1 0.3 We want to select several ...
  • 13
2 votes
0 answers
45 views

Avoid Cycles in Integer Program

Traveling salesman problem can be cast to an integer program, see https://gurobi.github.io/modeling-examples/traveling_salesman/tsp.html. The problem is, however, that the solution might contain ...
  • 61
0 votes
0 answers
13 views

How to use SMT solver to prove model validation

I have a mixed-integer model with some parameters. I also have a set of validation rules telling me if the model is satisfiable. How can I use SMT solver to prove that my validation rules are valid ...
  • 143
9 votes
1 answer
124 views

Shortest palindromic Egyptian representation for reciprocal integers

Consider the problem of representing the reciprocal of an integer as an Egyptian fraction where all the denominators are palindromes. i.e. write $$ \frac{1}{n} = \sum_{i} \frac{1}{a_i} $$ where $a_i$...
  • 2,132
0 votes
1 answer
56 views

How to minimize the gap between a fractional linear expression with a constant value?

how to minimize the gap between a fractional linear expression with a constant value I have a selection problem with objective function like: $$ min\mid\frac{\sum a_i\cdot x_i}{\sum b_i\cdot x_i}-\...
  • 13
3 votes
1 answer
61 views

Issue with integer subproblem in Dantzig-Wolfe decomposition

I am dealing with an integer model, and I'm using Dantzig-Wolfe (DW) algorithm that I have developed in Matlab to decompose the model into a master and sub-problems. I put the integer constraints in ...
1 vote
1 answer
36 views

Portfolio optimization with cardinality constraint

The simple portfolio optimization problem with cardinality constraint is stated as \begin{align} \min_{\vec{w}} -\vec{\mu}^T \vec{w} + \frac{\gamma}{2} \vec{w}^T \Sigma \vec{w} \end{align} such that ...
  • 113
1 vote
2 answers
37 views

Q: penalizing variables deviating from a given ratio

I want my optimization variables $\phi_1, \cdots , \phi _n >0$ (positive real) to remain around a known ratio, say $\alpha_1 :\alpha_2 :\cdots :\alpha_n$, where $\alpha_i\in (0, 1)$. To be clear, ...
2 votes
2 answers
90 views

About Benders decomposition for MILP [closed]

I have been using Benders decomposition for the following MILP: Original problem I put the binary y variables into the residual subproblem, which is as follows: Residual subproblem The dual form is: ...
0 votes
1 answer
30 views

CNF form of the logical $exactly(2) x_{i}$

Let's say, in order to linearize the product of the two binary variables the logical condition would be, z <=> (x and y), where x, y, and z are binary. The corresponding CNF form is as follows: \...
  • 115
0 votes
1 answer
25 views

linearizing if-then with two binary invoved

I need to linearize this $\alpha_i^{ap}=1 \implies \beta_{ij}^{ap} =1 $. As both are binary, I think the right answer is $ \alpha_i^{ap} \ge \beta_{ij}^{ap} $. But rading one of the questions a the ...
-1 votes
2 answers
38 views

Conditional statement in mixed integer linear programming

I have been trying to enforce the following conditional statement in a MILP: If $X_1 + 2(X_2 + X_3) = 4$, then $X_4 = 1$. where $X_1, X_2, X_3, X_4$ are binary. How can I write this in conventional ...
3 votes
0 answers
69 views

How many variables and constraints can modern mixed integer programming solvers handle? [closed]

I know it depends on the specific problem instance, but approximately how large of an MIP problem can we write and still be guaranteed that an optimization solver will find a solution? For instance, ...
1 vote
1 answer
49 views

Which linearization is correct?

I'm trying to linearize the following constarints, however, Iam not sure if it's correct? Both of the make sense and seems incorrect at the same time! Could anyone help me to identify what I'm missing?...
  • 25
0 votes
1 answer
22 views

Is the product of two variable summations convex?

I have a mixed integer programming problem, which I believe may be convex. Namely, I have a matrix $R$, where rows are seats and columns are riders. The idea is optimally seat riders on the bus such ...
  • 203
2 votes
1 answer
25 views

Find cycles with fixed number of edges without shared vertices in a directed graph

I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, ...
  • 21
0 votes
0 answers
31 views

Minimizing $\|A x - b\|^2_2$ subject to $x \in \{0,1\}^n$ or $x \in \Bbb Z^n$

I have the following Boolean least-squares problem. $$ \underset{x \in \{0,1\}^n}{\text{minimize}} \quad \| A x - b \|_2^2 $$ where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^n$. A ...
2 votes
1 answer
74 views

Valid inequalities in a polyhedron

Let $\alpha, \beta >0, k \in \mathbb{Z}$, $\pi \in \mathbb{R}^n, \pi_0 \in \mathbb{R}$. Let $P\subset \mathbb{R}^n$ be a polyhedron, such that the inequalities: $$\pi x \leq \pi_0 +\alpha (x_j -k) $...
2 votes
1 answer
62 views

Maximising average of decision variables : mixed integer programming

I am trying to linearise a model I came up with for this problem: I have $n$ binary decision variables $x_i$ , each assosiated with a revenue $c_i$. The profit will be either the weighted average of ...
1 vote
0 answers
20 views

VRP where only a subset of vertices needs to be visited

Hi just a quick question, I am looking at a VRP problem, where only a subset of costumers needs to be visited. So given a complete graph G=(V,E) a fleet of vehicles needs to service a given number $n$ ...
  • 113
1 vote
1 answer
113 views

Multiplication of two continuous variables

I am working on MILP problem using AMPL/CPLEX. How to model the multiplication of two continuous variables x,y? and does it make a difference if they are integers? Thank you.
  • 33
2 votes
1 answer
51 views

Modelling a different ranges constraint based on a value

I want to set a variable $D$ to a certain value based on another variable $X$ depending on the range of $X$ as follows: if $0<x \le100 , D =2$ if $100<x \le200 , D =5.3$ if $200<x \le300 , ...
  • 33
0 votes
1 answer
32 views

Formulate nonlinear conditions as linear constraints.

Is there a way to formulated the conditions below in the form of linear constraint(s)? If $S_1 ≤ 1$ and $S_2 ≤ 1 ⇒ X = 0$ If $S_1 ≥ 2$ or $S_2 ≥ 2 ⇒ X ≤ 1$ $S_1, S_2 \in \left \{ 0, 1, 2 \right \}$ $X ...
  • 3
0 votes
1 answer
45 views

Linearize if else constraint in a MILP

How can you write the following if/else condition in a linear form? If S ≥ 3, then X ≤ 1, else X = 0 with S ∈{0, 1, 2, 3} X ∈{0, 1} I've seen some examples where X is forced to a value in the if ...
  • 3
0 votes
2 answers
70 views

How to convert a non-linear constraint to a linear constraint?

How to convert non-linear constraint $s_{k} = \min(t_i y_{ik})$ to MIP constraint? Here, $t_i$ is a positive decision variable and $y_{ik}$ is a binary decision variable.
1 vote
0 answers
16 views

Nonlinear discrete and continuous optimization problem

I'm trying to minimize a cost function that is made up of dependent binary variables and continuous variables. For example the cost function could look like: $F(x_{0}, x_{1}, x_{2}, r_{0}, r_{1}) = 0....
  • 111
0 votes
1 answer
80 views

How can I apply the McCormick Envelopes to the product of two binary variables?

I've seen the McCormick envelopes applied many times to the product of two continuous variables, but I can't seem to find when both of them are binaries. Also, I applied the restrictions as described ...
1 vote
0 answers
35 views

Conversion into MINLP

I want to solve the following optimization problem. \begin{aligned} \text{Objective:} \hspace{1cm} & \text{maximize} \hspace{0.2cm} \sum_{s=1}^{N}{\frac{1}{N}}\left[\sum_{t=1}^{T}\left(\frac{1}{...
  • 33
1 vote
2 answers
28 views

When to construct LP, IP, or MIP model

After doing a few optimization word problems, I've noticed I'm struggling a bit when trying to determine whether or not to set up the problem as an Integer Program, Linear Program, or Mixed Integer ...
0 votes
1 answer
24 views

Variable Neighbourhood search (VNS): How to specify the neighborhood structures?

I am new to optimisation and looking into VNS to attempt to apply a meta-heuristic to a MIQP in the form $$\max_x x^TQx$$ subject to: $x_i\in\{0,1\}$, $\sum_i x_i=C$, where $C$ is an integer. I don't ...
1 vote
1 answer
50 views

Need help establishing linear objective and linear constraints

So I have a problem, that is really similar to the assignment problem. Basically there is a company producing square envelopes. A number of papers should be put into the envelope. Exactly one paper pr ...
4 votes
2 answers
163 views

Problem-Heavy References in Linear/Integer/etc. Programming and Operations Research

I am reaching out for problem-heavy references in Linear / Integer / Mixed-Integer (MIP) / Non-Linear / Network Programming and Operations Research (and Linear Algebra as it pertains to the ...
user avatar
1 vote
1 answer
148 views

Linear Programming: Either OR constraint non-binary decision variables

I'm working on a production problem where I'm producing a number of products. My decision variables indicate quantity levels of production across a range of prices. My current LP solves for the ...
  • 23
1 vote
2 answers
33 views

Bin packing with load fairness across the bins

The bin pack problem denotes the process of assigning a set of n items into a minimal number of bins of capacity c. It can be simply formulated as an ILP as per the below description: My question is :...
1 vote
1 answer
48 views

Integer allocation problem alternative to MI-SOCP?

Can the following problem be solved without needing to use a MI-SOCP solver? I think I can code it as just a simple parallel branch-and-bound search but I'm not sure if the performance will be close ...
  • 13
1 vote
1 answer
22 views

Retaining the variable value for some consecutive intervals

I have been trying to model a constraint for a variable in an MIP formulation. My problem is like this; X(t) is a variable, whose value has to remain constant for some pre-defined consecutive periods ...
1 vote
0 answers
37 views

What is an unimodular problem?

Given an optimization problem below: $$ \min_{Y^m_{ij} \in \{0,1\}} \sum_{p \in P} \sum_{(i,j)\in A} \sum_{c \in C} n^c \rho_{ij}^{p,m(c)} X_{ij}^c\\ \text{where } X_{ij}^c \text{ solves:}\\ \min \...
2 votes
1 answer
288 views

How to transform a nonlinear constraint to linear constraint using big M?

Given a nonlinear constraint $$xy=0$$ where $x$ is a continuous variable and $y$ is a binary variable. Question: Using the Big-M method, how do I get to change the constraint above to a linear ...
2 votes
1 answer
72 views

How do I solve this mixed integer program?

I have a minimisation problem in the following form $$\textrm{min}: x^TAx$$ constrained by $\sum x_i=N$ where $x$ is a vector containing only 1's and 0's, and $A$ is a square matrix of real numbers. ...
2 votes
1 answer
120 views

What is the best way to convert this into a integer linear program and what is the best way to solve such a problem?

I am studying a mixed integer program in the form $$ \textrm{min}: \sum A x$$ constrained by $\sum x_i = N$ where $x$ is a vector containing only 1's and 0's, N is an integer, and $A$ is a square ...
1 vote
0 answers
49 views

Maximizing summation function with variable in index and in upper bound

I have a function $f(N_i, P_i) = \sum_{i=1}^M(N_i(1-kP_i))-\sum_{i=1}^M\sum_{j=1}^{N_i}\alpha_{ij}$, where $\alpha_{ij}$ are parameters. I want to maximize this function. I want to maximize this ...
  • 67
2 votes
2 answers
57 views

How do I transform the following set of conditions into inequalities?

I've been working on a mixed integer linear program for quite a while now and I need to set up constraints involving binary variables. I just can't find the correct answer to the following problem. ...
1 vote
1 answer
41 views

How to count gaps in a timetable?

I have a timetable with $n$ time slots. There can be an arbitrary amount of appointments in this timetable. Some example schedules for $n=4$: $(x_1, x_2, x_3, x_4)$: $(1,1,0,0), (1,0,0,1), (1,1,1,0) $,...
4 votes
0 answers
110 views

Minimizing the difference of convex functions in MIP

I am working on the following mixed-integer program (MIP): $\min_{\mathbf{x}, \mathbf{y}} \ f(x_{1}) - f(x_{2}) + c_{x}^{\top}\mathbf{x} + c_{y}^{\top}\mathbf{y} \\ \text{s.t.} \\ A\mathbf{x} + B\...
  • 303
2 votes
0 answers
24 views

Understanding "Blessing of Binary"

The theorem I am stating is Theorem 6.2 (Blessing of Binary) of the dissertation THE ROLE OF EXTREME POINTS FOR CONVEX HULL OPERATIONS, which was cited from Stochastic Dual Dynamic Integer Programming ...
  • 3,206
2 votes
1 answer
83 views

What are the prerequisites to learning integer programming and what textbooks would you recommend to learn it?

There was this course in many undergraduate mathematics programs called integer programming. It included Modelling, Linear Programming Primal, Linear Programming Duality, Dual Simplex Algorithm and ...

1
2 3 4 5
8