# 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.

387 questions
Filter by
Sorted by
Tagged with
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 ...
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
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
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
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
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
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
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
56 views

• 33
32 views

• 111
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
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
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 ...
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
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 ...
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 ... 1 vote
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
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
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
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
37 views

• 33
1 vote
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
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. ...
• 21
1 vote
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)$,...
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