Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
2
votes
2answers
92 views

Transformations that leave the linear program unchanged

A typical linear program is written as $$L_0:\min_{x \geq 0; A^\top x \leq b}c^\top x.$$ Here, $x \in \mathbb{R}^n$, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$. ...
0
votes
1answer
98 views

Objective function with exponential coefficients

I have a linear programming problem, with $n$ variables and $a\leq x_{i} \leq b$ for each variable $x_{i}$, where the objective function is $\min \sum\limits_{i=1}^{n}{2^{i} x_{i}}$ Is it true that, ...
10
votes
1answer
645 views

Linear Optimization Library for C++ with GPU Support

Does anyone know any linear optimization libraries for C++ supporting GPUs for parallelization? If multiple, which do you recommend? The GPU support is important to me since I am dealing with large ...
11
votes
1answer
134 views

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
-4
votes
1answer
102 views

Multiple If else constraints in Mixed integer programming

How to formulate the following as constraints in MILP? a[0][0] = y, if x[0]= 0, a[0][0] = 0, if x[0] != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b[0]...
19
votes
4answers
817 views

How can I remember the rules for taking the dual of a linear program (LP)?

When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?...
4
votes
2answers
188 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 ...
1
vote
0answers
49 views

Specializing Iterations of Dantzig-Wolfe Decomposition with an Oracle

This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the bounded ...
5
votes
2answers
167 views

Asymmetric time-constrained capacitated vehicle routing problem

I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4). The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent ...
4
votes
1answer
116 views

Extreme points of a simple polyhedron

Consider the polyhedron given by the set of inequalities \begin{align} \mathbf{b}^T\mathbf{x} ~&\leq~ c \\ \mathbf{e}^T\mathbf{x} - 1 ~&\leq~0 \\ \mathbf{x}~&\geq~0 \end{align} where $\...
9
votes
2answers
240 views

Common structures in Gurobi - Python

I'm new to Gurobi in Python and I was wondering if someone knows how to code some common structures of linear constraints. I'm trying to understand how you'll code something like the following ...
4
votes
2answers
155 views

Any Solution for $k$-means with minimum and maximum cluster size constraint?

I am looking for an efficient approach to $k$-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster. $N$ be the number ...
5
votes
4answers
448 views

How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
2
votes
1answer
92 views

On dual-formulation of a given primal for a set-covering problem

I need to solve an LP-relaxation of an airline crew pairing optimization problem (CPOP). The problem formulation is a modified SCP and is as follows: Primal of the CPOP: \begin{align}\min&\quad\...
2
votes
1answer
69 views

How to linearize inequalities having max or min?

I'm modeling an LP problem in which I have to maximize an objective function. Two of the constraints are the following, where $k_i$ are constants and $x_i$ decision variables (continuous). Could ...
0
votes
1answer
266 views

How to mathematically formulate the optimization problem?

I have a system with $S$ service points. There are also $U$ users in the system. We have $$U>S>G$$ One group can have maximum $M$ service points, but there is no restrictions on the number of ...
2
votes
2answers
100 views

How to deal with a decision variable in the objective function that depends on if-else conditions involving other decision variables?

I'm modeling an optimization problem in which a decision variable $x_1$ in the objective function depends on if-else conditions involving decision variables $x_2$ and $x_3$, as the following equation, ...
4
votes
1answer
323 views

Is there any automatic way to spot contradictory constraints in linear programming?

Let's have the following trivial linear program: \begin{align}\max&\quad z=20A+30B\\\text{s.t.}&\quad A\le60\\&\quad B\le50\\&\quad A+2B\ge220\\&\quad A,B\ge0\end{align} It's easy ...
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}$ ...
4
votes
3answers
216 views

Faster implementation of "or" constraints in ILP

I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
1
vote
0answers
66 views

LP instead of IP formulation of assignment problem

In the example files of GLPK, the assignment problem is written as a linear program. I don't understand why this isn't an integer programming problem. The problem formulation: ...
4
votes
3answers
111 views

warmstarting simplex algorithm- how much can problems differ from each other?

I'm working on an implementation of the simplex algorithm. I want to solve problems in real time every 30 minutes. They could be interpreted as a classic transportation problem. I couldn't really say ...
3
votes
2answers
316 views

If-then constraint with continuous variables

I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables $x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the ...
1
vote
1answer
150 views

How to linearize the product of a binary and a continuous variable? [duplicate]

Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
3
votes
0answers
101 views

Two binding constraints - Linear Programming

I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ...
2
votes
3answers
135 views

Linearizing a Max Function in the constraint - not working

I have a minimization function which is in its simplest form looks like below. I am including the index of the variables. ...
1
vote
1answer
104 views

Job Shop Scheduling Problem: jobs are scheduled on the same machine at the same time

I want to solve a job shop scheduling problem. I got $n$ Jobs that have to be scheduled on $k$ Machines. A Job $i$ has 2 or 3 Tasks $j$, and there is a known sequence of the Tasks of a Job. One ...
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
100 views

complexity order of the interior point method

I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5? Much appreciate your time and consideration.
0
votes
0answers
39 views

linear equation with conditions in Java

I have the following problem: I want to determine a linear equation for a data table with $x$ and $y$ value. Point 1 should be the point where the first time $y > 0$ and point 2 should be the point ...
1
vote
1answer
128 views

How to transform this problem with logarithmic objective function into an approximated convex optimization problem?

I have an objective function as follows $\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\...
0
votes
1answer
85 views

How to linearise this nonlinear constraint?

I have a constraint in the form $\sum_{n=1}^{N}x_{m,n}\omega_{m,n}\ge (t_u-1)\beta_u, \forall u, u=1,2,\cdots, U$ where $x_{m,n}$ is binary variable $t_u$ and $\beta_u$ are continuous optimization ...
0
votes
0answers
41 views

Linear equation from pairs of values with conditions in Gurobi (Java)

How can I create a linear equation in Gurobi (Java) from values (x-y value pairs) that also has the following properties: $\forall x \leq 0 \Longrightarrow y = 0$ The linear line/equation should have ...
2
votes
1answer
65 views

Constraining flow into a node and out of a node using Min Cost Flow input

Let's say I have a graph $G=(V,E)$ where each vertex has an edge going both into and out of it (i.e. cyclic, akin to the kidney donor pair problem). Now suppose we have a capacity $u_{ij} = 1 \forall(...
3
votes
1answer
128 views

Min Cost Flow with lower bound reduction to MCF algorithm

We define the Min Cost Flow Problem with Lower Bounds (MCFPLB) as a generalization of the usual Min Cost Flow. The input consists of: a directed graph $G=(V,E)$ capacities $u_{ij} \geq 0$ for each ...
2
votes
1answer
115 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 ...
10
votes
2answers
646 views

Do LP solvers convert LPs to standard form?

To solve a linear program (LP) using the simplex method one first needs to bring the LP to standard form. This requires replacing every equality constraint with two inequalities and replacing every ...
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
250 views

Clustering points based on a distance matrix

Although I asked this question on stackoverflow to possibly reach a broader audience, I wonder your inputs about this problem. Without giving much research into this, I thought p-center problem ($x_{...
2
votes
0answers
94 views

Solving transportation problem by the Network Simplex

I am trying to solve the following problem using Network Simplex method. But I have questions. My attempt: Basis Matrix$(B)$ Rows: 1, 2, 3, 4, 5 Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) $$ \...
4
votes
1answer
225 views

Algorithms for sparse linear systems

I've long wondered this, but what is the algorithm(s) implemented in modern linear equation solvers for sparse systems? The obvious answer I can think of is Gauss-Jordan with a bunch of tricks to make ...
2
votes
0answers
47 views

To estimate new sales from history

A fruit supplier sells 3 types of fruits. The company has 3 salespersons. Here are the sales quantity of each person for each fruit. The total sales figure is available. (this is all the available ...
3
votes
0answers
40 views

PuLP Python: How to linearize an inequality involving an integer variable

I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T. The total amount of payable tonnes i.e. what the customer will ...
2
votes
0answers
104 views

How can I see the engine log when solving a LP using pulp (python)?

I wonder which command should I use to see how the steps the pulp solver is doing when solving a linear program.
2
votes
1answer
108 views

How can I have minimum amount of resources wasted in this resource allocation problem?

I have a demand, $d$ I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by $s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+...
1
vote
1answer
176 views

How to dynamically set variable names in Pyomo?

I am looking to set variables in my Pyomo model by using a loop, so that they can be created automatically. However, each variable also contains bounds. I was hoping that it can loop through a ...
4
votes
2answers
369 views

Two-Objective Optimization in CPLEX

Until now, I used CPLEX to solve single-objective optimization problems only, but now I need to solve a two-objective mixed-integer linear optimization problem and I noticed that CPLEX 12.6.9 (unlike ...
7
votes
1answer
121 views

Maximizing a Ratio/Percent

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
7
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.
3
votes
2answers
115 views

Multi-objective function normalization

I am trying to solve the multi-objective function of my linear program. Are there another approaches other than the weighted sum approximation?

1
2
3 4 5
8