Questions tagged [integer-programming]

For questions about mathematical optimization problems involving binary or general integer variables.

Filter by
Sorted by
Tagged with
1
vote
1answer
66 views

Efficient solver for multiway number partitioning

I am interested in the following problem. The input is a set of $n$ integers, and a fixed integer $k$. The required output is a partitioning of the integers into $k$ subsets, such that the smallest ...
2
votes
1answer
47 views

Constraints that set values to binary variables depending on other binaries

I am trying to write a mathematical problem that involves some conditions based on binary variables. More specifically, I have a set of three binary variables $d_1$, $d_2$, $d_3$ and depending on ...
4
votes
1answer
290 views

Indicator function in math programming

Let $x$ be an integer variable that takes the values $1$, $2$ or $3$. Let $y_1$ and $y_2$ be binary variables. I want to express the two following logical constraints: if $x=2$ then $y_1=1$ if $x=3$ ...
4
votes
1answer
88 views

Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)

I am trying to write a program to schedule a team of 8 individuals into shifts. I want to know how to model that every individual must get at least one night shift break, and must not work two ...
2
votes
1answer
57 views

How does the RCPSP's precedence constraint work?

In [1] the authors define the RCPSP (resource-constrained project scheduling problem) as follows: minimize $$ \sum_{t} t x_{n t} $$ subject to $$ \begin{array}{c} \sum_{t} x_{j t}=1, \quad j \in J, \\ ...
2
votes
2answers
68 views

IP model for k-rooted spanning forest

I am looking for an IP model for finding a $k$-rooted minimum spanning forest on an undirected graph $G$. Given a set of roots $R$ and a set of nodes $N$ $(R\cap N=\emptyset)$, I would find a forest ...
1
vote
1answer
140 views

Generating numbers that should add up to a fixed value while they follow a known distribution

Suppose a perishable item that is associated with a shelf life $m\in \mathcal{M} = \{1,\dots,M\}$. We have a periodic review system with stock level $S$, i.e., based on the inventory level of the item,...
3
votes
1answer
97 views

Modeling that there is no feasible solution to a linear system in mixed integer programming

My question is about how to construct a mixed integer programming to model that there is no feasible solution to a given linear system. Specifically, given $x\in \mathbb{R}^{n}$ and $z\in \{0,1\}^{d}$,...
3
votes
0answers
70 views

How to linearize a max min objective function?

Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables: $\underset{x}\max \underset{y}\min dy$ Associated with the linear set of constraints and right ...
3
votes
0answers
100 views

0 1 solution of linear programming problem with only equality constraints

I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that ...
0
votes
1answer
103 views

Assignment problem with variable tasks to be done

I'm dealing with a kind of assignment problem, in which I have a set of tasks $t$ to be executed by machines $w$, but these tasks depend on the variatns $v$ of components $m$ being selected, which is ...
1
vote
1answer
86 views

How can I linearise this nonlinear proportional relation constraint?

My optimisation problem has a constraint in the form \begin{equation} \begin{array}{*{35}{l}} \text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\...
2
votes
1answer
110 views

Can I solve the separation problem efficiently, when I have access to an optimization oracle?

Assume I have given a convex feasible set $X$ and I have an oracle that can optimize some linear objective function $c$ over $X$. Assume that I have given a point $r$. I want to solve the separation ...
5
votes
1answer
167 views

What underlies intlinprog in MATLAB?

When a paper says they used the intlinprog in MATLAB to solve an integer program, what system actually does the solving? I have seen documentation about Gurobi and MATLAB: does Gurobi always provide ...
4
votes
2answers
420 views

Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously

I would like to seek some advice on modeling the following logical condition: I would like to ensure that a group of binary variables do not equate to 1 simultaneously, i.e., $\omega_{1}=1, \omega_{2}=...
7
votes
4answers
1k views

What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?

I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity. I also have a fixed number of objects each of which ...
1
vote
0answers
44 views

Unifying constraint matrices in sparse situations

$\DeclareMathOperator\Set{Set}$ Let $Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$ where $A$ has $r=km$ rows and $k=O(1)$. I am trying to write $$ Set=\{x\in\...
1
vote
1answer
106 views

Constraint programming and scheduling issues

I have a constraint problem that I need to resolve, but I did not how know to model the problem: I have 11 employees, I will name them from $a$ to $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$. I have a small ...
3
votes
1answer
175 views

Formulation of Assignment problem as integer programming

We need to maintain as quickly as possible a complex system. In particular, we need to replace six of its components $\{P_1,\ldots,P_6\}$. We have three 3D printers $\{M_1,M_2,M_3\}$ which we can use ...
4
votes
3answers
148 views

How can I find the optimal assignments for this MILP problem heuristically?

I have an assignment problem as follows $\begin{equation} \begin{array}{*{35}{l}} \underset{d_{u,c}}{\max}\hspace{1mm}\hspace{1mm}\sum_{u=1}^{U}\sum_{c=1}^{C}d_{u,c}\omega_{u,c}\\ \text{}\text{...
9
votes
3answers
364 views

Are there explainability approaches in optimization?

In the machine learning community there is the big topic of explainability, where you want to make the solution of ML models explainable or derive explainable models. This is also interesting for ...
6
votes
1answer
1k views

What are good reference books for introduction to operations research?

The reference books should cover the wide range of problem-solving techniques and methods.
5
votes
0answers
80 views

Bounding the size of the dual solution

Given an primal optimization with bounded feasible set: $\max \{cx: Ax \leq b\}$. The feasible region of the dual is $D = \{y:y^\top A = c^\top, y \geq 0\}$. If the primal feasbile region is a ...
5
votes
1answer
147 views

ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied

Consider several Integer (0/1) ILP variables, i.e., Boolean variables, $x_i$'s. Consider an ILP constraint $x_1 + x_2 + x_3 \geq 1$ and another constraint $x_4 + x_5 + x_6 \geq 1$. I would like to ...
9
votes
2answers
407 views

How to maximize “contrast” between nodes on a graph?

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
2
votes
1answer
80 views

Minimizing a quadratic binary nonconvex function by CPLEX

I am using CPLEX 12.8 to minimize a quadratic binary nonconvex function, according to quadratic function by CPLEX. In particular, my function is the following: $$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{...
3
votes
2answers
69 views

How to improve relative mip GAP using CPLEX in a MIP

Supose that I have an integer feasible solution for a MIP and I provide this one for CPLEX. I have tested this situation in a problem and CPLEX have reported the following: ...
3
votes
1answer
125 views

Problems finding a feasible solution in a MIP

I am using CPLEX with Julia using the package JuMP to solve a MIP problem. In a small instance, I have tested my problem but, after 10 minutes, nothing happens. I have defined the following parameters ...
0
votes
1answer
99 views

Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree

I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie, I need Miller-Tucker-Zemlin formulation ...
5
votes
2answers
370 views

How to establish constraint between variables with multiple indexes using CPLEX in Python

I am new in CPLEX and I am using docplex in Python to solve an ILP. I would like to translate the following constraint in docplex: $$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}_{,...
2
votes
1answer
52 views

Has the concept of TU other application than proving convex hull characterizations?

If a matrix is totally unimodular (TU), then we know that $\text{\{}x| Ax\leq b \text{\}}$ is integral for all integral $b$'s. This is often used for convex hull proofs, but does the concept of TU has ...
3
votes
2answers
179 views

Modeling in integer programming vs modeling in constraint programming

I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams). Now I am trying to learn how to model with constraint programming. ...
4
votes
1answer
91 views

Contiguous service area constraint

Background: I have a set of ZIP codes (e.g., all of the state of Wisconsin), and am trying to figure out an optimization-based approach to identify a subset of these ZIP codes for a logistics service ...
3
votes
1answer
78 views

In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?

I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices. I have trouble ...
3
votes
1answer
52 views

Strict inclusion for facility location formula and aggregate facility location formula

I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\...
8
votes
4answers
310 views

Understanding integer programming solvers

I would like to verify if I understand the nature or workings of integer programming solvers. My understanding is that for integer programming problems like the knapsack problem or the traveling ...
3
votes
0answers
61 views

Optimal Seat Allocation Problem

I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
2
votes
2answers
98 views

Constraint to handle the machine-configuration's change between initial position and its first occurrence in the process

I am working with a kind of a reconfigurable process planning, meaning that the same machine can have different configurations and perform multiple operations. Each machine has an initial ...
1
vote
1answer
51 views

Priority Constraint

Suppose I have the following set of binary variables: $X_i$: $I$ ranges from {1,..,4} Highest priority among the three variables $X$ , $Y$ and $Z$ $Y_j$: $J$ ranges from {1,..,3} $Z_k$: $K$ ranges ...
4
votes
2answers
208 views

How to solve this convex problem heuristically?

I have the following problem $$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$ $$\text{subject to}$$ $$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$ $...
4
votes
3answers
818 views

Branch and bound algorithm programming code

I want to solve an integer programming problem using the branch and bound method, but I'm having trouble finding the programming code. From what I saw, almost all algorithms use it for traveling ...
3
votes
2answers
158 views

How to get an extreme ray of an LP from Gurobi

I am working on a problem of form \begin{equation} \begin{array}{l @{\quad} l} \mathrm{max}_{x, u} & p^{\top} u \\ \text{st.} & A u + a x \leq 0 \\ & x \in \{0, 1\...
0
votes
2answers
204 views

How can I formulate this specific if-then constraint?

IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly) AND IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly) $X$ and $Y$ are binary variables. What I'm actually trying to do is to charge the ...
3
votes
0answers
50 views

Flexible Job Shop with Preemption

I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
5
votes
1answer
55 views

Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...
6
votes
0answers
114 views

Help in solving resource allocation optimization problem

I've been pondering on this question for some work optimization, and I need some help in being directed to the right direction. I have multiple customers that require an amount of $X$, $Y$ and $Z$ ...
2
votes
1answer
311 views

Divisibility constraint in Integer programming

I have a simple question regarding the divisibility in integer programming suppose the objective function is $\text{max}\quad x_1 + x_2$ where the constraint is that the sum of $x_1$ and $x_2$ are ...
2
votes
1answer
78 views

confusing results of two models with different complexity

i have two models that address the same problem. the first one is : the second one is: for different instances for the same size (n=30) i found the following results ( the first column on the left ...
5
votes
1answer
215 views

How to determine the size of a model?

I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....). Is the number of variables $\mathcal O(n^3)$ because we have ...
6
votes
1answer
137 views

Literature on “simcity-like” problems

As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that. I have a set of "buildings" that I want to place on a small 2d ...