Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
44 views

Building blocks for unimodular matrices

I read Chapter 19.4 of Schrijver(1986) and get to know that every totally unimodular matrix can be produced by taking operations on network matrices and two certain matrices. I find that some paper ...
5
votes
2answers
119 views

In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working ...
2
votes
0answers
72 views

What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree. ...
5
votes
1answer
87 views

Use of comparisons in objective function of an ILP

If the objective function of a problem contains a comparison between two linear statements, can the problem still be defined as an Integer Linear Program? For example: $$\text{max} \sum_{\forall i,j} ...
2
votes
1answer
117 views

Benders Decomposition cuts for MILP problem with further separable subproblems

I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
2
votes
1answer
79 views

Is there any solver intended specifically for integer and binary variables alone on the optimization model other than solvers for MIP, MILP?

Any solvers which can be integrated in python where we can quickly solve if we have integer and binary variables alone in our model other than normal solvers for MIP, MILP?
0
votes
0answers
93 views

Check VRP instance is feasibility

Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
3
votes
1answer
178 views

Scheduling minimization Integer Programming problem formulation

I am working with integer optimization. I have a problem with $t$ tasks and every task $i$ needs $w_i$ weeks to be completed and $p_{il}$ workers on a specific week $l$. There is a total time in weeks ...
3
votes
0answers
40 views

MIP: Do binary variables perform better that integers? [duplicate]

I have a model where investments can be done in blocks. Now I could model this with integer or binary variables. Does anybody know which one is the better choice in terms of computational performance?
5
votes
1answer
88 views

if $x = 0$ then $y \ne b$

I'm trying to model the following: if $x=0$ then $y \ne b$ $y$ is a positive integer number( $y\le U$) and $x$ is binary and $b$ is a constant.
1
vote
2answers
165 views

How to make the elements of the solution of gurobi belong to the elements of the specified list?

If I want to use the elements of the list as the range of the solution, like list1 = [10,20,50,60,30],and the elements of the solution must belong to the elements of the list The sample example as ...
1
vote
0answers
70 views

How can I set the solution of gurobi to be a multiple of 10 instead of all integers?

For example, the solution for gurobi has two solutions, as follows: [10,20,50,70] [55,79,30,80] I only want to output solutions that contain only multiples of 10. The sample example as follow: ...
5
votes
1answer
112 views

Is that Ok to exclude fixed components from an objective function?

Suppose we have the following objective function with one decision variable $x_i$ where $p_i$ is a fixed parameter for each $i$ and also, $a$ is a constant for the problem \begin{align} \label{eq} \...
2
votes
1answer
114 views

Capacitated Maximum Coverage Location Problem, Python and Gurobi

I am building a variant of the maximum coverage location model and want to limit the amount of points that each "facility" can cover. I am using Gurobi optimization . I have tried using the ...
3
votes
1answer
77 views

Need help with an appointment scheduling problem

I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could ...
4
votes
1answer
79 views

An efficient Integer programming model for the minimum spanning tree problem?

Let $T=(V, E')$ be a spanning tree of a graph $G=(V, E)$. Rather than verifying for any subset of vertices $S\subseteq V$ that $|E'(S)|=|S|-1$, is there an efficient way to satisfy the spanning tree ...
1
vote
1answer
134 views

How to prove the following statement about convex hulls?

Consider $M$ finite sets of integer points $P_m$, $m=1,\ldots,M$. Let $$A = \left\{x_m\in\operatorname{conv}P_m, m=1,\dots,M, \sum_{m=1}^MN_mx_m=0\right\}$$ and $$B =\operatorname{conv}\left\{x_m\in ...
6
votes
1answer
101 views

Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?

The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "...
2
votes
1answer
64 views

Finding the minimum of a group of timings

I would like to seek some modeling advice on the following: Say for instance I have 5 nodes representing workstations of the operation of 5 jobs, and that I have less than 5 vehicles. Say I have two ...
7
votes
0answers
93 views

Characterization for total dual integrality

A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the ...
4
votes
1answer
63 views

Name for subclass of ILP without any inequality constraints (including constraints on x)

In "Myths and Counterexamples of Mathematical Programming" myth "IP Myth 21" says: The problem of finding $x\in \mathbb{Z}$ such that $Ax=b$, where $A\in\mathbb{Z}^{m\times n}$ ...
5
votes
2answers
93 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019. It's a problem about minimizing a sum of terms that are ...
7
votes
3answers
294 views

No-good cuts for general integer variables

Question: Suppose we have an integer program $\min\{c^\top{x}\mid{Ax\leq{b}},x\in\mathbb{Z}_+^n\}$, and suppose that $x^*$ is a feasible solution for this IP (or even that $x^*$ is an extreme point of ...
7
votes
2answers
405 views

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In ...
2
votes
1answer
183 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 ...
3
votes
1answer
63 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
2answers
185 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
67 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, \\ ...
3
votes
2answers
79 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 ...
3
votes
0answers
84 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 ...
1
vote
1answer
148 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
137 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}$,...
6
votes
2answers
317 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
110 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
92 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
114 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
191 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
430 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
46 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\...
4
votes
3answers
164 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{...
5
votes
0answers
85 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 ...
6
votes
1answer
176 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 ...
11
votes
3answers
432 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 ...
2
votes
1answer
88 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_{...
4
votes
2answers
104 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
147 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
125 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 ...
2
votes
1answer
55 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 ...